How HashMap works

Problem

The seat was sold twice

The theater box office keeps the sold seats in a dictionary: seat → name of the customer. A seat is a class with a row and a number:

class Seat {
    int row;
    int number;

    Seat(int row, int number) {
        this.row = row;
        this.number = number;
    }
}

Map<Seat, String> bookings = new HashMap<>();
bookings.put(new Seat(5, 12), "Maria");

System.out.println(bookings.get(new Seat(5, 12)));
System.out.println(bookings.size());
bookings.put(new Seat(5, 12), "Ivan");
System.out.println(bookings.size());

Output

null
1
2

Maria bought seat 5/12, but get with the same seat returns null. Then Ivan buys the same seat, and the dictionary now has two 5/12 keys. Why?

The idea

Hash code: a number from the key

A HashMap does not compare the key with all the others. It computes one whole number from the key, and from it, it knows where to look. This number is called a hash code, and the hashCode() method returns it. Every object has it, because it is in Object.

System.out.println("Maria".hashCode());
System.out.println("Maria".hashCode());
System.out.println("Marie".hashCode());
System.out.println("maria".hashCode());

Output

74113750
74113750
74113754
103666422

• The same text gives the same number, every time and on every computer.
• A small change gives a different number: "Maria", "Marie" and "maria" are three different hash codes.
• A hash code is fast to compute, no matter how many keys are in the dictionary.

The method that makes the number is called a hash function.

More precisely, if you are curious

• For String the formula is defined in the Java documentation: s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1], where s[i] is the code of each character. The result is an int, so on overflow it becomes negative.

• Cryptographic hash functions like SHA-256 are something else. They give a long result, and it is practically impossible to find two texts with the same hash. That is why they are used to check that a file has not been tampered with and to store passwords. hashCode() is for fast lookups and gives no such protection.

See it

The buckets

Inside, a HashMap is an array of buckets. The number of the bucket for a key is the remainder of the hash divided by the number of buckets:

String[] keys = { "Boris", "Yana", "Ivan", "Emil" };
int buckets = 8;
for (String key : keys) {
    int hash = key.hashCode();
    int index = Math.floorMod(hash, buckets);
    System.out.println(key + " -> " + hash + " -> bucket " + index);
}

Step by step, in words

1. Four keys and eight empty buckets, numbered 0 to 7.
2. "Boris".hashCode() is 64372111. The remainder when divided by 8 is 7: that is the bucket.
3. "Yana" gives 2748123, bucket 3.
4. "Ivan" gives 2291258, bucket 2.
5. "Emil" is also in bucket 3: a collision. The two keys are in one bucket: "Emil" hangs after "Yana" like a chain.
6. Looking up "Emil": the same number, the same bucket 3. equals with "Yana": no. With "Emil": yes.

• put computes the bucket and puts the pair there. get computes the same bucket and looks only in it. That is why it is fast even with a million keys.
• Math.floorMod is a remainder of division that is never negative. A hash code can be negative, but a bucket number cannot.
• "Yana" and "Emil" landed in bucket 3. This is called a collision. The next card is about it.

More precisely, if you are curious

• The real HashMap computes the index a little differently: (h ^ (h >>> 16)) & (n - 1). The number of buckets n is always a power of two, and & (n - 1) is a fast remainder of division by n. So the numbers there are different, but the principle is the same.

Try it

Which bucket?

The hash code of an Integer is the number itself. The order numbers go into a dictionary with 4 buckets.

What will the program print?

int[] orderIds = { 6, 10, 13, 21 };
for (int id : orderIds) {
    Integer key = id;
    System.out.println(id + " -> bucket " + Math.floorMod(key.hashCode(), 4));
}

Answer

6 -> bucket 6
10 -> bucket 10
13 -> bucket 13
21 -> bucket 21

6 -> bucket 2
10 -> bucket 0
13 -> bucket 1
21 -> bucket 3

6 -> bucket 1
10 -> bucket 2
13 -> bucket 3
21 -> bucket 4

6 -> bucket 2
10 -> bucket 2
13 -> bucket 1
21 -> bucket 1

Check

The idea

Collision: hashCode finds the bucket, equals finds the key

Different keys can have the same hash code. The two best-known examples:

System.out.println("Aa".hashCode() + " " + "BB".hashCode());

Map<String, Integer> codes = new HashMap<>();
codes.put("Aa", 1);
codes.put("BB", 2);
System.out.println(codes.get("Aa") + " " + codes.get("BB"));

Output

2112 2112
1 2

The two keys are in one bucket, but the dictionary does not mix them up. The bucket holds a small linked list of pairs. get goes along it and compares with equals until it finds the key.

So the two steps work like this:

1. hashCode() says which bucket to look in.
2. equals() says which of the keys in the bucket is the one you want.

Now it is clear what happened with the theater seat. Seat overrides neither of them, so it uses the versions from Object. There, equals is ==, and hashCode is usually different for every object. The two new Seat(5, 12) objects are two different objects, so they are also two different keys.

The idea

The contract: equals and hashCode together

Seat has to say when two seats are the same seat, and give equal seats the same hash code:

class Seat {
    int row;
    int number;

    Seat(int row, int number) {
        this.row = row;
        this.number = number;
    }

    @Override
    public boolean equals(Object other) {
        if (!(other instanceof Seat)) {
            return false;
        }
        Seat s = (Seat) other;
        return row == s.row && number == s.number;
    }

    @Override
    public int hashCode() {
        return 31 * row + number;
    }
}

With the same code in main as in the first card:

Map<Seat, String> bookings = new HashMap<>();
bookings.put(new Seat(5, 12), "Maria");

System.out.println(bookings.get(new Seat(5, 12)));
System.out.println(bookings.size());
bookings.put(new Seat(5, 12), "Ivan");
System.out.println(bookings.size());

Output

Maria
1
1

The rules Java expects:

• If a.equals(b), then a.hashCode() == b.hashCode(). Always.
• If the hash codes are equal, the objects may be different. That is a collision.
• If you override equals, override hashCode too, with the same fields.

More precisely, if you are curious

• Why 31? It is an odd prime number, and it mixes well. Multiplying by 31 makes the hash depend on the order: seat 5/12 and seat 12/5 have different hash codes. With row + number, the two would land in the same bucket.
• Instead of the formula, you can write Objects.hash from java.util.Objects. It computes the same thing from the fields you give it:

@Override
public int hashCode() {
    return Objects.hash(row, number);
}

• equals gets an Object, so it first checks with instanceof whether the other one is a Seat at all, and then casts it. This is the downcast from the "Inheritance" module.

Try it

Find the bug

The catalog keeps the products in a HashSet. Two products with the same code are the same product, even if the price has changed. But contains with the new price returns false:

Set<Product> catalog = new HashSet<>();
catalog.add(new Product("A-100", 25.0));
// The price went down, but it is the same product.
System.out.println(catalog.contains(new Product("A-100", 19.9)));

Output

false

Which line in the class has the bug?

Pick the line with the bug.

1class Product {2 String code;3 double price;45 Product(String code, double price) {6 this.code = code;7 this.price = price;8 }910 @Override11 public boolean equals(Object other) {12 if (!(other instanceof Product)) {13 return false;14 }15 return code.equals(((Product) other).code);16 }1718 @Override19 public int hashCode() {20 return Objects.hash(code, price);21 }22}

Check

The idea

The buckets fill up

When there are many pairs, the buckets get long and lookups slow down. That is why a HashMap grows:

• At the start there are 16 buckets.
• When there are more pairs than 75% of the number of buckets, it makes twice as many buckets and redistributes all the keys. The bucket number depends on the number of buckets, so every key is computed again.
• That is why, on average, put and get are fast, but now and then one put takes longer.

There is a trap too. A key must not change while it is in a dictionary or a set:

Seat seat = new Seat(5, 12);
Set<Seat> sold = new HashSet<>();
sold.add(seat);

seat.number = 13;
System.out.println(sold.contains(seat));
System.out.println(sold.contains(new Seat(5, 12)));
System.out.println(sold.size());

Output

false
false
1

The seat was put in the bucket for 5/12. Then its number became 13, and the hash code changed. contains(seat) looks in the bucket for 5/13 and does not find it. contains(new Seat(5, 12)) looks in the right bucket, but the object there is no longer equal to 5/12. The element is in the set (the size is 1), but it cannot be found. That is why it is a good idea for the fields of a key to be final.

More precisely, if you are curious

• That 75% is called the load factor, and you can set it in the constructor: new HashMap<>(64, 0.75f). If you know how many keys there will be, give the starting number of buckets, and the dictionary will not have to grow along the way.
• From Java 8 on, a bucket with more than 8 pairs (TREEIFY_THRESHOLD) turns from a list into a balanced tree, if there are at least 64 buckets. If a redistribution leaves 6 or fewer pairs in such a bucket (UNTREEIFY_THRESHOLD), the tree becomes a list again. So with many collisions, a lookup in a bucket with n pairs takes about log n comparisons instead of n.

Exercise

Your own hash codes

Solve the tasks in your editor.

1. A hash code for a person. A Person class with a first name, a last name and an age. Override equals and hashCode. For hashCode, use the recipe: start from 17, and for each field, result = 31 * result + the hash of the field. For an int field, the hash is the number itself. Create Ivan Petrov at 30 twice and once at 31. Print the hash codes and how many different people are left in a HashSet.

Output

-1104532243
-1104532243
-1104532242
Different people: 2

2. The robot in the warehouse. The robot starts at cell (0, 0) and makes the moves NNEESWWN: N is up (y + 1), S is down, E is right (x + 1), W is left. How many different cells has it visited, counting the starting one? Keep them in a HashSet<Point>. With this class the program says 9, but it should say 7. Fix it:

class Point {
    int x;
    int y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

Output

Moves: 8
Different cells: 7

3. A hash of a file. A hashFileContent(String filePath) method reads the file and returns the hash code of its content as hexadecimal text: Integer.toHexString(content.hashCode()). Write three reports: a.txt and b.txt with "October report: €1250", and c.txt with "October report: €1260". Compare their hashes. Different hashes mean the files are certainly different. Equal hashes mean "almost certainly the same": with an int a collision is possible, so for a real check you use SHA-256.

Output

a.txt: c2192f1c
b.txt: c2192f1c
c.txt: c21932dd
a and b: same
a and c: different

More tasks

• Your own hash table. A follow-up to the user table from the last lesson, this time without HashMap. Make an array of 8 buckets, each an ArrayList of username and email pairs. The hash function is the sum of the character codes in the name. Write add, get, and a method that prints how many pairs are in each bucket.
• An ID from an email. generateUserId(String email) returns "U" + Integer.toHexString(email.toLowerCase().hashCode()). Is the ID the same for Ivan@Example.com and ivan@example.com? Can two different emails get the same ID? How would you find out?
• Counting collisions. Compute the bucket of the keys user1 … user1000 with 16, 64 and 1024 buckets, and count how many keys land in a bucket that already has a key.
• The shoe box. A Box class with a width, a height and a depth. Two boxes are the same if their sizes are the same, in the same order. Write equals and hashCode with Objects.hash, and check the boxes 30×20×10 and 10×20×30 in a HashSet.

Test

Check yourself

1. What does a HashMap do with the hash code of a key?

It compares it with all the other hash codesIt stores it instead of the keyIt computes from it the number of the bucket to look in

2. Two different keys have the same hash code. What happens?

HashMap throws an exceptionThe second one deletes the firstBoth sit in one bucket, and equals tells them apart

3. a.equals(b) is true. What must be true about their hash codes?

a.hashCode() == b.hashCode(), alwaysThey must be differentNothing

4. You use your own Seat class as a key without overriding equals and hashCode. What does get(new Seat(5, 12)) return?

The value put in with put(new Seat(5, 12), …)null: the new object is a different object, and the equals and hashCode from Object do not look at the fieldsIt throws an exception

5. Which field is safe to make part of the hashCode of a key?

A field that does not change (final) and that equals also comparesA field that changes while the object is in a HashSetA random number picked in the constructor

Check

Start the lesson over