C# in a Nutshell, Second Edition

Name

Hashtable

Synopsis

A hashtable is an associative array (dictionary) that contains key-value pairs. Each value is identified and retrieved by a specific key that is transformed into an integer value called a hashcode.

A hashtable is an efficient way to store and retrieve values in memory. It uses a fast algorithm to convert a hashcode into a hash key. This hash key is used internally to determine which “bucket” a hashtable entry belongs to. Although the algorithm selects a bucket quickly, each bucket may contain more than one value. In this case, a linear search locates the desired value based on its hashcode. However, the fast bucket search offers such an advantage that a subsequent linear search has a negligible impact on the overall performance of the hashtable.

Initially, a 1-to-1 ratio of buckets to values applies (called the load factor). However, as more items are added to the hashtable, the load factor is changed, and each bucket ends up holding more elements. Greater load factors reduce the amount of memory required to store the hashtable, but increase lookup time.

The first argument to the Hashtable constructor gives a value for its initial size or provides an existing IDictionary whose values will fill the Hashtable. A Hashtable automatically increases its size when all buckets are full. The loadFactor argument is optionally used to specify the load factor; the default is 1.0. You can also provide references to IHashCodeProvider and IComparer instances in the constructor ...