The curious case of the Map key with a unique hashcode

What would happen if a HashMap used a key which always returned the same hashcode ? Answer in images.

The underlying structure of a HashMap is akin to an array, where each entry in the array is a linked list of key/value pairs. The hashcode of the key is used to quickly lookup one of the lists indexed by the array.

When the key produces well distributed hashcodes, each entry in the array points to a list with a small number (ideally just one) of key,value pairs.

Well distributed hashcodes

If on the other hand the key always produces the same hashcode, then all array lookups will return the same list.

Map with unique hashcodes

Our HashMap has turned into a linked list… with the consequence that lookup times are also similar to a linked list O(n) versus O(1) for the original hashMap.

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