Hash codes and hash functions

In short: A hash code is a number computed from a key with GetHashCode(); Dictionary uses it to pick the bucket to search, so it finds a key fast even among a million.

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
{
    public int Row { get; set; }
    public int Number { get; set; }

    public Seat(int row, int number)
    {
        Row = row;
        Number = number;
    }
}

Dictionary<Seat, string> bookings = new Dictionary<Seat, string>();
bookings[new Seat(5, 12)] = "Maria";

Console.WriteLine(bookings.ContainsKey(new Seat(5, 12)));
Console.WriteLine(bookings.Count);
bookings[new Seat(5, 12)] = "Ivan";
Console.WriteLine(bookings.Count);

Output

False
1
2

Maria bought seat 5/12, but ContainsKey with the same seat says False. 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 Dictionary 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 GetHashCode() method returns it. Every object has it, because it is in object.

Console.WriteLine("Maria".GetHashCode() == "Maria".GetHashCode());
Console.WriteLine("Maria".GetHashCode() == "Marie".GetHashCode());
Console.WriteLine("Maria".GetHashCode() == "maria".GetHashCode());
Console.WriteLine(1004.GetHashCode());

Output

True
False
False
1004

• Within one run, the same text gives the same number.
• A small change gives a different number: "Maria", "Marie" and "maria" are three different hash codes.
• The hash code of an int is the number itself.
• A hash code is fast to compute, no matter how many keys are in the dictionary.

The number itself for text is not printed here on purpose. .NET computes the hash code of a string differently on every run of the program, so you would get a different one. The comparisons come out the same every time.

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

More precisely, if you are curious

• Why does the hash code of text change? If it were known in advance, someone could send a server thousands of keys with the same hash code and make the dictionary slow. So .NET picks a random starting point for the computation on every run. The hash code of text is not saved to a file or a database and is not sent to another program: there it is different.

• 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. GetHashCode() is for fast lookups and gives no such protection.

See it

The buckets

Inside, a Dictionary 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. The hash code of text changes on every run, so here the keys are order numbers: for them, the hash code is the number itself:

int[] keys = { 1007, 2043, 3010, 4051 };
int buckets = 8;
foreach (int key in keys)
{
    int hash = key.GetHashCode();
    int index = (hash % buckets + buckets) % buckets;
    Console.WriteLine(key + " -> " + hash + " -> bucket " + index);
}

Step by step, in words

1. Four keys (order numbers) and eight empty buckets, numbered 0 to 7.
2. 1007.GetHashCode() is the number itself, 1007. The remainder when divided by 8 is 7: that is the bucket.
3. 2043 gives bucket 3.
4. 3010 gives bucket 2.
5. 4051 is also in bucket 3: a collision. The two keys are in one bucket: 4051 hangs after 2043 like a chain.
6. Looking up 4051: the same number, the same bucket 3. Equals with 2043: no. With 4051: yes.

• Writing bookings[key] = … computes the bucket and puts the pair there. Looking up (ContainsKey, TryGetValue, [key]) computes the same bucket and looks only in it. That is why it is fast even with a million keys.
• % in C#, as in Java, can give a negative number: -7 % 8 is -7. That is why it is (hash % buckets + buckets) % buckets: this way the remainder is never negative. A hash code can be negative, but a bucket number cannot.
• 2043 and 4051 landed in bucket 3. This is called a collision. The next card is about it.

More precisely, if you are curious

• The real Dictionary turns the hash code into an unsigned number (uint), which is never negative, and takes the remainder of dividing by the number of buckets. That number is a prime (3, 7, 17, 37…), so the numbers there are different, but the principle is the same.

Console.WriteLine(-7 % 8 + " " + (-7 % 8 + 8) % 8);

Output

-7 1

Try it

Which bucket?

The hash code of an int 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 };
foreach (int id in orderIds)
{
    Console.WriteLine(id + " -> bucket " + id.GetHashCode() % 4);
}

Answer

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

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

Check

The idea

Collision: GetHashCode finds the bucket, Equals finds the key

Different keys can have the same hash code. The hash code of a long is the exclusive "or" (XOR) of its upper and lower halves, each of 32 bits. In -1 all the bits are 1, the two halves cancel out, and 0 is left, just as for 0 itself:

Console.WriteLine(0L.GetHashCode() + " " + (-1L).GetHashCode());

Dictionary<long, string> codes = new Dictionary<long, string>();
codes[0L] = "zero";
codes[-1L] = "minus one";
Console.WriteLine(codes[0L] + " " + codes[-1L]);

Output

0 0
zero minus one

The two keys are in one bucket, but the dictionary does not mix them up. The bucket holds a chain of pairs. A lookup goes along it and compares with Equals until it finds the key.

So the two steps work like this:

1. GetHashCode() 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 compares references, and GetHashCode 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 GetHashCode together

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

class Seat
{
    public int Row { get; set; }
    public int Number { get; set; }

    public Seat(int row, int number)
    {
        Row = row;
        Number = number;
    }

    public override bool Equals(object other)
    {
        if (other is not Seat s)
        {
            return false;
        }
        return Row == s.Row && Number == s.Number;
    }

    public override int GetHashCode()
    {
        return 31 * Row + Number;
    }
}

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

Dictionary<Seat, string> bookings = new Dictionary<Seat, string>();
bookings[new Seat(5, 12)] = "Maria";

Console.WriteLine(bookings.ContainsKey(new Seat(5, 12)));
Console.WriteLine(bookings.Count);
bookings[new Seat(5, 12)] = "Ivan";
Console.WriteLine(bookings.Count);

Output

True
1
1

The rules C# expects:

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

If you override only Equals, the compiler warns you, but the program compiles:

class Seat
{
    public int Row { get; set; }
    public int Number { get; set; }

    public Seat(int row, int number)
    {
        Row = row;
        Number = number;
    }

    public override bool Equals(object other)
    {
        if (other is not Seat s)
        {
            return false;
        }
        return Row == s.Row && Number == s.Number;
    }
}

Warning

warning CS0659: 'Seat' overrides Object.Equals(object o) but does not override Object.GetHashCode()

With this Seat, the first program again prints False, 1 and 2: the seat is sold twice. The warning does not stop the compiler, so read it.

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 HashCode.Combine. It computes a hash code from the values you give it:

public override int GetHashCode()
{
    return HashCode.Combine(Row, Number);
}

• The number from HashCode.Combine also changes on every run, like the hash code of text. For the dictionary that does not matter: within one run, equal seats have equal hash codes.
• Equals gets an object, so it first checks whether the other one is a Seat at all. other is not Seat s is the type check from the "Inheritance and polymorphism" module: if the other one is a Seat, s is that object, already of type Seat. That is why new Seat(5, 12).Equals("5/12") is False.
• In C#, a class that will be a key usually also has IEquatable<Seat>: an Equals(Seat other) method, with no conversion from object. Dictionary and HashSet call it when it is there, and Equals(object) only calls it. The properties here are read-only. You will see why in the card "The buckets fill up":

class Seat : IEquatable<Seat>
{
    public int Row { get; }
    public int Number { get; }

    public Seat(int row, int number)
    {
        Row = row;
        Number = number;
    }

    public bool Equals(Seat other)
    {
        return other is not null && Row == other.Row && Number == other.Number;
    }

    public override bool Equals(object other)
    {
        return Equals(other as Seat);
    }

    public override int GetHashCode()
    {
        return HashCode.Combine(Row, Number);
    }
}

• In the "Modern C#" module you will see record. With one line, record Seat(int Row, int Number);, Equals and GetHashCode from the properties are ready, and the first program prints True, 1 and 1.

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:

HashSet<Product> catalog = new HashSet<Product>();
catalog.Add(new Product("A-100", 25.0));
// The price went down, but it is the same product.
Console.WriteLine(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 Product2{3 public string Code { get; set; }4 public double Price { get; set; }56 public Product(string code, double price)7 {8 Code = code;9 Price = price;10 }1112 public override bool Equals(object other)13 {14 return other is Product p && Code == p.Code;15 }1617 public override int GetHashCode()18 {19 return HashCode.Combine(Code, Price);20 }21}

Check

The idea

The buckets fill up

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

• At the start there are no buckets. The first add makes 3.
• When the places fill up, it makes at least twice as many buckets (a prime number again) and redistributes all the keys. The bucket number depends on the number of buckets, so every key is computed again. Here is when it grows:

Dictionary<string, int> prices = new Dictionary<string, int>();
int capacity = prices.EnsureCapacity(0);
for (int i = 1; i <= 20; i++)
{
    prices["product " + i] = i;
    if (prices.EnsureCapacity(0) != capacity)
    {
        capacity = prices.EnsureCapacity(0);
        Console.WriteLine("Grows at pair " + i + ": " + capacity + " slots");
    }
}

Output

Grows at pair 1: 3 slots
Grows at pair 4: 7 slots
Grows at pair 8: 17 slots
Grows at pair 18: 37 slots

• EnsureCapacity(0) returns how many places the dictionary has, without changing anything. Here it only serves to see when the table changes. In a Dictionary there are as many places as buckets.
• That is why, on average, adding and looking up are fast, but now and then one add 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);
HashSet<Seat> sold = new HashSet<Seat>();
sold.Add(seat);

seat.Number = 13;
Console.WriteLine(sold.Contains(seat));
Console.WriteLine(sold.Contains(new Seat(5, 12)));
Console.WriteLine(sold.Count);

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 properties of a key to be read-only: public int Number { get; }.

More precisely, if you are curious

• You can set how many places there are at the start in the constructor: new Dictionary<string, int>(64). The dictionary takes a prime number that is not smaller (here 71), and with 64 keys it does not have to grow along the way. When it grows (when the places fill up) cannot be set.
• In .NET a bucket is always a chain: there is no tree as in Java. Against many deliberate collisions with text, what protects it is that the hash code of text is different on every run.

Dictionary<string, int> prices = new Dictionary<string, int>(64);
Console.WriteLine(prices.EnsureCapacity(0));
for (int i = 1; i <= 64; i++)
{
    prices["product " + i] = i;
}
Console.WriteLine(prices.EnsureCapacity(0));

Output

71
71

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 GetHashCode. For GetHashCode, 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 whether the hash codes of the first two are equal, whether the hash codes of the first and the third are equal, and how many different people are left in a HashSet. Do not print the hash codes themselves: with text they change on every run.

Output

True
False
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
{
    public int X { get; set; }
    public int Y { get; set; }

    public Point(int x, int y)
    {
        X = x;
        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 of its content as hexadecimal text. GetHashCode() will not do here: on the next run the same file would have a different hash code. Use SHA-256 from System.Security.Cryptography: Convert.ToHexStringLower(SHA256.HashData(Encoding.UTF8.GetBytes(content))) (Encoding is in System.Text). A file is written with File.WriteAllText(path, text) and read with File.ReadAllText(path) (in System.IO). 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 different files, and equal SHA-256 hashes in practice mean the same files.

Output

a.txt: 31c9db0c6cb9b9af7e6b355f9e6306b35281291f6a015049da01d1f6858bd293
b.txt: 31c9db0c6cb9b9af7e6b355f9e6306b35281291f6a015049da01d1f6858bd293
c.txt: cb9486eaca5007b8fef9f72a07411f78ed1fcd9a1fad3229c293ee3676024861
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 Dictionary. Make an array of 8 buckets, each a List 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" and the first 8 characters of the SHA-256 of the lowercase email. Is the ID the same for Ivan@Example.com and ivan@example.com? Why will GetHashCode() not do here? Can two different emails get the same ID? How would you find out?
• Counting collisions. Compute the bucket of the keys user1 … user1000 with GetHashCode() for 16, 64 and 1024 buckets, and count how many keys land in a bucket that already has a key. Run the program twice: the count changes a little, because the hash code of text changes.
• 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 GetHashCode with HashCode.Combine, and check the boxes 30×20×10 and 10×20×30 in a HashSet.

Test

Check yourself

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

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

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

The Dictionary 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.GetHashCode() == b.GetHashCode(), alwaysNothingThey must be different

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

True, if a new Seat(5, 12) key was put in beforeIt throws a KeyNotFoundExceptionFalse: the new object is a different object, and the Equals and GetHashCode from object do not look at the properties

5. You override Equals in Seat, but not GetHashCode. What happens?

It compiles with warning CS0659, and the Dictionary still does not find the seatThe program does not compileThe Dictionary computes the hash code from Equals by itself

6. Which property is safe to make part of the GetHashCode of a key?

A property that changes while the object is in a HashSetA property that does not change (get only) and that Equals also comparesA random number picked in the constructor

Check

Start the lesson over

Related lessons

• Builds on: try, catch and finally · Lists · Stack, queue and linked list · Dictionary and HashSet
• Continues in: record, switch and patterns · Hash table · Passwords · Dependencies: other people’s code that yours runs
• Tasks on this topic: Collections