From the constructor of
java.util.HashMap from J2SE 1.4.2 (reprinted without permission):
// Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table = new Entry[capacity];
loadFactor = 0.75;
initialCapacity is a power of two then it is used as the capacity. Combining this with the load factor you get a
threshold < initialCapacity. Had they only put that pesky “=” sign in the equation then we’d be all set. Ah well.
So what does this all mean? Given a distribution of hash values that fills each bucket only once (such as adding integers) and the default load factor of
0.75, if an initial capacity is a power of two then adding
initialCapacity elements will require at least one resizing of the hash table!!
It should also be noted that chaining is dominant for small non-power-of-two initial capacities (again, given the default load factor).
Something to keep in mind.