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

1 Answer 1

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

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.