Java, Kotlin: HashMap Under the hood?

Definition

Java HashMap class is an implementation of Map interface based on hash table. It stores elements in key & value pairs which is denoted as HashMap<Key, Value> or HashMap<K, V>.

It extends AbstractMap class, and implements Map interface and can be accessed by importing java.util package. Declaration of this class is given below.

Java (java.util)

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

Kotlin (kotlin.collections)

expect class HashMap<K, V> : MutableMap<K, V>

Create a HashMap:

// HashMap creation with 8 capacity and 0.6 load factor
HashMap<Key, Value> numbers = new HashMap<>(8, 0.6f);

Notice the part new HashMap<>(8, 0.6). Here, the first parameter is capacity and the second parameter is loadFactor.

  • load factor : The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.
  • capacity : The capacity is the number of buckets in the hash table( HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.), and the initial capacity is simply the capacity at the time the hash table is created

How it works?

HashMap in Java works on hashing principles. It is a data structure which allows us to store object and retrieve it in constant time O(1) provided we know the key. In hashing, hash functions are used to link key and value in HashMap. Objects are stored by calling put(key, value) method of HashMap and retrieved by calling get(key) method. When we call put method, the hashcode() method of the key object is called so that the hash function of the map can find a bucket location to store value object, which is actually an index of the internal array, known as the table. HashMap internally stores mapping in the form of Map.Entry object which contains both key and value object.o understand Hashing , we should understand the three terms first: Hashing, Hash Function, Hash Value, Bucket

1. Hashing

Hashing is a technique to convert a range of key values into a range of indexes of an array. We’re going to use modulo operator to get a range of key values. Consider an example of hash table of size 20, and the following items are to be stored. Item are in the (key,value) format.

2. What is Hash function?

Hash function should return the same hash code each and every time when the function is applied on same or equal objects. In other words, two equal objects must produce the same hash code consistently. hashCode() method which returns an integer value is the Hash function. The important point to note that, this method is present in Object class. This is the code for the hash function(also known as hashCode method) in Object Class :

public native int hashCode();

3. What is Hash value?

HashCode method return an int value.So the Hash value is just that int value returned by the hash function. The result of hashCode(), say "132", is then the number of bucket where the object should be stored if we had an array that big. But we don't, ours is only 16 buckets long. So we use the obvious calculation 'hashcode % array.length = bucket' or '132 mod 16 = 4' and store the Key-Value pair in a bucket number 4.

4. What is bucket?

A bucket is used to store key value pairs. A bucket can have multiple key-value pairs. In hash map, bucket used is simply a linked list to store objects.Each bucket has a unique number — that’s what identifies the bucket. When you put a key-value pair into the map, the hashmap will look at the hash code of the key, and store the pair in the bucket of which the identifier is the hash code of the key. For example: The hash code of the key is 235 -> the pair is stored in bucket number 235. (Note that one bucket can store more then one key-value pair).

5. Example

In this case,

  • there is an array with 256 buckets (numbered, of course, 0–255)
  • there are five people. Their hashcodes, after being put through mod 256, point to four different slots in the array.
  • you can see Sandra Dee didn’t have a free slot, so she has been chained after John Smith.

Now, if you tried to look up a telephone number of Sandra Dee, you would hash her name, mod it by 256, and look into the bucket 152. There you’d find John Smith. That’s no Sandra, look further … aha, there’s Sandra chained after John.

Key points:

  • It is member of the Java Collection Framework.
  • It uses a hashtable to store the map. This allows the execution time of get() and put() to remain same.
  • HashMap does not maintain order of its element.
  • It contains values based on the key.
  • It allows only unique keys.
  • Its initial default capacity is 16, load factor will be 0.75
  • It permits null values and the null key
  • It is unsynchronized (If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally)

📱IMStudio 🎓is a team that doesn’t stop moving. We expound on subjects as varied as developing a software application and through to disruptive technologies.🎓

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store