Implement a HashMap in Java
Problem
A hash map stores key-value pairs in an array of buckets; a key's hash code picks its bucket, so lookups jump straight to the right place instead of searching every entry.
Implement a generic map that supports put, get and remove, handles collisions, and grows its bucket array when it gets too full.
Java Program
public class SimpleHashMap {
static class MyHashMap<K, V> {
private static class Entry<K, V> {
final K key;
V value;
Entry<K, V> next; // entries in the same bucket form a linked list
Entry(K key, V value, Entry<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
}
private Entry<K, V>[] buckets = newArray(4);
private int size;
@SuppressWarnings("unchecked")
private static <K, V> Entry<K, V>[] newArray(int n) {
return (Entry<K, V>[]) new Entry[n];
}
private int indexFor(Object key, int length) {
return (key.hashCode() & 0x7fffffff) % length; // clear the sign bit, then pick a bucket
}
void put(K key, V value) {
int i = indexFor(key, buckets.length);
for (Entry<K, V> e = buckets[i]; e != null; e = e.next) {
if (e.key.equals(key)) {
e.value = value; // existing key: replace the value
return;
}
}
buckets[i] = new Entry<>(key, value, buckets[i]); // new key: add to the front of the chain
size++;
if (size > buckets.length * 3 / 4) resize(); // keep the load factor below 0.75
}
V get(K key) {
for (Entry<K, V> e = buckets[indexFor(key, buckets.length)]; e != null; e = e.next) {
if (e.key.equals(key)) return e.value;
}
return null;
}
boolean remove(K key) {
int i = indexFor(key, buckets.length);
Entry<K, V> prev = null;
for (Entry<K, V> e = buckets[i]; e != null; prev = e, e = e.next) {
if (e.key.equals(key)) {
if (prev == null) buckets[i] = e.next;
else prev.next = e.next;
size--;
return true;
}
}
return false;
}
private void resize() {
Entry<K, V>[] old = buckets;
buckets = newArray(old.length * 2);
for (Entry<K, V> head : old) {
for (Entry<K, V> e = head; e != null; e = e.next) {
int i = indexFor(e.key, buckets.length); // positions change with the new length
buckets[i] = new Entry<>(e.key, e.value, buckets[i]);
}
}
}
int size() { return size; }
int capacity() { return buckets.length; }
}
public static void main(String[] args) {
MyHashMap<String, Integer> stock = new MyHashMap<>();
stock.put("apple", 40);
stock.put("banana", 25);
stock.put("cherry", 60);
System.out.println("Size " + stock.size() + ", buckets " + stock.capacity());
stock.put("date", 15); // pushes the load factor past 0.75
System.out.println("Size " + stock.size() + ", buckets " + stock.capacity() + " (resized)");
stock.put("apple", 35); // update, not a new entry
System.out.println("apple = " + stock.get("apple") + ", size still " + stock.size());
System.out.println("remove banana: " + stock.remove("banana") + ", get banana = " + stock.get("banana"));
System.out.println("get kiwi = " + stock.get("kiwi"));
}
}Output
Core Logic
The key's hash code selects a bucket, each bucket holds a small linked list of entries, and the array doubles when the average chain would get too long.
- 1
indexForclears the sign bit ofhashCode()and takes it modulo the array length to pick a bucket. - 2
putscans the bucket's chain withequals: a matching key gets its value replaced, otherwise a new entry is added to the front. - 3When
sizeexceeds 75% of the bucket count,resizedoubles the array and re-inserts every entry, since bucket positions depend on the length. - 4
getandremovelook only inside the one bucket the key maps to.
apple afterwards leaves the size at 4.Key Point: This is why keys must implement hashCode and equals consistently — hashCode finds the bucket and equals finds the entry inside it.
Why: Resizing keeps chains short, so each operation inspects only a few entries on average; storage grows with the number of entries.
Key Concepts
Approach 2: Open Addressing (Linear Probing)
public class SimpleHashMapOpenAddressing {
private final String[] keys = new String[8];
private final int[] values = new int[8];
private int slot(String key) {
int i = (key.hashCode() & 0x7fffffff) % keys.length;
while (keys[i] != null && !keys[i].equals(key)) {
i = (i + 1) % keys.length; // linear probing: try the next slot
}
return i;
}
void put(String key, int value) {
int i = slot(key);
keys[i] = key;
values[i] = value;
}
Integer get(String key) {
int i = slot(key);
return keys[i] == null ? null : values[i];
}
public static void main(String[] args) {
SimpleHashMapOpenAddressing map = new SimpleHashMapOpenAddressing();
map.put("red", 1);
map.put("green", 2);
map.put("blue", 3);
map.put("green", 20);
System.out.println("red = " + map.get("red"));
System.out.println("green = " + map.get("green"));
System.out.println("blue = " + map.get("blue"));
System.out.println("pink = " + map.get("pink"));
}
}
Output
Core Logic
Instead of chaining, open addressing stores every entry directly in the array; on a collision it probes the following slots until it finds the key or an empty one.
- 1Keys and values live in two parallel arrays of the same size.
- 2
slotstarts at the hashed index and steps forward, wrapping around, until it finds the key or an empty slot. - 3
putwrites into that slot;getreturnsnullif the slot is empty.
green a second time finds its existing slot and overwrites 2 with 20.Key Point: Open addressing avoids allocating entry objects, but deletion is tricky — simply clearing a slot breaks later probes, so real implementations use "tombstone" markers.
Why: With a low load factor, probes are short; both arrays are sized to the table capacity.
Key Concepts
Interview Questions
What happens when two keys have the same hash code?
They land in the same bucket and are stored in a chain. equals then tells them apart during lookups.
How does Java's HashMap handle very long chains?
Since Java 8, a bucket with many entries is converted into a balanced tree, so worst-case lookups in that bucket are O(log n) instead of O(n).