Stage 4: HashMap internals, lesson 1 of 13

HashMap internals 1: What is hashing?

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

A hash function turns any key into a fixed-size number, its hash code. The same key always gives the same number, so instead of *searching* for a key you can *calculate* where it must be.

  • Every Java object has hashCode(), which returns an int (about 4.3 billion possible values).
  • String.hashCode() is calculated from the characters: s[0]·31^(n−1) + s[1]·31^(n−2) + … + s[n−1], letting the int overflow.
  • Different keys can share a hash code. There are endless possible strings but only 2^32 int values, so this is unavoidable. It's called a collision (part 5).
  • A good hash function spreads keys evenly, which is what makes lookups O(1) on average: calculate, then jump. In a plain list you'd check up to every element (O(n)).

Try it in the lab below: type a key and watch its hash code being worked out.

HashMap lab

Example

Java
System.out.println("java".hashCode());              // 3254818
System.out.println("Java".hashCode());              // 2301506   (one letter changed: a very different number)
System.out.println("Aa".hashCode());                // 2112
System.out.println("BB".hashCode());                // 2112      different strings, same hash code!
System.out.println(Integer.valueOf(42).hashCode()); // 42        an Integer's hash is its value

Common mistake

Assuming that equal hash codes mean equal objects. "Aa" and "BB" prove they don't.

Under the hood

String caches its hash code in a field the first time it's calculated; that's safe because strings are immutable. 31 is used because it's an odd prime and 31 * h can be computed as (h << 5) - h. Hash codes aren't unique IDs, and Object's default hash code can differ between runs, so never store them in a database.

Check yourself

"Aa".hashCode() is 2112. What is "BB".hashCode()?

How this connects

Part of HashMap internals, part by part.

Was this lesson helpful?

Finished reading? Mark it complete to track your progress.