Wie Hashing funktioniert
Hash-Funktionen, Buckets, Kollisionen und warum HashMap-Operationen im Schnitt O(1), im schlimmsten Fall aber O(n) sind.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
The hash map is the single most useful data structure in interviews - it turns "search" from O(n) into O(1) and unlocks a huge class of one-pass solutions. But to use it well (and answer the follow-up questions), you need to understand what's happening under the hood, including why it's only O(1) on average.
Buckets and hash functions
A hash map stores key-value pairs in an array of buckets. To find where a key goes, it runs the key through a hash function that produces an integer, then maps that integer to a bucket index. A good hash function spreads keys evenly across the buckets, so most buckets hold just one entry - giving O(1) lookup, insert, and delete.
// conceptually, where does key k live?
int hash = key.hashCode(); // the key produces an int
int bucket = hash & (capacity - 1); // map it into the bucket array
// then check that bucket for the keyCollisions and the worst case
Two different keys can hash to the same bucket - a collision. Java handles this by chaining entries in the same bucket (as a small list, upgrading to a balanced tree if a bucket gets large). With a good hash and a reasonable load, collisions are rare and operations stay O(1) average.
But if many keys collide into one bucket, that bucket degrades toward a linear scan - the worst case is O(n). This is why interviewers ask "what's the worst-case complexity of a HashMap lookup?" The honest answer: O(1) average, O(n) worst case (mitigated in modern Java by treeifying big buckets to O(log n)).
The hashCode / equals contract
For your own classes to work as map keys, hashCode() and equals() must agree: equal objects must
return equal hash codes. Violate this and the map looks in the wrong bucket and can't find entries it
contains. Records generate both correctly, which is one reason they make excellent keys.
// a record is a perfect map key: correct equals() and hashCode() for free
record Point(int x, int y) {}
Map<Point, String> grid = new HashMap<>();
grid.put(new Point(1, 2), "origin-ish");
grid.get(new Point(1, 2)); // finds it: equal points hash equallyMutable keys are a trap
If you use a mutable object as a key and then change a field that affects its hashCode, the map can no longer find it - it's in the bucket for its old hash. Use immutable keys (Strings, records, boxed primitives). This is a favorite 'why can't the map find my entry?' interview gotcha.
A coat check hashes your ticket number to a hook and hangs your coat there - retrieval is instant because the number points straight to the hook, no searching the whole rack. A collision is two tickets assigned the same hook; the attendant hangs both and, on retrieval, checks the couple of coats on that hook. Rare collisions barely slow things down (still ~O(1)), but if a bad numbering scheme sent everyone to one hook, retrieval becomes searching the whole rack again (O(n)). A good hash function is a good numbering scheme: it keeps one coat per hook.
An interviewer asks: "You said HashMap.get is O(1), but I've heard it can be O(n) - which is it?" Explain when each holds, what causes the worst case, and how modern Java softens it.
What is the time complexity of HashMap.get, precisely?
Key takeaways
- A hash map stores entries in buckets chosen by a hash function; a good hash keeps ~1 entry per bucket for O(1) operations.
- Collisions (different keys, same bucket) are chained; heavy collisions degrade a bucket toward O(n), capped at O(log n) by treeifying in modern Java.
- So HashMap.get is O(1) average, O(n)/O(log n) worst case - state both in interviews.
- Custom key classes must obey the equals/hashCode contract: equal objects need equal hash codes.
- Use immutable keys (String, record, boxed primitives); mutating a key's hash-affecting field hides it from the map.