How Java's HashSet Maintains Uniqueness
Java’s java.util.HashSet gives you a collection where every element appears at most once. Uniqueness sounds like one idea, but in a hash-based set it is actually two cooperating mechanisms: a hash code that decides where an element lives, and equals() that decides whether an arriving object is the same as one already there. This post walks three layers: the visible duplicate-rejection behavior, what’s actually inside — a HashSet is a HashMap in disguise — and the failure mode that happens when a custom class breaks the contract between equals() and hashCode().
Rejecting duplicates
Set’s contract is that adding an element that is already present changes nothing, and add reports this with its return value: it returns true when the set did not already contain the element, false otherwise. A small program adds five strings, two of them twice, and prints each result:
import java.util.HashSet;
import java.util.Set;
public class HashSetBasics {
public static void main(String[] args) {
Set<String> tags = new HashSet<>();
// Each add prints whether the element was new.
System.out.println("add(\"java\") -> " + tags.add("java"));
System.out.println("add(\"rust\") -> " + tags.add("rust"));
System.out.println("add(\"java\") -> " + tags.add("java")); // duplicate
System.out.println("add(\"go\") -> " + tags.add("go"));
System.out.println("add(\"rust\") -> " + tags.add("rust")); // duplicate
System.out.println();
System.out.println("size() = " + tags.size());
System.out.println("contains(\"java\") = " + tags.contains("java"));
System.out.println("contains(\"python\") = " + tags.contains("python"));
System.out.println("elements: " + tags);
}
}Compiled and run with JDK 21:
add("java") -> true
add("rust") -> true
add("java") -> false
add("go") -> true
add("rust") -> false
size() = 3
contains("java") = true
contains("python") = false
elements: [rust, java, go]The two repeated add calls returned false, so size() settled at 3 instead of 5 — duplicates were recognized and dropped. Also note the iteration order: [rust, java, go] is not the insertion order java, rust, go. A hash-based set organizes elements by bucket, not by arrival, so it never promises the order you added things in; if you need insertion order, that’s what LinkedHashSet is for.
Inside the set: a HashMap with a table of buckets
The first program was black-box: add returned false for duplicates, and that was all we could see. The rest of the story is in the implementation. The JDK 21 HashSet Javadoc says the class is “backed by a hash table (actually a HashMap instance)”, and in the JDK 21 source HashSet.add is literally map.put(e, PRESENT) == null, where PRESENT is a single static dummy object shared by every element. In other words, the set’s elements are the map’s keys, and everything that follows is HashMap’s. From openjdk’s java/util/HashMap.java:
HashMap.hash(key)spreads the key’s hash:(h = key.hashCode()) ^ (h >>> 16)— the upper 16 bits are XORed into the lower ones.- The bucket index is
(table.length - 1) & hash; table length is a power of two, so that’s just taking the low bits of the hash. putVallooks attab[index]. If it’s empty, the entry goes there. If it’s occupied, it walks the chain of entries, looking for one matchingp.hash == hash && (k == key || key.equals(k))— i.e. an equal key. An equal key makesputreturn the old value (which is whyaddreportsfalse); a non-equal key is appended to the end of the chain (addreportstrue). (If a bucket’s chain grows very long, its entries are reorganized into tree nodes.)
This program mirrors that arithmetic verbatim — capacity 16, DEFAULT_INITIAL_CAPACITY = 1 << 4 — then does the same adds in a real HashSet and prints the bucket each element iterates in:
import java.util.HashSet;
import java.util.Set;
public class HashSetInternals {
// Mirrors JDK 21's java/util/HashMap.java:
// hash(key) = (h = key.hashCode()) ^ (h >>> 16)
// bucket = (table.length - 1) & hash
// and DEFAULT_INITIAL_CAPACITY = 1 << 4, i.e. 16.
static final int CAPACITY = 16;
static int hash(String key) {
int h = key.hashCode();
return h ^ (h >>> 16);
}
static int bucket(String key) {
return (CAPACITY - 1) & hash(key);
}
public static void main(String[] args) {
String[] keys = {"java", "rust", "go", "c", "haskell", "lisp"};
System.out.println("== the arithmetic HashMap.put performs on each key ==");
System.out.printf("%-8s %-10s %-10s %s%n", "key", "hashCode", "hash()", "bucket");
for (String k : keys) {
System.out.printf("%-8s %-10d %-10d %d%n", k, k.hashCode(), hash(k), bucket(k));
}
System.out.println();
Set<String> set = new HashSet<>();
System.out.println("== adding them to a HashSet (\"java\" and \"c\" share bucket 3) ==");
for (String k : keys) {
System.out.printf("add(\"%s\") -> %s%n", k, set.add(k));
}
System.out.println("add(\"java\") -> " + set.add("java") + " // true duplicate");
System.out.println("size = " + set.size());
System.out.println("contains(\"c\") = " + set.contains("c"));
System.out.println("contains(\"lisp\") = " + set.contains("lisp"));
System.out.println();
System.out.println("== iterating, with each element's bucket index ==");
for (String e : set) {
System.out.printf("%-8s bucket %d%n", e, bucket(e));
}
System.out.println();
System.out.println("== removal: equals() picks the right entry inside a shared bucket ==");
System.out.println("remove(\"c\") -> " + set.remove("c")
+ ", contains(\"java\") = " + set.contains("java"));
System.out.println("remove(\"java\") -> " + set.remove("java") + ", size = " + set.size());
}
}Compiled and run with JDK 21:
== the arithmetic HashMap.put performs on each key ==
key hashCode hash() bucket
java 3254818 3254803 3
rust 3512292 3512273 1
go 3304 3304 8
c 99 99 3
haskell 697623028 697616480 0
lisp 3322010 3322024 8
== adding them to a HashSet ("java" and "c" share bucket 3) ==
add("java") -> true
add("rust") -> true
add("go") -> true
add("c") -> true
add("haskell") -> true
add("lisp") -> true
add("java") -> false // true duplicate
size = 6
contains("c") = true
contains("lisp") = true
== iterating, with each element's bucket index ==
haskell bucket 0
rust bucket 1
java bucket 3
c bucket 3
go bucket 8
lisp bucket 8
== removal: equals() picks the right entry inside a shared bucket ==
remove("c") -> true, contains("java") = true
remove("java") -> true, size = 4Three things stand out. First, distinct keys collide: java (hash 3254803) and c (hash 99) both land in bucket 3, and go (3304) and lisp (3322010, 3322024 after the XOR) both land in bucket 8 — yet all six are kept, because putVal only bails out when the stored key is equal. And the hash() column shows why the XOR exists at all: go’s 3304 is under 2^16, so its upper half is zero and it passes through unchanged, while lisp’s high bits mix down into the low bits that pick the bucket. A collision doesn’t break uniqueness; it just forces the chain lookup.
Second, the true duplicate is still caught: the final add("java") returned false and the size stayed at 6 — the same behavior as the first program, now with a mechanical explanation behind it.
Third, look at the iteration: haskell, rust, java, c, go, lisp with bucket indices 0, 1, 3, 3, 8, 8 — non-decreasing, with the colliding neighbors sitting side by side. That’s because HashMap’s iterator advances a running index over the table array — do {} while (index < t.length && (next = t[index++]) == null) in nextNode() — so iteration walks buckets in order. That’s the concrete reason the first program printed [rust, java, go] instead of insertion order: the set iterates the table, and each element’s position is set by the low bits of its hash, not by when it arrived.
The last block shows equals() doing its job inside a shared bucket: remove("c") returned true while java, the bucket’s other occupant, stayed, and remove("java") then brought the set down to 4. The hash routes to the bucket; equals() makes the pick within it.
The equals/hashCode contract
String’s duplicate detection was easy because String already implements both equals() and hashCode(). For your own classes, uniqueness in a HashSet is only as good as both of those methods. The requirement is the one stated in the Object Javadoc: if two objects are equal according to equals(), they must have the same hashCode(). A HashSet (which the Javadoc says is backed by a HashMap) uses the hash code to find the bucket to look at, and then equals() to confirm it is the same element. Break the first half and the second never gets a chance to run.
This program defines two classes with identical equals() logic — one also provides hashCode(), the other doesn’t — and adds a second, content-equal object of each kind:
import java.util.HashSet;
public class HashSetContract {
// Overrides equals() but NOT hashCode().
static class Name {
final String value;
Name(String value) { this.value = value; }
@Override
public boolean equals(Object o) {
return o instanceof Name && ((Name) o).value.equals(value);
}
// inherits Object.hashCode() -> identity-based
}
// Overrides both.
static class Name2 {
final String value;
Name2(String value) { this.value = value; }
@Override
public boolean equals(Object o) {
return o instanceof Name2 && ((Name2) o).value.equals(value);
}
@Override
public int hashCode() {
return value.hashCode();
}
}
public static void main(String[] args) {
HashSet<Name> broken = new HashSet<>();
broken.add(new Name("ada"));
boolean dup = broken.add(new Name("ada")); // equal content, new object
System.out.println("equals only: second add returned " + dup
+ ", set size = " + broken.size());
System.out.println("equals only: set contains new Name(\"ada\")? " + broken.contains(new Name("ada")));
System.out.println();
HashSet<Name2> working = new HashSet<>();
working.add(new Name2("ada"));
boolean dup2 = working.add(new Name2("ada"));
System.out.println("equals+hash: second add returned " + dup2
+ ", set size = " + working.size());
System.out.println("equals+hash: set contains new Name2(\"ada\")? " + working.contains(new Name2("ada")));
}
}The output:
equals only: second add returned true, set size = 2
equals only: set contains new Name("ada")? false
equals+hash: second add returned false, set size = 1
equals+hash: set contains new Name2("ada")? trueName says two objects are equal when their value fields match — but it inherits Object’s hashCode(), which is identity-based (per the Object Javadoc, it is derived from the object’s internal address, so two different instances get different values). The set asked for the hash first, got a hash matching neither stored entry, and never consulted equals(). The “duplicate” slipped in: add returned true, the set grew to 2, and even contains(new Name("ada")) says false, because a brand-new object again has its own identity hash. The equals() override was silently doing nothing for set membership.
Name2 behaves the way you’d expect: the second, content-equal add returns false, the size stays at 1, and contains finds the stored element — because the hash code routes the lookup to the right bucket where equals() can confirm the match.
Takeaway
The three runs show the same mechanism from three angles. The first showed the visible behavior: a HashSet reports a duplicate with add returning false and keeps only one copy. The internals run showed what the set actually is — a HashMap whose keys are the elements and whose value is a shared dummy, where hashCode() (spread with the top-16-bits XOR) picks a bucket and equals() is consulted inside it — and why iteration follows the table rather than insertion order. The contract run showed the failure mode when that two-step lookup is broken: a class that overrides equals() but not hashCode() accepts duplicates it should reject, and the broken version compiles fine and fails quietly. If you put a custom class in a HashSet (or HashMap), these runs are a good argument for overriding hashCode() right alongside equals().