Information Technology Reference
In-Depth Information
single function generates more discussion and more confusion than
GetHashCode(). Read on to remove all that confusion.
If you're defining a type that won't ever be used as the key in a container,
this won't matter. Types that represent window controls, Web page con-
trols, or database connections are unlikely to be used as keys in a collec-
tion. In those cases, do nothing. All reference types will have a hash code
that is correct, even if it is very inefficient. Value types should be
immutable (see Item 20), in which case, the default implementation always
works, although it is also inefficient. In most types that you create, the best
approach is to avoid the existence of GetHashCode() entirely.
One day, you'll create a type that is meant to be used as a hash key, and
you'll need to write your own implementation of GetHashCode(), so read
on. Hash-based containers use hash codes to optimize searches. Every
object generates an integer value called a hash code. Objects are stored in
buckets based on the value of that hash code. To search for an object, you
request its key and search just that one bucket. In .NET, every object has a
hash code, determined by System.Object.GetHashCode(). Any overload
of GetHashCode() must follow these three rules:
1. If two objects are equal (as defined by operator==), they must gen-
erate the same hash value. Otherwise, hash codes can't be used to
find objects in containers.
2. For any object A, A.GetHashCode() must be an instance invariant.
No matter what methods are called on A, A.GetHashCode() must
always return the same value. That ensures that an object placed in a
bucket is always in the right bucket.
3. The hash function should generate a random distribution among all
integers for all inputs. That's how you get efficiency from a hash-
based container.
Wr i t i n g a cor re c t a n d e f fi c i e n t h a s h f u n c t i o n re q u i re s ex ten s ive k n ow l e d g e
of the type to ensure that rule 3 is followed. The versions defined in
System.Object and System.ValueType do not have that advantage. These
versions must provide the best default behavior with almost no knowl-
edge of your particular type. Object.GetHashCode() uses an internal field
in the System.Object class to generate the hash value. Each object created
is assigned a unique object key, stored as an integer, when it is created.
These keys start at 1 and increment every time a new object of any type gets
created. The object identity field is set in the System.Object constructor and
