3 ms·
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 defini
by jameshart 7y ago
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’.
- geophile 7y agoA 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.