Lets Dive Deep Within HashMap Code...
This is very important and trending topic in java. In this post i will be explaining HashMap custom implementation in lots of detail with diagrams which will help you in visualizing the HashMap implementation. This is must prepare topic for interview and from knowledge point of view as well.
I will be explaining how we will put and get key-value pair in HashMap by overriding-
>equals method - helps in checking equality of entry objects.
>hashCode method - helps in finding bucket’s index on which data will be stored.
We will maintain bucket using arraylist and entry using linkedlist.
We store key value pair by using Entry<K,V>
- K key,
- V value and
- Entry<K,V> next (i.e. next entry on that location of bucket)
Entry<K,V> can be considered as Node even.
package sorting;
/**
* @author Upendra Joshi
*
*/
public class CustomHashMap<K, V> {
private Entry<K, V>[] table; // Array of entry
private int capacity = 16;// initial capacity of hashmap
static class Entry<K, V> {
K key;
V value;
Entry<K, V> next;
public Entry(K key, V value, Entry<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
}
@SuppressWarnings("unchecked")
public CustomHashMap() {
table = new Entry[capacity];
}
/**
* Method allows you put key-value pair in CustomHashMap. If the map already
* contains a mapping for the key, the old value is replaced. Note: method does
* not allows you to put null key though it allows null values. Implementation
* allows you to put custom objects as a key as well. Key Features:
* implementation provides you with following features:- >provide complete
* functionality how to override equals method. >provide complete functionality
* how to override hashCode method.
*
* @param newKey
* @param data
*/
public void put(K newKey, V data) {
if (newKey == null)
return; // does not allow to store null ,but in hashmap the senario is different it
// usually adds single null key record to 0th index we wont do it here
// calculate hash of key.
int hash = hash(newKey);
// create new entry.
Entry<K, V> newEntry = new Entry<>(newKey, data, null);
// if table location does not contain any entry, store entry there.
if (table[hash] == null) {
table[hash] = newEntry;
} else {
Entry<K, V> previous = null;
Entry<K, V> current = table[hash];
while (current != null) { // we have reached last entry of bucket.
if (current.key.equals(newKey)) {
if (previous == null) { // node has to be insert on first of bucket.
newEntry.next = current.next;
table[hash] = newEntry;
return;
} else {
newEntry.next = current.next;
previous.next = newEntry;
return;
}
}
previous = current;
current = current.next;
}
previous.next = newEntry;
}
}
/**
* Method returns value corresponding to key.
*
* @param key
*/
public V get(K key) {
int hash = hash(key);
if (table[hash] == null) {
return null;
} else {
Entry<K, V> temp = table[hash];
while (temp != null) {
if (temp.key.equals(key))
return temp.value;
temp = temp.next; // return value corresponding to key.
}
return null; // returns null if key is not found.
}
}
/**
* Method removes key-value pair from CustomHashMap.
*
* @param key
*/
public boolean remove(K deleteKey) {
int hash = hash(deleteKey);
if (table[hash] == null) {
return false;
} else {
Entry<K, V> previous = null;
Entry<K, V> current = table[hash];
while (current != null) { // we have reached last entry node of bucket.
if (current.key.equals(deleteKey)) {
if (previous == null) { // delete first entry node.
table[hash] = table[hash].next;
return true;
} else {
previous.next = current.next;
return true;
}
}
previous = current;
current = current.next;
}
return false;
}
}
/**
* Method displays all key-value pairs present in CustomHashMap., insertion
* order is not guaranteed, for maintaining insertion order refer
* LinkedCustomHashMap.
*
* @param key
*/
public void display() {
for (int i = 0; i < capacity; i++) {
if (table[i] != null) {
Entry<K, V> entry = table[i];
while (entry != null) {
System.out.print("{" + entry.key + "=" + entry.value + "}" + " ");
entry = entry.next;
}
}
}
}
/**
* Method implements hashing functionality, which helps in finding the
* appropriate bucket location to store our data. This is very important method,
* as performance of CustomHashMap is very much dependent on this method's
* implementation.
*
* @param key
*/
private int hash(K key) {
return Math.abs(key.hashCode() % capacity);
}
Lets calculate the time complexity of above hashmap in case of put operation.
We will calculate hash by using our hash(K key) method - in this case it returns key/capacity= 25%4= 1. So, 1 will be the index of bucket on which Entry object is stored.
We will go to 1st index, it contains entry with key=21, we will compare two keys(i.e. compare 21 with 25 by using equals method), as two keys are different we check whether entry with key=21’s next is null or not, next is not null so we will repeat same process and ultimately will be able to get Entry object.
Now let’s do complexity calculation -
There were 2 elements in HashMap and for getting Entry Object we iterated on both of them. Hence complexity was O(n).
Now lets check the time complexity for get operation:-
And we have to get Entry Object with Key=30, value=151 
We will calculate hash by using our hash(K key) method - in this case it returns
key/capacity= 30%4= 2.
So, 2 will be the index of bucket on which Entry object is stored.
We will go to 2nd index and get Entry object.
Now let’s do complexity calculation -
There were 3 elements in HashMap but we were able to get Entry Object in first go.
Hence complexity was O(1).
To Summarize the operations it is as mentioned below:-
Operation/ method | Worst case | Best case |
put(K key, V value) | O(n) | O(1) |
get(Object key) | O(n) | O(1) |
Comments
Post a Comment