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];

where

loadFactor = 0.75;

If `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.

HashMap hash function problems in 1.4.0

### Like this:

Like Loading...

*Related*