When picking a data structure to store key/value pairs and the size is unknown the HybridDictionary object (System.Collections.Specialized) is a great tool for the job. The data structure will internally use a ListDictionary while the count is <= 10 and will convert to using a Hashtable afterwards. If the starting item count is greater than 10, the HybridDictionary will start out with the Hashtable to reduce the overhead generated by the conversion.
A ListDictionary uses an single linked list data structure for implementation so the Item, Add, Remove, and Contain operations are all in linear time.
The Hashtable works off the Object.GetHashCode method for storage. For each entry, a key, value, and a hashcode is stored. The entry is placed into a bucket based on this hashcode. Each time a item is added to the Hashtable, an actual load factor is computed and is compared to the specified load factor. The default load factor of 1.0 can be changed during the Hashtable creation, but must be between 0.10 and 1.0. The load factor is directly related to the probability that a bucket will contain more than one entry. The lower the value, the less chance of a collision but the trade-off is memory consumption. Then the actual equals the specified load factor, the Hashtable is reallocated to contain the smallest prime number larger than twice the current number of hashtable buckets. Dan Mabbutt has some interesting benchmarks regarding the load factor.
Customized hashing can be achieved by overriding the Object.GetHashCode, and Object.GetEquals methods. Using the IEqualityComparer interface will enforce these methods.
The operations for the Hashtable are all in constant time on average with the exceptions of reallocation, hash collisions, and multiple items in a bucket. The Hashtable will automatically rehash collisions.
For a hash table review visit Wikipedia.
Remember that all key objects must be immutable!