Super basic: How Hashmap works in Java

Hi there!
It is 2020 already and what's a better way to start off the new year than to recap what we've already know such as how to walk and breathe and get drunk? LOL

Today I might bring up some real basic concepts of hashmap in Java. I am pretty sure a lot of you already know better than anyone on this one. If that's the case, feel free to click the go back button but if you are a little unsure or have no idea what I am talking about, it is up to you spend 2 minute reading this article!

Well, the most well known definition of has a hash map would be a data structure that implements an associative array abstract data type, a structure that can map keys to values.

To make it even easier,
you know when we think of an array, we would probably think of a number index to access to a certain value. ex) arrayName[index]= value
Same goes to hash map except that we can use key instead of number index values.
As shown in the image below, the hashmap is an array of nodes that has Key and Value which makes look ups to be much easier and more efficient by using key values.

If we look into the hashmap slightly more in detail, we can see it looks like a table that has nodes so called buckets which can represent a class having following objects:

1. K key : key string value that we use for look ups
2. int hash: integer hashcode from the string key value
3. V value: the actual value that we want to access
4. Node next: to point out the next entry or node

Alright, now we kinda understand what the hashmap is, then it is time for us to have a try to work with it to understand how it actually works.

To explain the steps in order to access to a certain value using key, first of all, I would like to insert some values into the map first for better understanding.

To insert the values, we can use put(k,v) method and to to that, let's quickly create a simple hashmap called scroes where we will be storing the names and scores accordingly.

HashMap<String, integer>scores = new HashMap<String, Integer>();

Once the hashmap is created, the size of the map will be automatically initialised by 16 which makes the index of the map starts from 0 and finishes to 15.

Now let's say we want to put these three records into the scores map.

scores.put("Smith","100");
scores.put("Blake","87");
scores.put("King","100");

To start with the first record, we will be going through this put() method as shown below.

put(K k, V v)

hash(k)

index = hash & (n-1)

Let's go ahead and start inserting the data.

put(K k, V v) // k = "Smith" and v = "100"

hash(k) // This will get the hash of the string key. in this case hash("SMITH")= 79019862

index = hash & (n-1)// n= 16 and index will be 6

After this process, the map will look like this

After following the same steps for all the records, the map will end up looking like below

notice: I forgot to change the hash value for the second record for Kings in the picture. just note that the hash value for king is different from the one for Blake

Wait, hold on a second, some of you might have noticed that we have 2 records in index 4 node. How did this happen?

If we scroll back a bit up to where we get the index by hash & (n-1), we can check those two records end up having same index which is 4 in this case. Let's say we tried to put Blake's record first and there shouldn't have been any problem, like we understood the data "Blake | hash| score| null" must have been inserted.

But as we insert Kings record after, we will figure out that they have same index number, the map will automatically put the record next to the Blake's record by changing the null value to point out to the next node which is King's in this case. That is how the outcome looks like the map above.

This will also lead us to this question.
"If they have same index number, how do we access to them?"

In order to access to the nodes, we can use get(k) method.
This method looks like this.

V get(Object key)
hash(key)

Index = hash & (n-1)

Now, let's say we want to find King's score in this hashmap using

scores.get("King")

then it will get the hash which is 2306996 and will get the index number which is 4 in this case. In the first node which has index 4, it will compare hashcode between the hascode that we are looking for and the hashcode that this node has. For example, the hascode we are looking for is 2306996 and the node has 63281940 as a hash value. They don't match, so it will be pointed out to the next node which and will do the comparison again. This time the hash value do match since it has 2306996 which we are looking for.

notice: I forgot to change the hash value for the second record for Kings. just note that the hash value for king is different from the one for Blake

Alright!
Today, we have talked about some of the basic concepts of hashmap. Actually, the reason I brought this topic up today was that I realised that hashmap come across very often we we code and it is very easy to just overlook, thinking that we understand how it works 100%. However, when I faced some complicated issues, I realised that I wasn't really understanding how it works and how to use it properly. I hope it helped for some of you guys to understand little bit better about hashmap and not get confused later when we really need to go through some concepts along the way of programming.

Thanks a lot for your time to read this article and Happy new year!!!

Comments

[Michael Tharrington]

Nice idea for a feature image! 😀

[Emma Ham]

Thank you, Michael!

[nago-alexandru]

Hi, the hash values from the last example dont match with the values in the picture. In the picture both entries have the same hash at index 4. Thank you for the article!

[Emma Ham]

good found! just added a comment about that! I've missed out on value changing on the picture! Thanks for the input!