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?

$\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 at 20:20

2 Answers 2

0
$\begingroup$

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

$\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 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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