Question: I must admit to having only a rudimentary understanding of how HashTables work, although from what little I do know it seems fairly straightforward. My question is just this: it seems that the conventional wisdom is to use simple, basic value types such as integers for the keys in a HashTable. However, strings are also often used, even though in many languages they are implemented as reference types. What I feel is generally *not* encouraged is using complex reference types; I'm guessing this is because doing so would necessitate a slower hash function? But then why are strings so commonly used? After all, isn't a string internally a char[] array (again, in most languages)?

In the end, what value types are generally regarded as the "best" (or even simply "acceptable") choices to use as keys in a HashTable? And are there any commonly used choices that are actually regarded as "bad" (like strings, possibly)?

Answer: 
The best [hash keys](http://en.wikipedia.org/wiki/Hash_function) are those that 

1. Have good (as in low [collisions](http://en.wikipedia.org/wiki/Collision_(computer_science))) hashes (see [Object.GetHashCode](http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx) for .NET, [Object.hashcode](http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html) for Java)
2. Have quick comparisons (for when there are hash collisions).

All that said, I think Strings are good hash keys in most cases, since there are many excellent hash implementations for Strings.
If you were to use a complex type as a key then:

* It would be hard for the hash table implementation to group items into buckets for fast retrieval; how would it decide how to group a range of hashes into a bucket?
* The hash table may need to have intimate knowledge of the type in order to pick a bucket.
* There is the risk of the properties of the object changing, resulting in items ending up in the wrong buckets. The hashes must be immutable.

Integers commonly used because they are easy to split into ranges that correspond to the buckets, they are value types and therefore immutable, and they are fairly easy to generate.