CODEWITHSUNDEEP
data-structureshashtable
user1147717
user1147717

Reputation: 27

How does performance vary between a 1 million item hashtable and a 100 item hashtable

I know that there can be a performance issues with the hashtable, but how can the hashtable with 1 million item can be faster then a hashtable with 100 item?

Upvotes: 2

Views: 405

Answers (2)

Sean Patrick Floyd
Sean Patrick Floyd

Reputation: 298898

That depends on the efficiency of the hashing algorithm used.

If there are many collisions in the small map and none in the larger one then the larger one will be faster.

Read the HashMap javadocs to learn about initial capacity and load factor, and read about hash codes (starting with Object.hashCode()). (Hashtable is an ancient relic, don't use it.)

Upvotes: 5

BrokenGlass
BrokenGlass

Reputation: 160882

It all depends on the number of collisions: If there are no collisions at all in the hashtable with 1 million items it will be much faster than the one with 100 items and 100 collisions.

If there is no collision the lookup will be O(1) just using the hash key and a modulo (see perfect hash). In the case of collisions (assuming hashtable as array and collisions chained in a linked list) you have to sequentially walk through all of them until you find the item in question, which worst case with 100% collision rate (think constant hash function i.e.) will be O(n).

Upvotes: 11

Related Questions