2) Simple HashMap
Req:
Need a data structure for fast searching operations.
Idea:
Rather than linearly searching elements in worst case, create a hashed data structure.
DS:
1) Create a Node (Key, Value , Hash , ptrNext)
2) Create a table of nodes, where each node location is a bucket
Put: (Addition of elements with (Key,Value) when key is not null)
1) Calculate index for table:
1.1) Get hashcode
1.2) Perform hashing
1.3) Do bitwise and with size
2) Check if table[index] is null or not
2.1) If null then put the value (create a new node) then ++size
2.2) If not null (Hash Collision-> two diff objects having keys producing same hashcode hence same index)
2.2.1) Check if the given key is already present or not (check both hash and equals) may
be traversing linked list in the worst case.
if key is found then replace the old value with the new value.
2.2.2) Else create a new node with the given key,value pair and add to linked list then ++size
(After certain threshold : linked list is converted to BST)
Get : (Get key,value mapping using key when key is not null)
1) Calculate index for table:
1.1) Get hashcode
1.2) Perform hashing
1.3) Do bitwise and with size
2) Check if table[index] is null or not
2.1) If null then return null
2.2) If not null
2.2.1) Check if the given key is already present or not (check both hash and equals) may
be traversing linked list in the worst case.
if key is found then return the node.
2.2.2) Else return null; Equality and Hash Code
While equality makes sense from a general perspective, hash codes are much more technical. If we were being a little hard on them, we could say that they are just an implementation detail to improve performance.
Most data structures use equals to check whether they contain an element. For example:
List<String> list = Arrays.asList("a", "b", "c");
boolean contains = list.contains("b");The variable contains is true because, while instances of "b" are not identical (again, ignoring String interning), they are equal.
Comparing every element with the instance given to contains is wasteful, though, and a whole class of data structures uses a more performant approach. Instead of comparing the requested instance with each element they contain, they use a shortcut that reduces the number of potentially equal instances and then only compare those.
This shortcut is the hash code, which can be seen as an object’s equality boiled down to an integer value. Instances with the same hash code are not necessarily equal but equal instances have the same hash code. (Or should have, we will discuss this shortly.) Such data structures are often named after this technique, recognizable by the Hash in their name, with HashMap the most notable representative.
This is how they generally work:
When an element is added, its hash code is used to compute the index in an internal array (called a bucket).
If other, non-equal elements have the same hash code, they end up in the same bucket and must be bundled together, e.g. by adding them to a list.
When an instance is given to
contains, its hash code is used to compute the bucket. Only elements therein are compared to the instance.
This way, very few, ideally no equals comparisons are required to implement contains.
As equals, hashCode is defined on Object.
Hashing :
HashMap without hash() check, performance lag:
package com.tcs.hdfc.rxconnect.hashing;
import java.util.Objects;
class MyHashMap {
private int size;
private Node[] table;
public MyHashMap(int size) {
this.size = size;
table = new Node[size];
}
class Node {
private Object ele;
private Object key;
private int hash;
private Node next;
public Node(Object ele, Object key, int hash) {
this.ele = ele;
this.key = key;
this.hash = hash;
}
}
public void put(Object key, Object value) {
int hash;
int index;
if (key != null) {
hash = hash(key);
index = hash & size - 1;
if (null != table[index]) {
// traverse linked list
Node ptr = table[index];
boolean isKeyAlreadyPresent = false;
for (Node pptr = ptr; pptr != null; pptr = pptr.next) {
ptr = pptr;
if (ptr.key.equals(key)) {
// replace old value
ptr.ele = value;
isKeyAlreadyPresent = true;
break;
}
}
if (!isKeyAlreadyPresent) {
Node node = new Node(value, key, hash);
ptr.next = node;
}
} else {
table[index] = new Node(value, key, hash);
}
}
}
public Object get(Object key) {
int hash;
int index;
Object value = null;
if (key != null) {
hash = hash(key);
index = hash & size - 1;
if (table[index] != null) {
for (Node pptr = table[index]; pptr != null; pptr = pptr.next) {
if (pptr.key.equals(key)) {
value = pptr.ele;
break;
}
}
}
}
return value;
}
private int hash(Object val) {
return val.hashCode();
}
}
class FullName {
String fname;
String lname;
public FullName(String fname, String lname) {
this.fname = fname;
this.lname = lname;
}
@Override
public String toString() {
return "FullName [fname=" + fname + ", lname=" + lname + "]";
}
@Override
public int hashCode() {
return Objects.hash(fname, lname);
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
FullName other = (FullName) obj;
if (fname == null) {
if (other.fname != null)
return false;
} else if (!fname.equals(other.fname))
return false;
if (lname == null) {
if (other.lname != null)
return false;
} else if (!lname.equals(other.lname))
return false;
return true;
}
}
public class Hashing1 {
public static void main(String[] args) {
// MyHashMap hashMap = new MyHashMap(8);
// hashMap.put("Mohit", "test");
// hashMap.put("Rohit", "test");
// hashMap.put("Sumit", "test");
// hashMap.put("Mohit", "test1");
//
// System.out.println(hashMap.get("Mohit"));
//
// System.out.println("testing without hash impact");
MyHashMap myHashMap = new MyHashMap(5);
// FullName fullName1 = new FullName("Mohit", "Malhotra");
// FullName fullName2 = new FullName("Rohit", "Malhotra");
FullName fullName3 = new FullName("Malhotra", "Mohit");
// FullName fullName4 = new FullName("Sumit", "Malhotra");
// FullName fullName5 = new FullName("Amit", "Malhotra");
FullName fullName33 = new FullName("Malhotra", "Mohit");
// myHashMap.put(fullName1, "fullName1");
// myHashMap.put(fullName2, "fullName2");
// myHashMap.put(fullName4, "fullName4");
// myHashMap.put(fullName5, "fullName5");
//
myHashMap.put(fullName3, "fullName3");
myHashMap.put(fullName33, "fullName3 hacked");
System.out.println(myHashMap.get(fullName3));
System.out.println(myHashMap.get(fullName33));
}
}HashMap with hash() check,
import java.util.Objects;
class MyHashMap {
private int size;
private Node[] table;
public MyHashMap(int size) {
this.size = size;
table = new Node[size];
}
class Node {
private Object ele;
private Object key;
private int hash;
private Node next;
public Node(Object ele, Object key, int hash) {
this.ele = ele;
this.key = key;
this.hash = hash;
}
}
public void put(Object key, Object value) {
int hash;
int index;
if (key != null) {
hash = hash(key);
index = hash & size - 1;
if (null != table[index]) {
// traverse linked list
Node ptr = table[index];
boolean isKeyAlreadyPresent = false;
for (Node pptr = ptr; pptr != null; pptr = pptr.next) {
ptr = pptr;
if (ptr.hash == hash(key) && (ptr == key || ptr.key.equals(key))) {
// replace old value
ptr.ele = value;
isKeyAlreadyPresent = true;
break;
}
}
if (!isKeyAlreadyPresent) {
Node node = new Node(value, key, hash);
ptr.next = node;
}
} else {
table[index] = new Node(value, key, hash);
}
}
}
public Object get(Object key) {
int hash;
int index;
Object value = null;
if (key != null) {
hash = hash(key);
index = hash & size - 1;
if (table[index] != null) {
for (Node pptr = table[index]; pptr != null; pptr = pptr.next) {
if (pptr.hash == hash(key) && (pptr == key || pptr.key.equals(key))) {
value = pptr.ele;
break;
}
}
}
}
return value;
}
private int hash(Object val) {
int h = val.hashCode();
return h ^ (h >>> 16);
}
public int size() {
return size;
}
}
class FullName {
String fname;
String lname;
public FullName(String fname, String lname) {
this.fname = fname;
this.lname = lname;
}
@Override
public String toString() {
return "FullName [fname=" + fname + ", lname=" + lname + "]";
}
@Override
public int hashCode() {
return Objects.hash(fname, lname);
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
FullName other = (FullName) obj;
if (fname == null) {
if (other.fname != null)
return false;
} else if (!fname.equals(other.fname))
return false;
if (lname == null) {
if (other.lname != null)
return false;
} else if (!lname.equals(other.lname))
return false;
return true;
}
}
public class Hashing2 {
public static void main(String[] args) {
// MyHashMap hashMap = new MyHashMap(8);
// hashMap.put("Mohit", "test");
// hashMap.put("Rohit", "test");
// hashMap.put("Sumit", "test");
// hashMap.put("Mohit", "test1");
//
// System.out.println(hashMap.get("Mohit"));
//
// System.out.println("testing without hash impact");
MyHashMap myHashMap = new MyHashMap(5);
FullName fullName1 = new FullName("Mohit", "Malhotra");
FullName fullName2 = new FullName("Rohit", "Malhotra");
FullName fullName3 = new FullName("Malhotra", "Mohit");
FullName fullName4 = new FullName("Sumit", "Malhotra");
FullName fullName5 = new FullName("Amit", "Malhotra");
FullName fullName33 = new FullName("Malhotra", "Mohit");
FullName fullName331 = new FullName("Mohit", "Malhotra");
myHashMap.put(fullName1, "fullName1");
myHashMap.put(fullName2, "fullName2");
myHashMap.put(fullName4, "fullName4");
myHashMap.put(fullName5, "fullName5");
System.out.println(fullName33.hashCode() & myHashMap.size() - 1);
System.out.println(fullName331.hashCode() & myHashMap.size() - 1);
myHashMap.put(fullName3, "fullName3");
myHashMap.put(fullName33, "fullName3 hacked");
myHashMap.put(fullName331, "fullName331");
System.out.println("-----------Testing index----------");
System.out.println(getIndex(fullName1, myHashMap.size()));
System.out.println(getIndex(fullName2, myHashMap.size()));
System.out.println(getIndex(fullName3, myHashMap.size()));
System.out.println(getIndex(fullName4, myHashMap.size()));
System.out.println(getIndex(fullName5, myHashMap.size()));
System.out.println(getIndex(fullName33, myHashMap.size()));
System.out.println(getIndex(fullName331, myHashMap.size()));
System.out.println(myHashMap.get(fullName1));
System.out.println(myHashMap.get(fullName2));
System.out.println(myHashMap.get(fullName3));
System.out.println(myHashMap.get(fullName4));
System.out.println(myHashMap.get(fullName5));
System.out.println(myHashMap.get(fullName33));
System.out.println(myHashMap.get(fullName331));
}
public static int getIndex(Object key, int size) {
int h = key.hashCode();
return (h ^ (h >>> 16)) & size - 1;
}
}With Interface :
import java.util.Objects;
interface MyMap {
public void put(Object key, Object value);
int size();
Object get(Object key);
interface Entry {
Object getValue();
void setKey(Object key);
Object getKey();
void setValue(Object value);
}
}
class MyHashMap implements MyMap {
private int size;
private Node[] table;
private SimpleList entryList;
public MyHashMap(int size) {
this.size = size;
table = new Node[size];
}
static class Node implements MyMap.Entry {
private Object value;
private Object key;
private int hash;
private Node next;
public Node(Object ele, Object key, int hash) {
this.value = ele;
this.key = key;
this.hash = hash;
}
@Override
public Object getValue() {
return value;
}
@Override
public void setValue(Object value) {
this.value = value;
}
@Override
public Object getKey() {
return key;
}
@Override
public void setKey(Object key) {
this.key = key;
}
}
public SimpleList entryList() {
entryList = convertMapToList();
return entryList;
}
private SimpleList convertMapToList() {
Entry[] entries = new Entry[size];
for (int i = 0; i < table.length; i++) {
}
return null;
}
@Override
public void put(Object key, Object value) {
int hash;
int index;
if (key != null) {
hash = hash(key);
index = hash & size - 1;
if (null != table[index]) {
// traverse linked list
Node ptr = table[index];
boolean isKeyAlreadyPresent = false;
for (Node pptr = ptr; pptr != null; pptr = pptr.next) {
ptr = pptr;
if (ptr.hash == hash(key) && (ptr == key || ptr.key.equals(key))) {
// replace old value
ptr.value = value;
isKeyAlreadyPresent = true;
break;
}
}
if (!isKeyAlreadyPresent) {
Node node = new Node(value, key, hash);
ptr.next = node;
}
} else {
table[index] = new Node(value, key, hash);
}
}
}
@Override
public Object get(Object key) {
int hash;
int index;
Object value = null;
if (key != null) {
hash = hash(key);
index = hash & size - 1;
if (table[index] != null) {
for (Node pptr = table[index]; pptr != null; pptr = pptr.next) {
if (pptr.hash == hash(key) && (pptr == key || pptr.key.equals(key))) {
value = pptr.value;
break;
}
}
}
}
return value;
}
private int hash(Object val) {
int h = val.hashCode();
return h ^ (h >>> 16);
}
@Override
public int size() {
return size;
}
}
class FullName {
String fname;
String lname;
public FullName(String fname, String lname) {
this.fname = fname;
this.lname = lname;
}
@Override
public String toString() {
return "FullName [fname=" + fname + ", lname=" + lname + "]";
}
@Override
public int hashCode() {
return Objects.hash(fname, lname);
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
FullName other = (FullName) obj;
if (fname == null) {
if (other.fname != null)
return false;
} else if (!fname.equals(other.fname))
return false;
if (lname == null) {
if (other.lname != null)
return false;
} else if (!lname.equals(other.lname))
return false;
return true;
}
}
public class MyHashMapTest {
public static void main(String[] args) {
// MyHashMap hashMap = new MyHashMap(8);
// hashMap.put("Mohit", "test");
// hashMap.put("Rohit", "test");
// hashMap.put("Sumit", "test");
// hashMap.put("Mohit", "test1");
//
// System.out.println(hashMap.get("Mohit"));
//
// System.out.println("testing without hash impact");
MyMap myHashMap = new MyHashMap(5);
FullName fullName1 = new FullName("Mohit", "Malhotra");
FullName fullName2 = new FullName("Rohit", "Malhotra");
FullName fullName3 = new FullName("Malhotra", "Mohit");
FullName fullName4 = new FullName("Sumit", "Malhotra");
FullName fullName5 = new FullName("Amit", "Malhotra");
FullName fullName33 = new FullName("Malhotra", "Mohit");
FullName fullName331 = new FullName("Mohit", "Malhotra");
myHashMap.put(fullName1, "fullName1");
myHashMap.put(fullName2, "fullName2");
myHashMap.put(fullName4, "fullName4");
myHashMap.put(fullName5, "fullName5");
System.out.println(fullName33.hashCode() & myHashMap.size() - 1);
System.out.println(fullName331.hashCode() & myHashMap.size() - 1);
myHashMap.put(fullName3, "fullName3");
myHashMap.put(fullName33, "fullName3 hacked");
myHashMap.put(fullName331, "fullName331");
System.out.println("-----------Testing index----------");
System.out.println(getIndex(fullName1, myHashMap.size()));
System.out.println(getIndex(fullName2, myHashMap.size()));
System.out.println(getIndex(fullName3, myHashMap.size()));
System.out.println(getIndex(fullName4, myHashMap.size()));
System.out.println(getIndex(fullName5, myHashMap.size()));
System.out.println(getIndex(fullName33, myHashMap.size()));
System.out.println(getIndex(fullName331, myHashMap.size()));
System.out.println(myHashMap.get(fullName1));
System.out.println(myHashMap.get(fullName2));
System.out.println(myHashMap.get(fullName3));
System.out.println(myHashMap.get(fullName4));
System.out.println(myHashMap.get(fullName5));
System.out.println(myHashMap.get(fullName33));
System.out.println(myHashMap.get(fullName331));
}
public static int getIndex(Object key, int size) {
int h = key.hashCode();
return (h ^ (h >>> 16)) & size - 1;
}
}Last updated
