Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Why can’t hash tables shrink and grow gracefully?


Because items are placed into buckets based on their hash, and as you add or remove buckets you need to redistribute items.

I guess it depends what your definition is of ‘graceful’.


A b-tree grows and shrinks gracefully because each update modifies O(log n) pages. And the base of the logarithm is pretty big.

A typical hash table is not graceful in this way, because while each insert is O(1), you occasionally need to rehash everything into a bigger table, and that is O(n). As I noted above, linear and extensible hashing avoid this problem. An insert that forces a reorg just reorgs one bucket.


It might be down to memory/space allocation after all.

All hashtable requires rehashing up to certain fill rate, otherwise it will regress to linear look up. For the two most popular implementations, linked-list based or open addressing based, the common strategy for rehashing is to create another instance of hash table and copy the KV over. But on disk, this will be disastrous.


They can. See linear hashing and extensible hashing.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: