How does HashMap work and how is implemented in Java?

1.	How does HashMap work and how is implemented in Java?
Answer» Hashmap compose with an array of node and Node is an object of a class which has following below object: HashKey of int type Key of type K Value of type V Reference of next Node Let’s see how it all together works, first will approach to hashing process, which uses a hashing algorithm to generate index position-taking as an input of hashkey value of the corresponding object. Let’s look on below code snippet: Class KeyDemo { String key; KeyDemo(String key){ This.key = key; } @Override public int hashCode() { return (int)key.charAt(0); } @Override public booleanequals(Object OBJ) { return key.equals((String)obj); } } The moment, when we passing the key object in the put method of hashmap like below Map map = new HashMap(); map.put(key, value); The HashMap calling the hashcode() method of object and get the 10 digit numeric value, which eventually passing to the hashing algorithms which is like below syntax f(h(hashCode (key) % array_length)) = {index position} of hashmap, ,where x is a hashcode value, according to the index position the hashmap insert the value object in the corresponding bucket. HashMap uses the linkedlist to store the value object. Below is the implementation of HashMap, where K is the Key and V is the Value, usually the initial capacity is always 16, whenever the map get instantiated and it's computed every time when its reach to a threshold value which is 0.75, public class Map<K, V> { private Entry<K, V>[] buckets; private static final int INITIAL_CAPACITY = 1 << 4; // 16 private int size = 0; public Map() { this(INITIAL_CAPACITY); } public Map(int capacity) { this.buckets = new Entry[capacity]; } public VOID put(K key, V value) { Entry<K, V> entry = new Entry<>(key, value, null); int bucket = getHash(key) % getBucketSize(); Entry<K, V> EXISTING = buckets[bucket]; if (existing == null) { buckets[bucket] = entry; size++; } else { // compare the keys see if key already exists while (existing.next != null) { if (existing.key.equals(key)) { existing.value = value; return; } existing = existing.next; } if (existing.key.equals(key)) { existing.value = value; } else { existing.next = entry; size++; } } } The retrieval process of HashMap is, it has to compute the hashcode whenever the get method call which along with the key, using the key, hashmap computes the index position and equal() plays the vital role to identify the correct object from the bucket or LinkedList. Below is the code snippet for same. public V get(K key) { Entry<K, V> bucket = buckets[getHash(key) % getBucketSize()]; while (bucket != null) { if (bucket.key.equals(key)) { return bucket.value; } bucket = bucket.next; } return null; } There is a collision issue happening which is usually taken care of by collision detection and collision prevention.

Answer»

Hashmap compose with an array of node and Node is an object of a class which has following below object:

HashKey of int type
Key of type K
Value of type V
Reference of next Node

Let’s see how it all together works, first will approach to hashing process, which uses a hashing algorithm to generate index position-taking as an input of hashkey value of the corresponding object. Let’s look on below code snippet:

Class KeyDemo { String key; KeyDemo(String key){ This.key = key; } @Override public int hashCode() { return (int)key.charAt(0); } @Override public booleanequals(Object OBJ) { return key.equals((String)obj); } }

The moment, when we passing the key object in the put method of hashmap like below

Map map = new HashMap(); map.put(key, value);

The HashMap calling the hashcode() method of object and get the 10 digit numeric value, which eventually passing to the hashing algorithms which is like below syntax

f(h(hashCode (key) % array_length)) = {index position} of hashmap, ,where x is a hashcode value, according to the index position the hashmap insert the value object in the corresponding bucket. HashMap uses the linkedlist to store the value object.

Below is the implementation of HashMap, where K is the Key and V is the Value, usually the initial capacity is always 16, whenever the map get instantiated and it's computed every time when its reach to a threshold value which is 0.75,

public class Map<K, V> { private Entry<K, V>[] buckets; private static final int INITIAL_CAPACITY = 1 << 4; // 16 private int size = 0; public Map() { this(INITIAL_CAPACITY); } public Map(int capacity) { this.buckets = new Entry[capacity]; } public VOID put(K key, V value) { Entry<K, V> entry = new Entry<>(key, value, null); int bucket = getHash(key) % getBucketSize(); Entry<K, V> EXISTING = buckets[bucket]; if (existing == null) { buckets[bucket] = entry; size++; } else { // compare the keys see if key already exists while (existing.next != null) { if (existing.key.equals(key)) { existing.value = value; return; } existing = existing.next; } if (existing.key.equals(key)) { existing.value = value; } else { existing.next = entry; size++; } } }

The retrieval process of HashMap is, it has to compute the hashcode whenever the get method call which along with the key, using the key, hashmap computes the index position and equal() plays the vital role to identify the correct object from the bucket or LinkedList. Below is the code snippet for same.

public V get(K key) { Entry<K, V> bucket = buckets[getHash(key) % getBucketSize()]; while (bucket != null) { if (bucket.key.equals(key)) { return bucket.value; } bucket = bucket.next; } return null; }

There is a collision issue happening which is usually taken care of by collision detection and collision prevention.

How does HashMap work and how is implemented in Java?

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment