HashMap in Java – How it Works?

Hashmap in Java is a class that implements Java map interface and found inside java.util package. It stores data based on key and value.

It stores elements in an unsorted manner, which means it does not return elements in the order they’re inserted.

Hashmap is denoted by “Hashmap<Key, Value>

Points to remember:

  • Data is inserted based on key and value.
  • It contains unique keys.
  • It may have one null key and multiple null values.
  • It is an unordered collection.
  • It is non-synchronized.

How does Hashmap in Java work?

Hashmap is a part of the Collections framework which use hashing technique. It uses an array data structure internally to store elements.

It works on the principle of hashing where keys are mapped to values. In Hashmap elements are stored using put() function and retrieved using get() function.

Internally, the combination of key and value is stored in the form of Entry, which can be further used to iterate over hashmap elements.

Now, let’s see how some of the methods works internally:

1. put() working:

 Map<String, Integer> map = new HashMap<>();
    
 map.put("John", 1);
 map.put("Harry", 2);

As you know, the put() method is used to store elements in hashmap. Whenever you call put method it checks for NULL and calculates the hash value of the key i.e hashvalue of “John”.

See the internal implementation:

  public V put(K key, V value) {
    if (key == null)
      return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K, V> e = table[i]; e != null; e = e.next) {
      Object k;
      if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        V oldValue = e.value;
        e.value = value;
        e.recordAccess(this);
        return oldValue;
      }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
  }

Here, as you can see, 

  • Using the hashcode, hashvalue is calculated
  • Using hashvalue, index position is calculated using indexFor() method.

2. get() working:

When we have to retrieve a value from hashmap we use get() method by passing key as a method parameter.

Internally, it works similarly to put() method where hashvalue is calculated for the object passed as an argument and returns the value form the Entry object.

If, nothing is found then NULL is returned.

See the internal implementation:

  public V get(Object key) {
    if (key == null)
      return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
      Object k;
      if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
        return e.value;
    }
    return null;
  }

Here, as you can see, 

  • Using the hashcode, hashvalue is calculated (same as put())
  • The Key provided in arguments is matched with the Entry object and returned back.

Hope you’ve understood what is hashmap in java and how it works.

For Examples and methods explanation visit here.

Happy Learning!

Map Interface In Java

Stack Class in Java