GetHashCode() - change item id and then find that item in dictionary - KeyNotFoundException

Question

Finding items in dictionary is based on hash code. The hash code is based on item id in below code so I shouldn't change item id. But I have done some experiment and I have changed item id and searched it in dictionary but then I have got KeyNotFoundException. Could somebody explain me why?

After change point1 id, it has 1727699806 hash code, element with index 0 in dictionary has the same hash code: 1727699806 - so why I have KeyNotFoundException?

class Program
{
    public class Point
    {
        public int Id { get; set; }

        public override bool Equals(object obj)
        {
            return obj is Point point &&
                    Id == point.Id;
        }

        public override int GetHashCode()
        {
            return HashCode.Combine(Id);
        }
    }

    static void Main(string[] args)
    {
        Point point1 = new Point();
        point1.Id = 5;            

        Point point2 = new Point();
        point2.Id = 20;

        var dictionary = new Dictionary<Point, string>()
        {
            { point1, "Poland" },
            { point2, "Germany" }
        };

        point1.Id = 999; // here I change id
        var point1_hash = point1.GetHashCode(); //1727699806

        var dictionary1_hash = dictionary.ElementAt(0).Key.GetHashCode(); //1727699806
        var dictionary2_hash = dictionary.ElementAt(1).Key.GetHashCode(); //650208270

        string result = dictionary[point1]; //KeyNotFoundException
    }
}

After change point1 id, it has 1727699806 hash code, element with index 0 in dictionary has the same hash code: 1727699806 - so why I have KeyNotFoundException?

So you know that you shouldn't do that and are confused that it leads to problems? — Joey, May 12 '19 at 13:03
Because `5 != 999`, even if both have the same hashcode https://stackoverflow.com/questions/2975612/what-happens-when-hash-collision-happens-in-dictionary-key — Guy, May 12 '19 at 13:04

score 2 · Answer 1 · answered May 12 '19 at 16:15

The issue is that the object/key is placed in a so called "bucket" inside the Dictionary class. Each entry in a bucket has the same hashcode (simplified, there are some modulo operations involved so there aren't int.MaxValue buckets). When you insert or retrieve an object with the key, the Dictionary class only needs to look in one bucket because the keys have the same hashcode.

But now you have changed the hashcode of the key object by changing the Id property. The key point1 is now stored in a bucket where it doesn't belong to, but the Dictionary class doesn't know about that change. This means:

When you use the getter, a different hashcode will be calculate so the Dictionary class will look in a different bucket.
The Dictionary class will not find the key/entry, because it is in the previous selected bucket (a different one).

For that reason, you must not change the object of the key to produce a different hashcode, while is it used as a key in a Dictionary. See the documentation of the Dictionary class:

As long as an object is used as a key in the Dictionary<TKey,TValue>, it must not change in any way that affects its hash value.

Joey · Accepted Answer · 2019-05-13T05:44:33.090

1

This answer was incorrect, but cannot be deleted for technical reasons. See Progman's answer below, instead.

edited May 13 '19 at 05:44

answered May 12 '19 at 13:04

Joey

344,408
85
689
683

2

-1, This doesn't explain why the key isn't found even though it's inside the Dictionary. It is even the exact same object so it should find it (and not throw a KeyNotFoundException). The problem is that the key to look for is now in the wrong internal bucket of the `Dictionary` class after changing the `Id` and therefore the hash code. – Progman May 12 '19 at 15:51
@Progman: Good point, I overlooked that part. Can't delete the answer now, though. – Joey May 13 '19 at 05:43

score 0 · Answer 3 · answered May 12 '19 at 17:03

Here is the related source code inside Dictionary<T> class:

private int FindEntry(TKey key)
{
    if (buckets != null)
    {
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next)
        {
            if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
        }
    }
    return -1;
}

As you can see, searching for a key starts by calculating the hashcode of the searched key. This hashcode determines the bucket that will be searched for a matching entry. Then each entry inside the specified bucket is compared first by the stored hashcode, and then by value of the key. So changing the key of an entity stored in a dictionary breaks the key finding algorithm in three different ways.

GetHashCode() - change item id and then find that item in dictionary - KeyNotFoundException

3 Answers3