CODEWITHSUNDEEP
c#hashset
Chuu
Chuu

Reputation: 4509

Do the HashSet set operators work based on GetHashCode() or Equals()?

The C# HashSet defines many set operators such as ExceptWith(...) that require comparing elements to another collection. Do these methods work based on the HashCode of the objects they are comparing, or are they using Equals()?

Upvotes: 1

Views: 850

Answers (1)

Jon Skeet
Jon Skeet

Reputation: 1500515

Anything to do with hash codes should use both GetHashCode and Equals (whether by calling them directly on the candidate values or via an IEqualityComparer<T>).

Hash codes are not guaranteed to be unique: they're just an initial filter, effectively. If two objects are equal then their hash codes must be the same... but just because the hash codes are the same doesn't mean that they're definitely equal.

The hash code is used to very quickly narrow down a large set of possible matches down to a very small set of candidates which have the same hash code. (The hash set remembers both the elements and their hash codes, so that the hash codes can be checked without recomputing them each time.) Then each candidate in turn has to be checked with Equals to determine if it really is a match.

The same logic is used in HashTable and Dictionary, although potentially with subtle differences in implementation. (The Wikipedia article on hash tables lists several variations.)

Upvotes: 4

Related Questions