Q:

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?

A:

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

A:

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

