Why are hash table expansions usually done by doubling the size?

by

Hash-tables could not claim “amortized constant time insertion” if, for instance, the resizing was by a constant increment. In that case the cost of resizing (which grows with the size of the hash-table) would make the cost of one insertion linear in the total number of elements to insert. Because resizing becomes more and more expensive with the size of the table, it has to happen “less and less often” to keep the amortized cost of insertion constant.

Most implementations allow the average bucket occupation to grow to until a bound fixed in advance before resizing (anywhere between 0.5 and 3, which are all acceptable values). With this convention, just after resizing the average bucket occupation becomes half that bound. Resizing by doubling keeps the average bucket occupation in a band of width *2.

Sub-note: because of statistical clustering, you have to take an average bucket occupation as low as 0.5 if you want many buckets to have at most one elements (maximum speed for finding ignoring the complex effects of cache size), or as high as 3 if you want a minimum number of empty buckets (that correspond to wasted space).

More Related Contents:

  1. Hash table runtime complexity (insert, search and delete)
  2. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  3. Hashing a Tree Structure
  4. How does a hash table work?
  5. hash function for string
  6. Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
  7. Data structures for loaded dice?
  8. Find kth smallest element in a binary search tree in Optimum way
  9. How to implement a queue using two stacks?
  10. How do you validate a binary search tree?
  11. Computing set intersection in linear time?
  12. Best algorithm to test if a linked list has a cycle
  13. How to delete in a heap data structure?
  14. Array remove duplicate elements
  15. What is the difference between tree depth and height?
  16. Probability of collision when using a 32 bit hash
  17. What is the fastest way to find the closest point to a given point?
  18. O(klogk) time algorithm to find kth smallest element from a binary heap
  19. Compute rank of a combination?
  20. Given a number, produce another random number that is the same every time and distinct from all other results
  21. What hashing function does Java use to implement Hashtable class?
  22. Skip List vs. Binary Search Tree
  23. graph – Dijkstra for The Single-Source Longest Path
  24. How can I return an array of struct in solidity?
  25. The intersection of all combinations of n sets
  26. Which is faster, Hash lookup or Binary search?
  27. Reason for the number 5381 in the DJB hash function?
  28. Algorithm for merging two max heaps?
  29. Why is vector array doubled?
  30. How to apply binary search O(log n) on a sorted linked list?

Leave a Comment