Below is an implementation heavily based on climberig's implementation on Leetcode for LeetCode 706. Design HashMap. Just to preface, I am doing this in preparation for an exam.
The one below is dynamically sized, so it should increase the size of ListNode[] whenever the condition (keyCount > length * 0.90) has been met.
I was initially going to have that condition be (loadFactor > 0.75), but for whatever reason, the runtime seems to increase heavily (at least on LeetCode).
My main concern would be whether the hashing and collisions work accurately and spread evenly.
Any and all advice to improve the code below would be helpful.
import java.lang.Math;
class MyHashMap {
int length = 10;
int keyCount = 0;
int loadFactor = keyCount / length;
ListNode[] nodes = new ListNode[length];
public void put(int key, int value) {
int hashKey = hashFunction(key);
if (nodes[hashKey] == null)
nodes[hashKey] = new ListNode(-1, -1);
ListNode prev = find(nodes[hashKey], key);
if (prev.next == null) {
keyCount++;
prev.next = new ListNode(key, value);
}
else prev.next.val = value;
rehash();
}
public int get(int key) {
int hashKey = hashFunction(key);
if (nodes[hashKey] == null)
return -1;
ListNode node = find(nodes[hashKey], key);
return node.next == null ? -1 : node.next.val;
}
public void remove(int key) {
int hashKey = hashFunction(key);
if (nodes[hashKey] == null) return;
ListNode prev = find(nodes[hashKey], key);
// Key did not exist in the first place
if (prev.next == null) return;
// Removes the key by setting the previous node to the next node from the key
prev.next = prev.next.next;
}
// Hash Function
int hashFunction(int key) { return Integer.hashCode(key) % length;}
ListNode find(ListNode bucket, int key) {
ListNode node = bucket;
ListNode prev = null;
while (node != null && node.key != key) {
prev = node;
node = node.next;
}
return prev;
}
public void rehash() {
if (keyCount > length * 0.90) {
int oldLength = length;
length = length * 2;
ListNode[] newNodes = new ListNode[length];
for (int i = 0; i < oldLength; i++) {
if (nodes[i] == null) {
continue;
}
ListNode next = nodes[i].next;
while (next != null) {
int key = next.key;
int value = next.val;
int hashKey = hashFunction(key);
if (newNodes[hashKey] == null)
newNodes[hashKey] = new ListNode(-1, -1);
ListNode prev = find(newNodes[hashKey], key);
if (prev.next == null) {
prev.next = new ListNode(key, value);
}
else {
prev.next.val = value;
}
next = next.next;
}
}
nodes = newNodes;
}
printHash();
System.out.println("---------------");
}
public void printHash() {
for (int i = 0; i < length; i++) {
if (nodes[i] == null) {
System.out.println("Bucket Not Found");
continue;
}
ListNode next = nodes[i].next;
while (next != null) {
System.out.print("Bucket Found | Key - " + next.key + " Value - " + next.val + " | ");
next = next.next;
}
System.out.println();
}
}
// ListNode to handle collisions
class ListNode {
int key, val;
ListNode next;
ListNode(int key, int val) {
this.key = key;
this.val = val;
}
}
public static void main(String[] args) {
MyHashMap ht = new MyHashMap();
for (int i = 0; i < 100; i++) {
int randomNumber = (int) (Math.random() * 100);
ht.put(randomNumber, i);
}
ht.printHash();
}
}
