java.util.HashMap

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s