2 ms·

Growing hashtable based on number of unsuccessful probes is essentially the same as grow based on load ratio (α). Because the expected number of probes can be

• _benedict 10y ago
  Well, you're assuming a perfect uniform distribution of your values. Skew in data is common, since cryptographic hash functions are uncommon (since they're expensive), and any way we generally store collections vanishingly smaller than infinity, in which case even a perfect distribution will produce clusters with varying frequency; and each will degrade differently under these situations. At the extreme, if every item produces the same hash code, growing on reprobes will result in exponential insert complexity (since every insert will trigger a grow). Growing on load factor will just maintain O(n) insert/lookup complexity (or the complexity of the hash bucket, if not open-addressing). With less extreme skew, growing on load factor will simply use less memory than growing on reprobes, while reprobes will have a slightly lower median (and possibly mean) insert/lookup costs.