Hacker News Reader

I’m missing something… doesn’t open addressing fail catastrophically the moment you try to insert more items than the table has buckets? (With very bad degradation in performance as you approach this saturation point)?

Is the idea that you only use open addressing in cases where you know you’ll place much fewer items into the table than the number of bins?

View on HN

When the load factor of an open-addressed hashtable gets too high, you allocate a larger set of buckets and rehash the table’s existing contents into them. You’ll have to do this with a chained hashtable anyway, as performance will start to approach O(n) once the table is overloaded.

This does mean that insertion time goes from a true O(1) to an amortized O(1), but that’s usually not an issue. (You can do the rehashing gradually if you really have to, but it’s probably not worth the complexity.)

Reply on news.ycombinator.com