CODEWITHSUNDEEP
java
C G
C G

Reputation: 41

Order of growth - Load factor effect on hash tables

I did an experiment to see how load factors had an effect on hash table performance and got these results

enter image description here

I am confused on what the order of growth would be for 50%,70% and 90%. Would it be that 50 and 70 percent are constant and 90% is N?

Upvotes: 0

Views: 370

Answers (2)

Aplet123
Aplet123

Reputation: 35560

The complexity of insertion into a hashmap is the complexity of the hashing algorithm plus the length of the maximum chain (or size of largest block of continuous data if not using hashing with chaining). Anything less than a 100% load factor does not guarantee a chain of more than 1 length, which means that it is still O(1) on average, just with a larger constant factor. You can see in your graph that the 90% load factor does not go up like a line and is somewhat random, which is to be expected.

Upvotes: 1

Jonathan Locke
Jonathan Locke

Reputation: 303

A good load factor for hashtables (or disk drives) is around 70%. After this, performance degrades, which is what you are seeing. At 90% full, the hash map is spending almost 5X as much time searching for data as it is with 50%. You can also see on your graph that 70% isn't that much worse than 50%, so a lot of people choose this load factor.

Upvotes: 0

Related Questions