4 ms·
It's always going to be a problem; even the best hash tables of this size will suffer performance problems as they age. As the table increases in size, less of
by emn13 14y ago
It's always going to be a problem; even the best hash tables of this size will suffer performance problems as they age. As the table increases in size, less of it will fit in memory/various caches, and more of it will involve (expensive, potentially numerous) disk seeks.
Once you take caches into account, hash tables are not ammortized O(1). Having said that, those graphs show delays of well over 100 milliseconds, and that sounds excessive. It's possible the delay is primarily due to a poor implementation and not so much due to inherent limitations.
- twoodfin 14y agoFor something like link coloring over a long history, a Bloom filter would seem to be ideal for reducing the number of true hash table lookups you'd need per page.
- emn13 14y agoLarge bloom filters have exactly the same problem. And since they're fixed size, you'd need a potentially huge bloom filter to avoid huge numbers of false positives; more likely you'd need to periodically regenerate it based on the original data. This is a really tricky optimization because on a positive hit you've introduced more random I/O! After all, you've got the bloom filter and then the hash table lookup. False positives are also bad - so you only save something on true negatives. Is it worth it? Only if you get the tuning just right.