Error in Array.IStructuralEquatable.GetHashCode?

Question

When writing my own immutable ByteArray class that uses an internal byte array, I implemented the IStructuralEquatable interface. In my implementation, I delegated the task of computing hash codes for an internal array. During testing, to my great surprise, I found that my two different arrays had the same structural hash code, i.e. They returned the same value from GetHashCode . Playback:

 IStructuralEquatable array11 = new int[] { 1, 1 }; IStructuralEquatable array12 = new int[] { 1, 2 }; IStructuralEquatable array22 = new int[] { 2, 2 }; var comparer = EqualityComparer<int>.Default; Console.WriteLine(array11.GetHashCode(comparer)); // 32 Console.WriteLine(array12.GetHashCode(comparer)); // 32 Console.WriteLine(array22.GetHashCode(comparer)); // 64 

IStructuralEquatable is completely new and unknown, but I read somewhere that it can be used to compare the contents of collections and arrays. Am I mistaken, or is my .Net wrong?

Please note that I'm not talking about Object.GetHashCode !

Edit: Thus, I am apparently mistaken, since unequal objects can have the same hash codes. But doesn't GetHashCode mean returning some randomly distributed set of values? After some testing, I found that any two arrays with the same first element have the same hash. I still think this is strange behavior.

Answer 1

What you described is not a mistake. GetHashCode() does not guarantee unique hashes for non-null objects.

From MSDN :

If two objects are compared as equal, the GetHashCode method for each object must return the same value. However, if two objects are not compared as equal, GetHashCode methods for two objects should not return different values.

EDIT

While the implementation of MSFT.NET GetHashCode() for Array.IStructuralEquatable follows the principles in the above MSDN documentation, it seems that the authors did not implement it as intended.

Here is the code from "Array.cs":

  int IStructuralEquatable.GetHashCode(IEqualityComparer comparer) { if (comparer == null) throw new ArgumentNullException("comparer"); Contract.EndContractBlock(); int ret = 0; for (int i = (this.Length >= 8 ? this.Length - 8 : 0); i < this.Length; i++) { ret = CombineHashCodes(ret, comparer.GetHashCode(GetValue(0))); } return ret; } 

Pay particular attention to this line:

ret = CombineHashCodes(ret, comparer.GetHashCode(GetValue( 0 )));

If I am wrong, 0 should have been i . Because of this, GetHashCode() always returns the same value for arrays with the same maximum (0, n-8th) element, where n is the length of the array. This is not the case (does not violate the documentation), but it is clearly not as good as if 0 were replaced with i . There is also no reason for a loop if the code was just about to use a single value from an array.

Answer 2

This bug has been fixed, at least with .NET 4.6.2. You can see it through the Help source .

 ret = CombineHashCodes(ret, comparer.GetHashCode(GetValue(i))); 

Answer 3

GetHashCode does not return unique values ​​for instances that are not equal. However, instances that are equal will always return the same hash code.

For a quote from the Object.GetHashCode method :

If two objects are compared as equal, the GetHashCode method for each object must return the same value. However, if two objects are not compared as equal, GetHashCode methods for two objects should not return different values.

Your observations do not contradict the documentation and errors in the implementation.