HashMap in Java

Hashing

Hashing is transformation of a string of characters to a shorted fixed length value that represents original text. A shorter value helps in indexing and faster searches.

In Java, every object has a method `public int hashcode()` that will return a hash value for given object.

Map in Java

A map is an associative array which lets you store a key value association:

key1 -> value1

key2 -> value2

The Map interface in Java is not a sub type of Collection interface, hence, its behavior is a bit different from rest of the collection types.

Map hierarchy

Features of Map interface:

· Map doesn’t allow duplicate keys, but duplicate values can be stored.

· Null key and values are allowed in implementation except TreeMap.

· Ordering of maps have predictable order in TreeMap and LinkedHashMap but not in HashMap

· Maps are used to performs look ups by keys, or if there is requirement to retrieve or update an element by its key.

HashMap

HashMap is a class in Java which implements Map interface using hash table. HashMap has a table of array of Nodes and each Node is basically a LinkedList inside table.

HashMap structure

· Each Index in the table is known as bucket

· Each bucket is a node which can be LinkedList of nodes.

By default, HashMap comes with a table of size 16.

HashMap operations

In HashMap, put API computes the hash of the ‘key’, and where to place it in the table index, it is decided by using a modular operation.

In mathematical terms, we divide ‘hash-code’ using maximum value of the range and remainder will be the value which can be fit within the range.

There can be scenarios, when we are trying to put the data and index calculated turns out to be the same which has been used earlier, in that case, we use the benefit of having LinkedList at each node and simply add the <K,V> pair at the same node and the earlier <K,V> pair will point to the latest one.

Data storage representation of HashMap

· In Java, HashMap allows null key which always goes to index 0, since Hash of null is calculated as 0.

HashMap implementation

To have a detailed look at how HashMap is implemented in Java, we can try to have our own implementation.

Step 1:

Create a structure of a single bucket of HashMap, where every node is a LinkedList.

Node structure

We can even override the implementation of calculating Hash code:

Hash-Code Calculation

Step 2:

Let us look at the ‘put’ and ‘get’ operations of HashMap, which can also be implemented.

#PUT

Put operation

#GET

Get operation

I have uploaded the implementation code of HashMap at the following Github repository for your reference:

reeshabh90/HashMap-Implementation