Hashing and Hash Tables in Java
A school with 2,000 students keeps their files in a cabinet with 26 drawers, one for each letter of the alphabet. To find Srihitha's file, nobody searches all 2,000. You go straight to drawer S and look through the few files there. The rule "first letter of the name decides the drawer" is a simple hash function, and the cabinet is a hash table. In this lesson, you will learn what hashing is, how collisions are handled, and build a small hash table from scratch in Java with chaining and resizing, then compare it with HashMap.
What Is Hashing?
Hashing in Java is the process of converting a key into a whole number, called a hash code, that is used to decide where to store the key in an array. A hash table is a data structure that is used to store key-value pairs in an array of buckets, where each key's bucket is chosen from its hash code.
- Finding the bucket takes O(1): compute the hash code, then the index.
- A good hash function spreads keys evenly across the buckets.
- Two different keys can land in the same bucket. This is called a collision, and every hash table must handle it.
From Key to Bucket
- Call the key's
hashCode(), which returns anint(it can be negative). - Turn it into a bucket index:
Math.floorMod(hash, capacity)gives a number from 0 tocapacity - 1. - Look in that bucket.
public class BucketIndex {
public static void main(String[] args) {
int capacity = 8;
for (String name : new String[] {"Navika", "Srihitha", "Advitha"}) {
int hash = name.hashCode();
System.out.println(name + " hash=" + hash
+ " bucket=" + Math.floorMod(hash, capacity));
}
}
}Navika hash=-1968692324 bucket=4
Srihitha hash=-174075838 bucket=2
Advitha hash=533330551 bucket=7Explanation: String.hashCode() always gives the same number for the same text, so "Navika" always goes to the same bucket. Math.floorMod is used instead of % because % keeps the sign, and a negative hash code would give a negative index.
Handling Collisions
| Method | How it works | Used by |
|---|---|---|
| Separate chaining | Each bucket holds a small list of all entries that land there | java.util.HashMap (lists, turning into trees when long) |
| Open addressing | If a bucket is taken, try the next one (or another, by a rule) until a free one is found | IdentityHashMap, and many hash tables in other languages |
This lesson builds a table with separate chaining, the method HashMap uses.
A Hash Table from Scratch
Let's see a small hash table with put, get, remove and automatic resizing.
public class MarksTable {
private static class Entry {
final String key;
int value;
Entry next;
Entry(String key, int value, Entry next) {
this.key = key;
this.value = value;
this.next = next;
}
}
private Entry[] buckets = new Entry[4];
private int size = 0;
private int indexFor(String key, int capacity) {
return Math.floorMod(key.hashCode(), capacity);
}
void put(String key, int value) {
int i = indexFor(key, buckets.length);
for (Entry e = buckets[i]; e != null; e = e.next) {
if (e.key.equals(key)) {
e.value = value; // same key: replace
return;
}
}
buckets[i] = new Entry(key, value, buckets[i]); // add to chain
size++;
if (size > buckets.length * 3 / 4) {
resize(); // keep chains short
}
}
Integer get(String key) {
int i = indexFor(key, buckets.length);
for (Entry e = buckets[i]; e != null; e = e.next) {
if (e.key.equals(key)) return e.value;
}
return null;
}
boolean remove(String key) {
int i = indexFor(key, buckets.length);
Entry previous = null;
for (Entry e = buckets[i]; e != null; previous = e, e = e.next) {
if (e.key.equals(key)) {
if (previous == null) buckets[i] = e.next;
else previous.next = e.next;
size--;
return true;
}
}
return false;
}
private void resize() {
Entry[] old = buckets;
buckets = new Entry[old.length * 2];
for (Entry head : old) {
for (Entry e = head; e != null; e = e.next) {
int i = indexFor(e.key, buckets.length);
buckets[i] = new Entry(e.key, e.value, buckets[i]);
}
}
System.out.println(" resized to " + buckets.length + " buckets");
}
public static void main(String[] args) {
MarksTable marks = new MarksTable();
marks.put("Navika", 91);
marks.put("Srihitha", 84);
marks.put("Advitha", 77);
marks.put("Navika Anamaneni", 95);
marks.put("Navika", 93); // update
System.out.println("Navika: " + marks.get("Navika"));
System.out.println("Advitha: " + marks.get("Advitha"));
System.out.println("Unknown: " + marks.get("Unknown"));
System.out.println("remove Srihitha: " + marks.remove("Srihitha"));
System.out.println("Srihitha: " + marks.get("Srihitha")
+ ", size " + marks.size);
}
} resized to 8 buckets
Navika: 93
Advitha: 77
Unknown: null
remove Srihitha: true
Srihitha: null, size 3Explanation:
putfinds the bucket, walks its chain, and either replaces the value for an existing key or adds a new entry at the front of the chain.- Keys are compared with
equals, not==, because two differentStringobjects can hold the same text. - When the table is more than 75 percent full (the load factor),
resizedoubles the bucket array and moves every entry to its new bucket. This keeps chains short, so lookups stay O(1) on average. removeunlinks the entry from its chain, just like removing from a linked list.
The Contract Between the Two Methods
The table only works if equal keys have equal hash codes. If two keys are equals but give different hash codes, they go to different buckets and get can't find what put stored. That is the equals and hashCode contract from "Object Equality and Hash Codes in Java". Records and String follow it automatically.
Complexity
| Operation | Average | Worst (all keys in one bucket) |
|---|---|---|
put, get, remove | O(1) | O(n) with lists, O(log n) in HashMap (trees) |
| Resize | O(n), but rare, so O(1) on average per put | |
| Space | O(n) |
Our Table vs HashMap
java.util.HashMap uses the same ideas with some refinements (see "HashMap Internal Working"):
| Feature | MarksTable | HashMap |
|---|---|---|
| Collisions | Chained lists | Lists, turned into balanced trees when a bucket holds 8 or more |
| Capacity | Doubles from 4 | Doubles from 16, always a power of two |
| Bucket index | floorMod(hash, capacity) | Mixes high bits into low bits, then hash & (capacity - 1) |
null keys | Not supported | One null key allowed |
| Order | None | None (LinkedHashMap keeps insertion order) |
Interview Corner
What happens when two keys have the same hash code?
They go to the same bucket, and equals tells them apart inside the bucket's chain.
What is the load factor?
The ratio of entries to buckets at which the table resizes. HashMap uses 0.75 by default: a good balance between memory and short chains.
Why should hash map keys be immutable?
A changed key gets a different hash code but stays in its old bucket, so it can no longer be found.
Practice
- Easy: Add a method
printBuckets()that prints each bucket index and the keys in its chain. Call it before and after the resize. - Harder: Write a class
Roll(String className, int number)with noequalsandhashCode, use it as a key in aHashMap, and show thatget(new Roll("10-A", 7))returnsnull. Then makeRolla record and run it again.
Key Takeaways
Was this tutorial helpful?