1
$\begingroup$

For open addressing, I know that once you have around 70% table being filled you should resize because more than that you get collision.

But for closed addressing, I read that load factor should not exceed 1 (m/n where m = number of items in the buckets and n = size of the table) otherwise trigger rehashing to grow the hashtable, which I find to have two problems:

  1. We could have 6 items in one bucket and the size of the table is 6 so we have load factor of 1 which supposed to be a good but in reality we have a terrible hashtable.
  2. if we spread the items ot the table we are only allowed to have one items per a chain (or bucket) for example if we have 7 items, and the size of the hashtable is 6, we can't have a bucket that holds 2 items or we trigger a rehashing.

if you have more items than the size of the hashtable it results a trigger, unless I am miss calculating something (which highly possible).

so how load factor works in seperate chaining ? what is the magical number to trigger resizing if exceeded? how many items per bucket can we have if the hash function is good and we spread the items all over the hash table?

Improve this question
$\endgroup$
1
  • $\begingroup$ What does make a load factor good? In my book, even measuring collision ratio was way too indirect. I want access by key fast: If possible, I'd monitor extra time spent due to collisions. $\endgroup$
    – greybeard
    May 8, 2022 at 20:20

3 Answers 3

Reset to default
1
$\begingroup$

There is actually a very simple answer: Measure. If you cannot measure the difference between different load factors then the whole question is pointless.

The actual optimal load factor depends on the cost of calculating hash values, cost of comparing items with same hash value, performance cost of having a larger hash table, and all these depend on your exact implementation.

Improve this answer
$\endgroup$
1
  • $\begingroup$ In fact, there are wrong beliefs circulating around about the properties of some algorithms, due to neglecting to measure. For instance, when you're implementing quicksort, you're "supposed to" switch to insertion sort for subsequences that are around 15 items long or so. In an implementation, I tried to find the cutoff which makes an improvement and found none! (Or like 3 items or something.)The cost of dispatching the indirect comparison functions dominated, relative to the cost of the extra recursion, so that even small insertion sorts added to the time. $\endgroup$
    – Kaz
    Jun 20 at 23:35
0
$\begingroup$

According to this Python does a rehashing when the load factor reaches $2/3$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Do you imply all implementations of Python language use the same load factor? Can you clarify whether closed addressing is used? $\endgroup$
    – John L.
    May 10, 2022 at 21:43
0
$\begingroup$

When you look up a value in a hash table, the minimum cost is: One calculation of the values hash code. One calculation of a location where the value would likely to be stored if it was present in the hash table. One comparison of two hash codes. If they match, one comparison of values.

Additional cost is: Checking whether the slot is unused (in that case there is no value with the hash code), and visiting additional locations.

The case that there is an entry with the correct hash code but the wrong value should be extremely rare. If it is not, that's not a problem with the load factor - fix the hash function instead. We can basically ignore this.

So we need to rebuild the hash table if the cost of finding more possible locations and comparing hash values is large compared to the cost of calculating one hash value and comparing two values that are equal. If the values to be hashed are integers, calculating the hash value and comparing two values is quite cheap. If the values to be hashed are strings containing Unicode with correct comparison, calculating hash codes and comparing strings will be expensive, and you can allow quite a large load factor.

And storage isn't free. A larger hash table (same number of entries but smaller load factor) will be slower purely because of its larger size.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.