Skip to content

Instantly share code, notes, and snippets.

@aaronjwood
Last active October 13, 2017 17:27
Show Gist options
  • Save aaronjwood/73750f9283a9b6ff8cccc5af39f6dc26 to your computer and use it in GitHub Desktop.
Save aaronjwood/73750f9283a9b6ff8cccc5af39f6dc26 to your computer and use it in GitHub Desktop.
Hash map using an ArrayList
import java.util.ArrayList;
class HM<K, V> {
private static class HashNode<K, V> {
private K key;
private V value;
private HashNode<K, V> next;
HashNode(K key, V value) {
this.key = key;
this.value = value;
}
}
private ArrayList<HashNode<K, V>> buckets = new ArrayList<>();
private int size;
private int numBuckets;
public HM(int size) {
numBuckets = size;
for (int i = 0; i < size; i++) {
buckets.add(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.get(idx);
while (head != null) {
if (head.key.equals(key)) {
head.value = value;
return;
}
head = head.next;
}
head = buckets.get(idx);
HashNode<K, V> newNode = new HashNode<>(key, value);
newNode.next = head;
buckets.set(idx, newNode);
size++;
}
public V get(K key) {
int idx = getHashIndex(key);
HashNode<K, V> head = buckets.get(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.get(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;
} else {
buckets.set(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