Hashing an array in c#
Solution 1
To compute a hash code using the elements of an array, you can cast the array to IStructuralEquatable and then call the GetHashCode(IEqualityComparer) method, passing a comparer for the type of elements in the array.
(The cast is necessary because the Array class implements the method explicitly.)
For example, if your object has an int
array, then you can implement GetHashCode like this:
public override int GetHashCode()
{
return ((IStructuralEquatable)this.array).GetHashCode(EqualityComparer<int>.Default);
}
In case you're curious, here's how the Array class implements the GetHashCode method (from the Reference Source):
internal static int CombineHashCodes(int h1, int h2) {
return (((h1 << 5) + h1) ^ h2);
}
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(i)));
}
return ret;
}
As you can see, the current implementation only uses the last eight elements of the array.
Solution 2
It depends on what you want ...
One option as Michael answered above is to have a hashcode based on the array elements. This will be in line with your Equals value semantics. However because "As a guideline, the hash of an object must be the same over the object's entire lifetime" you will have to ensure your array does not change after getting its hashcode. To have a non immutable container with a demand that it never changes sounds error prone to me.
Your other (IMO better option) is to switch to an immutable container (ie ImmutableArray) then a value-based hashcode makes sense. You can either use IStructuralEquatable
as above or more generally:
public override GetHashCode() =>
Value.Aggregate(0, (total, next) => HashCode.Combine(total, next));
which will work for other immutable collections as well.
Solution 3
I don't agree you should naturally implement GetHashCode on an array
You would have to update it with every change
Or calculate it on the fly
I would compare directly on the fly
SequenceEquals will use the default equality comparer so you should also implement
public bool Equals
0n the objects in the array
Enumerable.SequenceEqual
Has an example
public static void SequenceEqualEx1()
{
Pet pet1 = new Pet { Name = "Turbo", Age = 2 };
Pet pet2 = new Pet { Name = "Peanut", Age = 8 };
// Create two lists of pets.
List<Pet> pets1 = new List<Pet> { pet1, pet2 };
List<Pet> pets2 = new List<Pet> { pet1, pet2 };
bool equal = pets1.SequenceEqual(pets2);
Console.WriteLine(
"The lists {0} equal.",
equal ? "are" : "are not");
}
Solution 4
Using the current framework one could consider using
int value=0;
for (var i = 0;i< this.array.Length; i++)
{
value=HashCode.Combine(this.array[i],value);
}
Related videos on Youtube
c z
Updated on July 25, 2022Comments
-
c z almost 2 years
Short question
How to implement
GetHashCode
for anArray
.Details
I have an object that overrides
Equals
, checking that:this.array[n] == otherObject.array[n]
for all
n
inarray
.Naturally I should implement the complementary
GetHashCode
. I was wondering if there is .NET way to do this, or if I should implement my own, something likehash = hash ^ array[n]
Clarification
My object contains an array, and I'm interested on GetHashCode for the elements of the array. My code for array equivalence is for example only - like my question says but maybe I wasn't clear, I'm interested in
GetHashCode
(notEquals
). I say I naturally should implement the complementaryGetHashCode
because it is a requirement of .NET to implement this onceEquals
is overridden (forDictionary
etc. to function correctly). Thanks.-
Draken about 8 yearsHave a look at the answer posted here. In other words, you are better off implementing your own variation or using another tool, you can't use
GetHashCode()
orEquals()
for an Array -
Mathias R. Jessen about 8 yearsWhy not do
this.array[n].Equals(otherObject.array[n])
forn
? -
Mike Debela about 8 yearsIf you want to compare two arrays for equality, you can use
SequenceEqual
extension -
Michael Liu about 8 years@c z: Please clarify whether
array
is a field in the object for which you're overriding Equals and GetHashCode. -
Christian Gollhardt almost 6 yearsPossible duplicate of GetHashCode override of object containing generic array
-
-
Michael Liu about 8 yearsThe OP has implemented Equals on an object which contains an array. It is natural to implement GetHashCode on that object as well.
-
paparazzo about 8 years@MichaelLiu Not how I read it. I am not reading an object which contains an array. I read it as objects in the array override equals this.array[n] == otherObject.array[n].
-
Michael Liu about 8 yearsWhy would an object in the array have an Equals method that references
this.array
? That would mean you have an array of objects which in turn contain arrays. -
paparazzo about 8 yearsNo it does not mean that. You are reading somethig not there. I agree why would an item in an array need to reference the array? There is slick built in method for comparing two arrays that uses default equality comparer of the items in the array.
-
c z about 8 years"I don't agree you should naturally implement GetHashCode on an array" - Dictionary<T, U> behaves very oddly if you don't implement GetHashCode when you override equals, so I really need GetHashCode.
-
paparazzo about 8 years@cz That is information you could have included in the question. Really you have a Dictionary where the Key is an object that implements array?
-
paparazzo about 8 yearsUnless you have large Dictionary you could just use the array size as the GetHashCode. If you have large dictionary with arrays as Keys then wow.
-
Michael Liu almost 6 yearsUsing Array.GetHashCode() is definitely wrong because it will return different values for two arrays with equal elements, whereas the OP needs it to return the same value. Obviously, you have to ensure that the contents of the array are not modified after obtaining its structural hash code, which is possible to do if the array is a private member of an object. (Given that an array has a fixed size, I assume that's what you meant by "add/remove elements".)
-
kofifus almost 6 yearsyou're right! edited my answer. It seems there is no 'good' solution to storing non-immutable collections with value semantics as elements of other collections