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

Question

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?

Are you talking about `Hashtable`, `HashMap`, `ConcurrentHashMap` or hash tables in general? What did you find when you experimented with them yourself? — Peter Lawrey, Jan 18 '12 at 20:16

score 11 · Answer 1 · answered Jan 18 '12 at 18:06

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).

score 5 · Answer 2 · edited May 23 '17 at 12:03

5

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.)

edited May 23 '17 at 12:03

Community

1
1

answered Jan 18 '12 at 18:06

Sean Patrick Floyd

292,901
67
465
588

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

2 Answers2