Skip to content

Instantly share code, notes, and snippets.

@aaronjwood
Created October 13, 2017 17:26
Show Gist options
  • Save aaronjwood/159728ad9db798cfd3bd1b64c2211026 to your computer and use it in GitHub Desktop.
Save aaronjwood/159728ad9db798cfd3bd1b64c2211026 to your computer and use it in GitHub Desktop.
Hash map using an array
class HM<K, V> {
private static class HashNode<K, V> {
private HashNode<K, V> next;
private K key;
private V value;
HashNode(K key, V value) {
this.key = key;
this.value = value;
}
}
private int size;
private int numBuckets;
private HashNode<K, V>[] buckets;
public HM(int size) {
numBuckets = size;
buckets = new HashNode[size];
for (int i = 0; i < size; i++) {
buckets[i] = null;
}
}
private int getHashIndex(K key) {
return key.hashCode() % numBuckets;
}
public void put(K key, V value) {
int idx = getHashIndex(key);
HashNode<K, V> head = buckets[idx];
while (head != null) {
if (head.key.equals(key)) {
head.value = value;
return;
}
head = head.next;
}
head = buckets[idx];
HashNode<K, V> newNode = new HashNode<>(key, value);
newNode.next = head;
buckets[idx] = newNode;
size++;
}
public V get(K key) {
int idx = getHashIndex(key);
HashNode<K, V> head = buckets[idx];
while (head != null) {
if (head.key.equals(key)) {
return head.value;
}
head = head.next;
}
return null;
}
public V remove(K key) {
int idx = getHashIndex(key);
HashNode<K, V> head = buckets[idx];
HashNode<K, V> prev = null;
while (head != null && !head.key.equals(key)) {
prev = head;
head = head.next;
}
if (head == null) {
return null;
}
V value = head.value;
if (prev != null) {
prev.next = head.next;
return value;
} else {
buckets[idx] = head.next;
}
size--;
return value;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment