Hash code as key in keyed collection

.net, c#, hash

Solution

When the documentation talks about a "keyed collection", they do not mean the same thing as a Dictionary. For insight into what it actually means, note that there is actually a `KeyedCollection` base class: http://msdn.microsoft.com/en-us/library/ms132438%28v=vs.110%29.aspx

The key paragraph is this:

Unlike dictionaries, an element of `KeyedCollection<TKey, TItem>` is not a key/value pair; instead, the entire element is the value and the key is embedded within the value. For example, an element of a collection derived from `KeyedCollection<String,String>` `(KeyedCollection(Of String, String)` in Visual Basic) might be "John Doe Jr." where the value is "John Doe Jr." and the key is "Doe"; or a collection of employee records containing integer keys could be derived from `KeyedCollection<int,Employee>`. The abstract `GetKeyForItem` method extracts the key from the element.

So a keyed collection is a collection of objects along with a way of extracting a key from each one. Conceptually this is similar to a table in a database, where you can define a primary key which is a subset of the entire record.

So with this in mind, the answer becomes relatively clear. As others have said, equality of hash code does not imply equality of the objects. But keys in a keyed collection- like primary keys in a database table- should uniquely identify the exact object. So the possibility of hash collisions makes them inappropriate for this purpose.

Also, even in a `Dictionary`, there's an important difference between using objects as keys and using the same objects' hash codes as the key. If two objects have a hash collision but do not compare as equal, the `Dictionary` will still store them as two separate keys. That's why overriding `GetHashCode` to just return 1 is always valid (though obviously not good for performance). As a demonstration:

var dict = new Dictionary<MyClass, string>();
var hashDict = new Dictionary<int, string>();

dict[myObj1] = "One";
hashDict[myObj1.GetHashCode()] = "One";
dict[myObj2] = "Two";
hashDict[myObj2.GetHashCode()] = "Two";

Console.Out.WriteLine(dict[myObj1]);  //Outputs "One"
Console.Out.WriteLine(hashDict[myObj1.GetHashCode()]); //Outputs "Two"

(`myObj1` and `myObj2` are instances of `MyClass` which have the same hash code but do not compare as equal)

Problem

As far as I (thought to) know, a `Dictionary` is implemented as a hashtable, where the hash code is used to identify a bucket, which is then searched for the key. In my opinion, this implies that the hash code of an object remains stable during a single run of my program (loosely speaking). Now, here http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx I read "A hash code is intended for efficient insertion and lookup in collections that are based on a hash table. A hash code is not a permanent value. For this reason: [...] Do not use the hash code as the key to retrieve an object from a keyed collection." Can anybody explain to me what that is supposed to mean?

Original source