Stage 4: HashMap internals, lesson 4 of 13

HashMap internals 4: How get() works

Intermediate3 min readall versions
Explain it forThe essentials plus production detail and pitfalls.

get(key) repeats the first steps of put:

  1. Hash the key the same way: spread(key.hashCode()).
  2. Find the bucket: hash & (n − 1).
  3. Check the first node: same hash and equal key? Return its value. This is the common case.
  4. Otherwise walk the rest of the bucket (a list, or a tree search for big buckets), comparing the hash first and then equals().
  5. Nothing matched: return null.

Speed: on average a bucket holds one entry or none, so get is O(1). A crowded bucket costs O(n) as a list, or O(log n) once it's a tree (Java 8+).

The null problem: get returns null both when the key is missing and when the key is mapped to null. Use containsKey or getOrDefault when that difference matters.

HashMap lab

Example

Java
Map<String, Integer> stock = new HashMap<>(Map.of("pen", 12, "book", 3));

stock.get("pen");                     // 12
stock.get("pencil");                  // null   missing
stock.getOrDefault("pencil", 0);      // 0

stock.put("eraser", null);
stock.get("eraser");                  // null   present, but mapped to null!
stock.containsKey("eraser");          // true   so this is how you tell them apart

Common mistake

Using get(key) == null to mean "the key isn't there". It's also null when the key maps to null.

Under the hood

get recalculates the hash of the key you pass in. If that differs from the hash stored when the entry was put (because the key object changed, or hashCode() is inconsistent), the lookup goes to the wrong bucket or fails the hash check, and the entry becomes unreachable. Part 13 shows this happening.

Check yourself

map.put("x", null); what does map.containsKey("x") return?

How this connects

Part of HashMap internals, part by part.

Was this lesson helpful?

Finished reading? Mark it complete to track your progress.