Creating our own hashmap in java
March 11, 2013 33 Comments
This is an attempt to come up with my own hashmap in java. It serves all basic needs of original java.util.HashMap with O(1) complexity in read operations. Full source code can be downloaded from here
To deep dive into the fundamentals of java.util.HashMap refer to this article
STEP1: Create a simple data structure with key, value and which can also extend as linked list
- line #2,#3: references to key and value
- line #4: link to itself (used when there is collision in the hashmap)
class Entry {
Employee key;
String value;
Entry next;
Entry(Employee k, String v) {
key = k;
value = v;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public Employee getKey() {
return key;
}
}
STEP2: Couple of important utility methods
- getSupplementalHash(): Supplemental hash function used to defend against the poor quality hash given by the user
- getBucketNumber(): It makes sure the bucket number falls within the size of the hashmap based on the value of hash
private int getSupplementalHash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
private int getBucketNumber(int hash) {
return hash & (SIZE - 1);
}
STEP3: PUT Method
- line #3: get the user defined hashcode
- line #4: defend against the poor quality hash functions defined by the user (if Employee.hashcode() is poor, this call will do a better job)
- line #8: get the bucket index
- line #12: If the control reaches into for loop, it means that it should either be a duplicate or a collision
- line #14-15: Its a duplicate, it will be replaced with old one
- line #20: Its a collision, new pair will be appended to the list
- line #28: Its either a new_pair/collision, add it to the map
public void put(Employee key, String value) {
// get the hashcode and regenerate it to be optimum
int userHash = key.hashCode();
int hash = getSupplementalHash(userHash);
// compute the bucket number (0-15 based on our default size)
// this always results in a number between 0-15
int bucket = getBucketNumber(hash);
Entry existingElement = table[bucket];
for (; existingElement != null; existingElement = existingElement.next) {
if (existingElement.key.equals(key)) {
System.out
.println("duplicate key value pair, replacing existing key "
+ key + ", with value " + value);
existingElement.value = value;
return;
} else {
System.out.println("Collision detected for key " + key
+ ", adding element to the existing bucket");
}
}
//
System.out.println("PUT adding key:" + key + ", value:" + value
+ " to the list");
Entry entryInOldBucket = new Entry(key, value);
entryInOldBucket.next = table[bucket];
table[bucket] = entryInOldBucket;
}
STEP4: GET Method
- line #3: defend against the poor quality hash functions defined by the user (if Employee.hashcode() is poor, this call will do a better job)
- line #7: get the bucket index
- line #14: This loop is iterated as many times as the number of collisions for every key
- line #23: If nothing is found
public Entry get(Employee key) {
// get the hashcode and regenerate it to be optimum
int hash = getSupplementalHash(key.hashCode());
// compute the bucket number (0-15 based on our default size)
// this always results in a number between 0-15
int bucket = getBucketNumber(hash);
// get the element at the above bucket if it exists
Entry existingElement = table[bucket];
// if bucket is found then traverse through the linked list and
// see if element is present
while (existingElement != null) {
System.out
.println("Traversing the list inside the bucket for the key "
+ existingElement.getKey());
if (existingElement.key.equals(key)) {
return existingElement;
}
existingElement = existingElement.next;
}
// if nothing is found then return null
return null;
}
STEP5: Employee object as the key to our custom map (TESTING)
hashCode(): Make sure the hash code falls with 0-10 so that we can reproduce collision easily.
equals(): based on id and name of the person
static class Employee {
private Integer id;
private String name;
Employee(Integer id, String name) {
this.id = id;
this.name = name;
}
@Override
public int hashCode() {
// this ensures all hashcodes are between 0 and 15
return id % 10;
}
@Override
public boolean equals(Object obj) {
Employee otherEmp = (Employee) obj;
return this.name.equals(otherEmp.name);
}
@Override
public String toString() {
return this.id + "-" + name;
}
}
STEP6: Test Code
- line #13-14: Demonstrate duplicate key replacement in hashmap
- line #30-42 and #31-35: Demonstrate collision in hashmap
- line #44-49: Demonstrate collision along with duplication in hashmap
TMHashMap tmhm = new TMHashMap();
System.out.println("============== Adding Element ===================");
Employee e1 = new Employee(100, "Niranjan");
tmhm.put(e1, "dept1");
// duplicate
System.out.println("============== Adding Duplicate =================");
Employee e1_dup = new Employee(100, "Niranjan");
tmhm.put(e1_dup, "dept12");
// the above value "dept12" should replace the old value "dept1"
Entry e = tmhm.get(e1_dup);
System.out.println("GET element - " + e.getKey() + "::" + e.getValue());
System.out.println("============== Adding Elements ==================");
Employee e2 = new Employee(102, "Sravan");
tmhm.put(e2, "dept3");
Employee e3 = new Employee(104, "Ananth");
tmhm.put(e3, "dept2");
Employee e4 = new Employee(106, "Rakesh");
tmhm.put(e4, "dept5");
Employee e5 = new Employee(108, "Shashi");
tmhm.put(e5, "dept2");
// collision with e2
System.out.println("============== Adding Collisions =================");
Employee e2_collision = new Employee(112, "Chandu");
tmhm.put(e2_collision, "dept16");
e = tmhm.get(e2_collision);
System.out.println("GET element - " + e.getKey() + "::" + e.getValue());
// collision with e3
Employee e3_collision = new Employee(114, "Santhosh");
tmhm.put(e3_collision, "dept9");
e = tmhm.get(e3_collision);
System.out.println("GET element - " + e.getKey() + "::" + e.getValue());
System.out
.println("============== Adding Duplicate in Collision ===================");
Employee e3_collision_dupe = new Employee(124, "Santhosh");
tmhm.put(e3_collision_dupe, "dept91");
e = tmhm.get(e3_collision_dupe);
System.out.println("GET element - " + e.getKey() + "::" + e.getValue());
OUTPUT: of this program
============== Adding Element =================== PUT adding key:100-Niranjan, value:dept1 to the list ============== Adding Duplicate ================= duplicate key value pair, replacing existing key 100-Niranjan, with value dept12 Traversing the list inside the bucket for the key 100-Niranjan GET element - 100-Niranjan::dept12 ============== Adding Elements ================== PUT adding key:102-Sravan, value:dept3 to the list PUT adding key:104-Ananth, value:dept2 to the list PUT adding key:106-Rakesh, value:dept5 to the list PUT adding key:108-Shashi, value:dept2 to the list ============== Adding Collisions ================= Collision detected for key 112-Chandu, adding element to the existing bucket PUT adding key:112-Chandu, value:dept16 to the list Traversing the list inside the bucket for the key 112-Chandu GET element - 112-Chandu::dept16 Collision detected for key 114-Santhosh, adding element to the existing bucket PUT adding key:114-Santhosh, value:dept9 to the list Traversing the list inside the bucket for the key 114-Santhosh GET element - 114-Santhosh::dept9 ============== Adding Duplicate in Collision =================== duplicate key value pair, replacing existing key 124-Santhosh, with value dept91 Traversing the list inside the bucket for the key 114-Santhosh GET element - 114-Santhosh::dept91
Full source code can be downloaded from here
After receiving a lot of requests/questions related to hashmap behavior on collisions and element duplication, I updated the code. I hope one can take it further from here š
coding algorithms 
Recent Comments