The labs on this site need JavaScript to run. The same content is written out below.

Learn › Java › Collections

Inside HashMap

Where does a HashMap put a key, and how does it find it?

A HashMap uses the hashCode of a key to decide the bucket number and puts the key there. When the bucket numbers decided from the hash codes collide, the keys are chained one after another in a single bucket, and when the entries become many, the number of buckets is doubled.

Checked against real execution · Checked against the internals of a real HashMap on JDK 21 over 360 steps

Concepts in this lab

Hash table and HashMap

This data structure decides the storage location (bucket) of a key from the value that a hash function produces for that key. The location can be computed directly from the key alone, so lookup, insertion, and removal are O(1) on average. Java's HashMap has this structure; it does not guarantee order and is not thread-safe.

Hash collision

This happens when different keys are assigned to the same bucket. It cannot be avoided because the number of buckets is finite. Java's HashMap links the entries of the same bucket in a linked list, and when too many entries gather in one bucket, it converts the list to a red-black tree to shorten the search time. More collisions mean lower performance, so hashCode must spread values evenly.

Load factor and resizing

The load factor is the ratio that decides how full a hash table can get before its size is increased. The default for HashMap is 0.75: when the number of stored entries exceeds 75% of the number of buckets, the number of buckets is doubled and the entries are placed again (resizing). Resizing is expensive, so if you know how much you will add, it is better to set the initial capacity in advance.

Red-black tree

This is a kind of self-balancing binary search tree. On every insertion and removal, it adjusts its structure by a set of rules so that it does not lean to one side, so lookup, insertion, and removal are always O(log n). It is used in Java's TreeMap and TreeSet, and in HashMap buckets that have many collisions.

equals and hashCode contract

This is the rule that two objects that are equal according to equals() must return the same hashCode() value. A HashMap or HashSet first uses the hash value to find the storage location and then compares with equals inside it, so if you override only equals, an object with the same contents cannot be found. For this reason, always override both methods together, based on the same fields.

Try these

• Default settings — 13 keys are put. At key #13, the buckets grow from 16 to 32.
• hashCode always returns the same value — Every key ends up in one bucket. Watch what happens from key #9 on.
• Only 4 hashCode values — 40 keys are put. Even when the number of buckets grows, the keys pile up in only 4 of them.
• Load factor 0.5 — The map resizes earlier. There are fewer collisions, and more memory is used.
• Only equals overridden — A lookup with a key that has the same contents as a key that was put does not find it.
• Only hashCode overridden — The lookup gets as far as the right bucket, but the key is not recognized as the same key.

Running with the default settings

1. put(id 3817). The hashCode is 3817, and the bucket number is 9 (the remainder of dividing a value that mixes the upper and lower bits of the hashCode by the number of buckets, 16). The bucket was empty, so the entry was put right away.
2. put(id 9204). The hashCode is 9204, and the bucket number is 4 (the remainder of dividing a value that mixes the upper and lower bits of the hashCode by the number of buckets, 16). The bucket was empty, so the entry was put right away.
3. put(id 1466). The hashCode is 1466, and the bucket number is 10 (the remainder of dividing a value that mixes the upper and lower bits of the hashCode by the number of buckets, 16). The bucket was empty, so the entry was put right away.
4. put(id 7531). The hashCode is 7531, and the bucket number is 11 (the remainder of dividing a value that mixes the upper and lower bits of the hashCode by the number of buckets, 16). The bucket was empty, so the entry was put right away.
5. put(id 2890). The hashCode is 2890, and the bucket number is 10 (the remainder of dividing a value that mixes the upper and lower bits of the hashCode by the number of buckets, 16). Entries already in this bucket: 1 (a collision). The key was compared with each of them from the front, and then the entry was attached at the end.
6. put(id 6043). The hashCode is 6043, and the bucket number is 11 (the remainder of dividing a value that mixes the upper and lower bits of the hashCode by the number of buckets, 16). Entries already in this bucket: 1 (a collision). The key was compared with each of them from the front, and then the entry was attached at the end.
7. put(id 5178). The hashCode is 5178, and the bucket number is 10 (the remainder of dividing a value that mixes the upper and lower bits of the hashCode by the number of buckets, 16). Entries already in this bucket: 2 (a collision). The key was compared with each of them from the front, and then the entry was attached at the end.
8. put(id 8312). The hashCode is 8312, and the bucket number is 8 (the remainder of dividing a value that mixes the upper and lower bits of the hashCode by the number of buckets, 16). The bucket was empty, so the entry was put right away.
9. put(id 4725). The hashCode is 4725, and the bucket number is 5 (the remainder of dividing a value that mixes the upper and lower bits of the hashCode by the number of buckets, 16). The bucket was empty, so the entry was put right away.
10. put(id 1039). The hashCode is 1039, and the bucket number is 15 (the remainder of dividing a value that mixes the upper and lower bits of the hashCode by the number of buckets, 16). The bucket was empty, so the entry was put right away.
11. put(id 6654). The hashCode is 6654, and the bucket number is 14 (the remainder of dividing a value that mixes the upper and lower bits of the hashCode by the number of buckets, 16). The bucket was empty, so the entry was put right away.
12. put(id 3391). The hashCode is 3391, and the bucket number is 15 (the remainder of dividing a value that mixes the upper and lower bits of the hashCode by the number of buckets, 16). Entries already in this bucket: 1 (a collision). The key was compared with each of them from the front, and then the entry was attached at the end.
13. put(id 7968). The hashCode is 7968, and the bucket number is 0 (the remainder of dividing a value that mixes the upper and lower bits of the hashCode by the number of buckets, 16). The bucket was empty, so the entry was put right away.
14. The number of entries, 13, exceeded the threshold of 12 (16 buckets × load factor 0.75). The number of buckets was increased from 16 to 32, and the bucket of every entry was decided again. Of the 13 entries, 8 moved to a new bucket. The next resize happens when the number of entries exceeds 24.
15. A new key object is created with the same id, 3817, and put again. The hashCode is 3817, and the bucket number is 9 (the remainder of dividing a value that mixes the upper and lower bits of the hashCode by the number of buckets, 32). A key with the same hash for which equals is also true was found in the bucket. No new entry is created, and only the value is replaced. The number of entries stays at 13.
16. get: A new key object is created with id 3817 and looked up. The hashCode is 3817, and the bucket number is 9 (the remainder of dividing a value that mixes the upper and lower bits of the hashCode by the number of buckets, 32). The key was found after comparing up to node #1 in the bucket. The value is returned.

Result of this run

• Both equals and hashCode are overridden, so a new object created with the same id could also be used to replace the value and to find it.

Code

class MemberKey {
    final int id;
    MemberKey(int id) { this.id = id; }

    @Override public boolean equals(Object o) {
        return o instanceof MemberKey k && k.id == id;
    }

    @Override public int hashCode() {
        return Integer.hashCode(id);   // the id itself
    }
}

Map<MemberKey, String> map = new HashMap<>(16, 0.75f);
for (int id : ids) {                 // number of ids: 13
    map.put(new MemberKey(id), "member");
}

// Create a new object with the same id as the first one that was put
map.put(new MemberKey(ids[0]), "updated");
map.get(new MemberKey(ids[0]));

Assumptions of this model

The initial number of buckets is fixed at 16. The calculation of the bucket number (the upper 16 bits of the hash are mixed into the lower bits, and then the remainder of dividing by the number of buckets is taken), the resize threshold (number of entries > number of buckets × load factor), and the rule that when node #9 is added to a single bucket the number of buckets is increased if there are fewer than 64 buckets and the bucket is converted to a tree if there are 64 or more are the same as in the JDK HashMap implementation. The model was checked against the result of taking out the internals of a real HashMap on JDK 21 on this PC, and in all 360 steps of putting 40 keys each with 3 hashCode implementations × 3 load factors, the number of buckets, the number of entries in each bucket, and whether each bucket is a tree matched. The value of hashCode when it is not overridden is in reality a value that the JVM decides for each object, and here an arbitrary number is used in its place.

Previous lab: ArrayList and LinkedList · Next lab: Kinds of Set and Map