A hash table uses a key's hash to help locate a stored value. Java's HashMap manages buckets, collisions, resizing, and key comparisons for you, but you still must supply keys with a correct equals and hashCode contract. Hashing is not encryption and a hash is not a guaranteed unique identifier. This lesson shows a map lookup, deliberately colliding keys, and immutable record keys so you can understand both the data structure's expected performance and its correctness requirements.
Separate hashing from equality
hashCode produces an integer used to narrow the search to a bucket. equals determines whether a candidate key is actually the same logical key. Equal objects must have equal hash codes. Unequal objects may share a hash code, which is a collision and must be handled by the map. A hash alone cannot prove equality. Overriding equals without a compatible hashCode can make a logically equal lookup fail to reach the stored entry.
Understand collisions and buckets
A collision means multiple keys map to the same bucket or hash result. The implementation compares candidate keys to distinguish them. HashMap handles collisions internally, so applications should not invent unique hashes merely to avoid every collision. Poor distribution can increase the work needed for operations. Modern HashMap includes strategies for heavily populated buckets under particular conditions, but its contract should not be described as a universal fixed-time guarantee for every possible key set.
Use expected complexity carefully
HashMap offers expected constant-time basic operations when hashes distribute entries adequately. Resizing and collision behavior affect individual operations and amortized analysis. The load factor relates stored entries to capacity and influences when resizing occurs. Pre-sizing can reduce resizing when an approximate entry count is known, but oversized maps consume extra storage. Choose capacity according to a real workload rather than treating the largest possible table as automatically faster.
Keep key identity stable
Do not change fields participating in equals or hashCode while an object is used as a key. The entry remains stored according to its earlier hash placement, so a later lookup using the mutated key can fail. Immutable records are convenient keys when their components provide stable value semantics. A record containing mutable components still needs care. If a key must change, remove the old entry before the identity-changing mutation and insert it under the new key deliberately.
Distinguish absence from a stored null
HashMap permits null values, so get returning null can mean either no entry or an entry whose value is null. containsKey distinguishes those cases. Some maps, such as ConcurrentHashMap, forbid null and have different contracts. Decide whether null belongs in your application's value model instead of relying on ambiguous interpretation. getOrDefault returns the default for an absent key but does not replace an explicitly mapped null value.
Ordering and security are separate concerns
HashMap does not guarantee iteration order. LinkedHashMap preserves a documented encounter order, and TreeMap orders keys through comparison rather than hashing. Use the right map when output order matters. hashCode is designed for data structure placement, not secure password storage or cryptographic verification. Never store a password's ordinary hashCode and call it protected. Security-sensitive hashing requires purpose-built algorithms and a separate security design.
Practice tasks and checks
Add a third colliding Key and verify all three values remain retrievable. Then replace the deliberately constant hash with the record's generated implementation and explain why correctness stays the same while distribution improves. For CompositeKeys, add records differing only in room or only in number and test their independent entries. Create a HashMap entry with a null value and compare get, containsKey, and getOrDefault for that key versus a missing key. Finally, write a short explanation of why hashCode is neither a unique database identifier nor a password-protection algorithm. The exercise should separate bucket placement, value equality, absence policy, iteration order, and security rather than treating the word hash as one universal operation.
Java Summary
- Equal keys must have equal hashes, but collisions are allowed.
- Keep key equality and hash identity stable after insertion.
- Hashing for map placement is not encryption or password protection.
- Continue with HashMap foundations when these examples are clear.
Java Examples
Each example shows the code, the output it produces and what each part does.
Store and retrieve values by key
Save this program as StockLookup.java. Compile it with javac StockLookup.java and run it with java StockLookup.
Expected output:
put associates lamp with seven and map with three. get retrieves the value for an equal lamp key. rope has no entry, so getOrDefault supplies zero under this application's absence policy. The output selects individual keys and therefore does not depend on HashMap iteration order. A real inventory may distinguish unknown product from zero stock, in which case a zero fallback would hide useful information.
import java.util.HashMap;
import java.util.Map;
public class StockLookup {
public static void main(String[] args) {
Map<String, Integer> stock = new HashMap<>();
stock.put("lamp", 7);
stock.put("map", 3);
System.out.println(stock.get("lamp"));
System.out.println(stock.getOrDefault("rope", 0));
}
}7
0Keep colliding keys distinct
Save this program as CollisionKeys.java. Compile it with javac CollisionKeys.java and run it with java CollisionKeys.
Expected output:
The record's generated equals compares its text component, while the overridden hashCode deliberately sends every key to the same hash value. Equal keys still share that value, satisfying the necessary contract, but different texts collide. HashMap distinguishes east and west through equality, stores both entries, and retrieves each correctly. This intentionally poor hash demonstrates collision correctness, not a recommended key implementation for performance.
import java.util.HashMap;
import java.util.Map;
public class CollisionKeys {
record Key(String text) {
@Override public int hashCode() { return 1; }
}
public static void main(String[] args) {
Map<Key, String> labels = new HashMap<>();
labels.put(new Key("east"), "Blue");
labels.put(new Key("west"), "Gold");
System.out.println(labels.get(new Key("east")));
System.out.println(labels.get(new Key("west")));
System.out.println(labels.size());
}
}Blue
Gold
2Use an immutable composite key
Save this program as CompositeKeys.java. Compile it with javac CompositeKeys.java and run it with java CompositeKeys.
Expected output:
Two separately constructed Shelf records with matching room and number compare equal and have compatible generated hashes, so the lookup finds twelve. Changing the number to five creates a different logical key and containsKey returns false. String and int components are stable for this use. No identity comparison between record instances is needed; value equality supplies the key contract.
import java.util.HashMap;
import java.util.Map;
public class CompositeKeys {
record Shelf(String room, int number) {}
public static void main(String[] args) {
Map<Shelf, Integer> capacity = new HashMap<>();
capacity.put(new Shelf("Reading", 4), 12);
System.out.println(capacity.get(new Shelf("Reading", 4)));
System.out.println(capacity.containsKey(new Shelf("Reading", 5)));
}
}12
falseJava FAQ
Can two keys have the same hash code?
Yes. Collisions are permitted. A map must use equality to distinguish unequal keys sharing a hash, while equal keys are required to produce compatible hash codes.
Why should I avoid mutable map keys?
Changing the fields used for hashCode or equals after insertion can make the key's stored bucket placement disagree with later lookups. Stable value keys avoid that mismatch.
What is a load factor?
The ratio of entries to buckets at which a hash table grows. HashMap uses 0.75 by default: with 16 buckets it resizes after 12 entries, doubling the bucket array and redistributing the entries. A lower load factor reduces collisions but uses more memory.
How does HashMap cope with many collisions in one bucket?
Since Java 8, when a bucket's chain grows long and the table is large enough, HashMap turns that chain into a small balanced tree. Lookups in that bucket then take logarithmic rather than linear time, which limits the damage from poor hash codes, especially when the keys are Comparable.
How do I write a good hashCode method?
Combine the same fields that equals compares, for example with Objects.hash(name, id), so equal objects always produce equal hash codes. Records and IDE generators do this for you. Don't include fields that change while the object is used as a key.
Java Exercises
Answer each one and check it instantly. If you get stuck, open the hint before the answer.
What must be true for equal keys?
Why do CollisionKeys entries remain distinct?
Java Quiz
2 questions to check what you learned.
Which map gives insertion-oriented encounter order?
- LinkedHashMap
- HashMap by universal guarantee
- ConcurrentHashMap sorted by key
What distinguishes a missing HashMap entry from a stored null?
- containsKey
- hashCode alone
- The filename