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:
- 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.
- 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?