## Wednesday, 19 June 2019

### Algorithms | Create own HashMap

1. Data Structure need to store the key-value pair.
Make an Entry class to store the HashMap Entries.
Variable: key, value and next
next (Entry) variable is used to avoid the collision of hashmap using chaining (linked list).

2. put() method to put new entries in hashmap.
Identify the bucket using hash (hashcode%SIZE)
• If no element exists in that bucket: put it as a new Entry.
• If element already exists: If element is duplicate, replace old one, otherwise, find the last element in the chain and add a new entry to the next pointer of the last element.

3. get() method :  return the element in the hashmap
Identify the element bucket by calculating the hash (hashcode%SIZE) of the key, and return the element using the equals method.

4. Define size in power on 2
Rehashing is good when the size is exponential of 2.
Set initial size = 2^4 = 16.
To expanding HashMap, make size to it's double using power, i.e. 2^5= 32.
To reducing HashMap, make size to its half using power, i.e. 2^3= 8.

public class MyHashMap {

// for better re-sizing is taken as 2^4
private static final int SIZE = 16;

private Entry table[] = new Entry[SIZE];

/**
* To store the Map data in key and value pair. Used linked list approach to avoid the collisions
*/
class Entry {

final String key;
String value;
Entry next;

Entry(String k, String v) {
key = k;
value = v;
}

public String getValue() {
return value;
}

public void setValue(String value) {
this.value = value;
}

public String getKey() {
return key;
}
}

/**
* Returns the entry mapped to a key in the HashMap.
*/
public Entry get(String k) {
int hash = k.hashCode() % SIZE;
Entry e = table[hash];

// Bucket is identified by hashCode and traversed the bucket
// till element is not found.
while (e != null) {
if (e.key.equals(k)) {
return e;
}
e = e.next;
}
return null;
}

/**
* If the map previously contained a mapping for the key, the old value is replaced.
*/
public void put(String k, String v) {
int hash = k.hashCode() % SIZE;
Entry e = table[hash];

if (e != null) {
// If we will insert duplicate key-value pair,
// Old value will be replaced by new one.
if (e.key.equals(k)) {
e.value = v;
} else {
// Collision: insert new element at the end of list
// in the same bucket
while (e.next != null) {
e = e.next;
}
Entry entryInOldBucket = new Entry(k, v);
e.next = entryInOldBucket;
}
} else {
// create a new bucket for the new element in the map.
Entry entryInNewBucket = new Entry(k, v);
table[hash] = entryInNewBucket;
}
}

public static void main(String[] args) {
MyHashMap myHashMap = new MyHashMap();

myHashMap.put("Awadh", "SSE");
myHashMap.put("Rahul", "SSE");
myHashMap.put("Sattu", "SE");
myHashMap.put("Gaurav", "SE");

Entry e = myHashMap.get("Awadh");
System.out.println("" + e.getValue());
}
}

Output:
SSE