How does HashMap work in Java

Most of you will agree that HashMap, today, is the most favorite topic for discussion during interviews. Sometimes I had similar discussions with my colleagues and it really helped. Now I will have such a discussion with you. I assume that if you are interested in the internals and workings of HashMap, then you are already familiar with the basics of HashMap , so I will skip that part. But if you're new to this, I suggest you head over to the Java Docs site . Before we move on, I highly recommend you check out my previous article: Working with hashCode and the equals method in Java. Contents of this article:

1. The only possible answer.
2. What is Hashing.
3. A little about the class Entry.
4. What does the put().
5. How the method works get().
6. Notes

The only possible answer

If anyone asks me to explain " How does HashMap work?" ", I will simply answer: " According to the principles of Hashing ." It couldn't be simpler. To understand this and get an extended answer, you need to be sure you know the basics of Hashing. Right?

What is Hashing

Hashing in its simplest form is a way of converting any variable/object into a unique code after applying any formula/algorithm to their properties. A true hash function must follow the following rule: A hash function must return the same hash code whenever it is applied to the same or equal objects. In other words, two identical objects must return the same hash codes in turn. You can read more about this here: Working with hashCode and equals method in Java

A little about the Entry class

By definition, a map is “an object that stores values ​​and keys in pairs.” Pretty simple, right? So, there must be some kind of mechanism in HashMap that stores pairs of Values ​​and Keys? Answer - Yes. HashMaphas an inner class Entrythat looks like this:

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//остальной code тут…
}

Naturally, the class Entryhas a Key and Value stored as attributes. The key is marked as finaland we also see two additional fields: nextand hash. We will try to understand the purpose of these fields as the article progresses.

What does the Java put() method do?

Before we dive into the implementation of the method put(), it is very important to understand that instances of a class Entryare stored in an array. The HashMap class defines this variable as:

/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть
* кратна двум!
*/
    transient Entry[] table;

Now take a look at the method implementation code put():

/**
* Связывает определенное meaning с определенным ключом в этой карте(map).
* Если карта перед этим содержала meaning для данного ключа, это meaning
* заменится на новое.
*
* @param key
*            ключ с которым указанное meaning должно быть связано.
* @param value
*            meaning которое должно быть связано с ключом.
* @return вернет предыдущее meaning связанное с key, or null
*         если не было значений связанных с key. (Вернет null
*         так же, если перед этим key был связан со meaningм null)
*/
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;
}

Let's figure it out step by step:

• First of all, we check whether the key exists. If the key does not exist ( null), the value is placed in the table at position zero because the hash code for the value is null, это – всегда 0.


• In the next step, the hash value is calculated using the hash code of the key obtained by calling the method hashCode(). This hash value is used to calculate the position in the array where the object will be placed Entry. The JDK designers assumed that a poorly written function hashCode()could return a hash value that was too high or too low. To solve this problem, they introduced another hash()function and passed the hash value of an object into it to make the hash value match the size of the array.


• Now the function is called indexFor(hash, table.length)to calculate the exact position where the object will be placed Entry.


• This is where the main part begins. Now, based on what we know that - two unequal objects can have equal hash codes, we ask the question: Will two different objects be placed in the same position in the [bucket] array? The answer is LinkedList. If you remember, the class Entryhas an attribute " next". This attribute always points to the next object in the chain. This is exactly the behavior LinkedList.

So, objects Entryare stored in the form LinkedList. When an object Entryis to be placed at a specific location, HashMap checks to see if there is already an entry at that location. If there is no entry, then the object is placed at this position. If, however, there is already an object at this position, the next attribute is checked. If it returns nulland the current object Entrybecomes the next link in the LinkedList. If the next variable is not null, the procedure is repeated for the next one until it finds null. What if we put another object with a different value but with the same key as before? Logically this should result in the old value being replaced. How does this happen? In general, after determining the position of an object Entry, while traversing LinkedListto the calculated position, HashMapit calls the key compare method for each object Entry. All of these Entryobjects LinkedListmay have similar hash codes, but the method equals()will check for true similarity. This will only replace the value within the Entry. Thus, HashMap guarantees the uniqueness of all keys.

How does the Java get() method work?

Now we have an idea of ​​how key-value pairs are stored in HashMap. The next big question is: What happens when an object is passed from a HashMap to a method get()? How is the value of an object determined? We should already know the answer, because the way in which the uniqueness of a key is determined in the method put()has the same logic that the method applies get(). Once HashMapit determines the key of the object passed in as an argument, it simply returns the value of the corresponding Entry. If no matches are found, the method get()will return null. Let's take a look at the code:

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

The code above is similar to the method put()up to this point if (e.hash == hash && ((k = e.key) == key || key.equals(k))). After that it simply returns the value of the object.

Notes

• The data structure to be stored in an object Entryis an array with a name tableand a type Entry.
• Each individual position in the array is called a bucket because it can contain the first element LinkedListof the objects Entry.
• hashCode()The key is required to calculate the object's position Entry.
• equals()The key is used to check the uniqueness of the key in the map( map).
• hashCode()and equals()Values ​​are not used in methods get()and set()in HashMap.
• The hash code for keys with a value nullis always 0. And such an object Entrywill always be stored in the zero position of the array.

I hope I conveyed my thoughts correctly in this article. If you find errors or have questions, please leave them in the comments. Happy learning!