Consistent hashcodes for dictionaries in c#

Question

You would think that if two dictionaries contained the same keys and values they would return the same hash code? but they don't - how do i get two dictionaires to return the same hash code if they contains the same keys and values?

Thanks. Code sample below - hash codes are different.

    SortedDictionary<int,string> sd1 = new SortedDictionary<int,string>();
    sd1.Add(1,"one");
    sd1.Add(2, "two");
    sd1.Add(5, "five");
    int sd1Hash = sd1.GetHashCode();

    SortedDictionary<int, string> sd2 = new SortedDictionary<int, string>();
    sd2.Add(1, "one");
    sd2.Add(2, "two");
    sd2.Add(5, "five");
    int sd2Hash = sd2.GetHashCode();

I wouldn't think that personally - only if the type was expected to be used as a key in a hash table would I expect the hash code to be the same and with a SortedDictionary I wouldn't — Tom Carter, Jun 11 '09 at 11:00
You may find this helpful: [Getting hash of a list of strings regardless of order](https://stackoverflow.com/questions/670063/getting-hash-of-a-list-of-strings-regardless-of-order/) — Theodor Zoulias, Apr 19 '19 at 19:21

Simon P Stevens · Answer 1 · 2009-06-11T10:40:52.963

For reference types, hashcodes are defined based on the reference, not the object itself. The hadhcodes will only be the same if the two dictionaries point to the same object.

You could override the GetHashCode method in your own class, and re-code it to build a custom hash code based on the contents of the dictionary, but that would break user expectation of how the function works, so probably isn't a good idea. I'd write an extension method or an IComparer that took 2 dictionaries and compared them by comparing the values in them.

score 2 · Answer 2 · answered Jun 11 '09 at 10:36

2

If you use .NET Reflector, you can take a look at the definition of SortedDictionary, and it doesn't override GetHashCode, so the value it returns will not depend in any way on the keys and values.

answered Jun 11 '09 at 10:36

Daniel Earwicker

114,894
38
205
284

score -3 · Answer 3 · answered Jun 11 '09 at 10:34

-3

The hashcode I believe is also instance dependent.

Create a new class the inherits from the SortedDictionary class. Then override GetHashCode();

e.g.

class SortedHasher : SortedDictionary<int, string>
{
   public override int GetHashCode()
   {
      int hash = 0;
      foreach(KeyValuePair<int, string> kvp in this)
      {
         hash += kvp.Key.GetHashCode() + kvp.Value.GetHashCode();
      }
      return hash;
   }
}

answered Jun 11 '09 at 10:34

Ian

33,605
26
118
198

Ian: Using this technique will mean that the hashcode changes whenever the items in the collection are added, removed or updated. Not a very good idea. – LukeH Jun 11 '09 at 10:39
2

This is really really bad. your implementation of GetHashCode could result in dictionaries with different contents having the same hash code. By summing the hash codes of the dictionaries contents you could cause real problems. Imaging 2 dictionaries containing {1,2} and {2,1} With your method both of these would have the same resultant hash code. When overriding GetHashCode it is critical you make sure that 2 different objects can never end up with the same hash code. – Simon P Stevens Jun 11 '09 at 10:40
@Simon: It's not necessarily the end of the world if two different objects return the same hashcode. See the "Remarks" section of http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx. – LukeH Jun 11 '09 at 10:56
Careful, according to http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx two different objects may return the same hashcode. Only if the objects are equal do they need to return the same hashcode – Tom Carter Jun 11 '09 at 10:56
Luke : I believe that is the whole point of the question though. And if I'm not mistaken the hashcode of the SortedDictionary would change anyway. I've actually +1'd Simon's comment because I think he's right. It's something I didn't consider and isn't an unlikely situation. Fortunately in this case the key and value are different data types so the chances actually rely on the GetHashCode() for the int and string objects to return the same codes. – Ian Jun 11 '09 at 11:06
1

@Ian: Simon is correct when he says that your implementation is problematic. He's not right when he says that hashcodes have to be unique. It's fine for two objects to have the same hashcode so long as they implement Equals correctly: If two objects are equal then they *must* have the same hashcode, but objects with the same hashcode aren't necessarily equal. – LukeH Jun 11 '09 at 11:30
Luke hits the nail on the head - you have to remember what the hashcode is for : it's to give a fast *indication* that 2 instances are the same - it's the Equals function that determines whether they are actually the same or not – Tom Carter Jun 11 '09 at 11:47
1

@Luke/Ian/Tom: All right all right, maybe I overreacted a tincy bit =:) but my point still stands - I wouldn't recommend this particular implementation. If the OP is doing this to try and compare two dictionaries, personally I'd leave the default implementation of GetHashCode() alone and look at creating a custom IComparer class or something like that to check the equality of contents. – Simon P Stevens Jun 11 '09 at 12:07
I don't see what is particularly objectionable about summing the hash codes. This is what Java HashMap does [1] and those are conveniently comparable with 'equals'. Yes, the hashcode will then change with the contents. In over 10 years I have never observed this as a problem, or seen anybody use a Dictionary as a Dictionary key. [1] http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/AbstractMap.java#AbstractMap.hashCode%28%29 – aaron Sep 07 '13 at 03:48

Consistent hashcodes for dictionaries in c#

3 Answers3