From what I read, the load factor of a hashtable is defined as n/N where n=number of items N=Number of buckets in the hash table

Its recommended you increase the size of your hashtable when load factor is 0.75

Now my question is this

If I have 75 items in my list and the size of the hashtable is 100, is it not possible that multiple items are in the same bucket? Which means I could also be using just 40 buckets. So why not resize when number of buckets used reaches close to 100 instead of looking at number of items?


The reason you want number of buckets N to be greater than number of keys n, is that no algorithm (hashvalue + compression) gives a perfect even distribution of keys though the buckets. So when n starts approaching N, the odds of collisions become higher. Which means you will have longer linked lists in certain buckets. Thus increasing the time to find that key.

| cite | improve this answer | |
  • $\begingroup$ Can the down voter tell me the reason? $\endgroup$ – developer747 Aug 23 '15 at 18:19

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