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: 
It's not a matter of *strings* versus *integers*, or value versus reference, but of **mutable keys versus immutable keys.** As long as the keys are immutable (and thus their hashing value never change) they are OK to index a hash table. For instance, strings in Java are immutable and thus perfectly suited as hashtable keys.

By the way, if a data type is simpe enough to be always passed by value (like scalars), then it will of course be OK.

But now imagine that you use a mutable type ; if you give me a reference to one of these objects as a key, I will compute its hash value and then put it in one of my hashtable buckets. But when you later modify the object, I will have no way to be notified ; and the object may now reside in the wrong bucket (if its hash value is different).

Hope this helps.
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.