What is a java HashMap and How it works ?

What is a java HashMap and How it works ?

What is a HashMap ?

            The HashMap in Java is one of the most popular Collection class among Java programmers. The HashMap is a data structure, based on hashing, which allows you to store an object as key value pair, an advantage of using HashMap is that you can retrieve object on constant time i.e. O(1) if you know the key. The HashMap class implements Map interface and supports Generics from Java 1.5 release, which makes it type safe. There are a couple of more Collections, which provides similar functionalities like HashMap, which can also be used to store key value pair. Hashtable is one of them, but Hashtable is synchronized and performs poorly in a single threaded environment. one relatively new is ConcurrentHashMap, which provides better performance than Hashtable in a concurrent environment and should be preferred.

How HashMap works ?

            In Hashmap objects are stored by calling put(key, value) method of HashMap and retrieved by calling get(key) method. When we call put method, hashcode() method of the key object is called so that hash function of the map can find a bucket location to store value object, which is actually an index of the internal array, known as the table. HashMap internally stores mapping in the form of Map.Entry object which contains both key and value object. When you want to retrieve the object, you call the get() method and again pass the key object. This time again key object generate same hash code (it's mandatory for it to do so to retrieve the object and that's why HashMap keys are immutable e.g. String) and we end up at same bucket location. If there is only one object then it is returned and that's your value object which you have stored earlier. Things get little tricky when collisions occur. It's easy to answer this question if you have read good books on data structure and algorithms like this one. If you know how hash table data structure works then this is a piece of cake.

·         INTERNAL STORAGE

o   The JAVA HashMap class implements the interface Map<K,V>. The main methods of this interface are:

§  V put(K key, V value)

§  V get(Object key)

§  V remove(Object key)

§  Boolean containsKey(Object key)

HashMaps use an inner class to store data: the Entry<K, V>. This entry is a simple key-value pair with two extra data

o   A reference to another Entry so that a HashMap can store entries like singly linked lists

o   A hash value that represents the hash value of the key. This hash value is stored to avoid the computation of the hash every time the HashMap needs it.

In plain English all the keys with the same hash value are put in the same linked list (bucket).

Keys with different hash values can end-up in the same bucket.

When a user calls put(K key, V value) or get(Object key), the function computes

the index of the bucket in which the Entry should be. Then, the function iterates

through the list to look for the Entry that has the same key (using the equals()

function of the key).

In the case of the get(), the function returns the value associated with the entry (if

the entry exists).

In the case of the put(K key, V value), if the entry exists the function replaces it

with the new value otherwise it creates a new entry (from the key and value in

arguments) at the head of the singly linked list.

This index of the bucket (linked list) is generated in 3 steps by the map:

·         It first gets the hashcode of the key.

·         It rehashes the hashcode to prevent against a bad hashing function from

the key that would put all data in the same index (bucket) of the inner

array

·         It takes the rehashed hash hashcode and bit-masks it with the length

(minus 1) of the array. This operation assures that the index can’t be

greater than the size of the array. You can see it as a very computationally

optimized modulo function.

hash (getting from hash(key.hashCode())) is used to find the bucket location at which the Entry object is stored . Entry object stores in the bucket like this (hash,key,value,bucketindex) .

In Summary
1. HashMap works on the principal of hashing
2. HashMap uses the hashCode() method to calculate a hash value. Hash value is calculated using the key object. This hash value is used to find the correct bucket where Entry object will be stored
3. HashMap uses the equals() method to find the correct key
4. more than one key have the same hash value, Entry objects are stored as a linked-list with in a same bucket. With in a bucket values are stored as Entry objects which contain both key and value.