-1
$\begingroup$

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?

$\endgroup$

closed as off-topic by Kaveh, Tyson Williams, jbapple, David Eppstein, R B Aug 23 '15 at 19:52

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh, Tyson Williams, jbapple, David Eppstein, R B
If this question can be reworded to fit the rules in the help center, please edit the question.

0
$\begingroup$

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.

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