How HashMap works in Java

Most of you will agree that HashMap, today, is the most favorite topic for discussion in 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 this 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 does the method work get().
6. Notes

The only possible answer

If anyone asks me to explain How does HashMap work? ”, I will simply answer: “ By the principles of Hashing ”. Easier nowhere. To understand this and get an extended answer, you need to be sure that 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 it here: Working with hashCode and the equals method in Java

A little about the Entry class

A map, by definition, is “an object that holds pairwise values ​​and keys”. Pretty simple, right? Means, in HashMap there should be some mechanism storing pairs of Values ​​and Keys? The answer is 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 a 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 class instances 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 understand this step by step:

• First of all, we check if 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 null, это – всегда 0.


• In the next step, the hash value is calculated using the hash code of the key obtained by calling the 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 too high or too low a hash value. To solve this problem, they introduced another hash()function, and passed the value of the hash code of the object to it to bring the hash value into line with the size of the array.


• The function is now 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 the fact that 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 [bin] array? The answer is LinkedList. If you remember, the class Entryhas the " next" attribute. This attribute always points to the next object in the chain. This is exactly the behavior of LinkedList.

So, objects Entryare stored in the form LinkedList. When an object Entryis to be placed in a certain location, HashMap checks to see if there is already an entry in that location. If there is no record, then the object is placed at the given position. If 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 LinkedList. If the next variable is not null, the procedure is repeated for the next one until null. What if we put in another object with a different value but the same key as before? Logically, this should cause the old value to be replaced. How does this happen? In general, after determining the position of the object Entry, during the passage along LinkedListto the calculated position,HashMapinvokes the compare key method on each Entry. All of these Entryobjects LinkedListcan have similar hash codes, but the method equals()will check them for true similarity. This will only replace the value inside the Entry. Thus HashMap guarantees the uniqueness of all keys.

How the Java get() method works

We now have an idea of ​​how key-value pairs are stored in HashMap. The next big question will be: 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 in a method is determined put()has the same logic that the method uses get(). Once HashMapit determines the key of the object passed in the argument, it simply returns the value of the corresponding object Entry. If no match is 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 like a 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 store in an object Entryis an array with the name tableand type Entry.
• Each individual position in the array is called a bucket because it can contain the first element LinkedListof objects Entry.
• hashCode()The key is required to calculate the position of the object 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 nullof this is 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!