A new fast hash table in response to Google’s new fast hash table
Sort of off topic: In theory hash tables are supposed to be O(1) (under the RAM model). But looking at these graphs, they seem to grow linearly after they stop fitting in the cache which is especially apparent on the unsuccessful lookup graph. Since it's on a log-scale graph, O(log(n)) would probably fit better.Just thought it's an interesting divergence between what's taught in school and in practice. I wonder if there's something that's more predictive than big Oh for these types of analysis.