Hashtable, Hashfunction: Difference between Value, Key, Hashvalue?

Question

Lets imagine we have data we want to put in an Hashtable. The Hashfunction calculates an Hashvalue for each data object and put this hashvalues into a table (each value should get its own bucket). With the hashvalue we know the exact position of the data object in the table.

What role does the key play here? The HashMap in Java wants a specific key for every value we put into the HashMap and with the key we can get the value.

I am wondering whats the difference between the value we want to put into an Hashtable (in java Hashmap), the hashvalue and the key? What is the mathematic behind that?

Answer 1

You always need to original key, to cope with hash collisions. The point of the hash code (or hash value as you're calling it) is to be able to very quickly find possible matches for the keys. The hash code is solely based on the key - the value is completely irrelevant.

So logically, a fetch from a hash table is:

• Compute hash code of key we're searching for
• Find all entries which have the same hash code. (This will be quick, because we're just dealing with a number, and we can arrange a data structure which makes it easy to find entries with a given hash code. There are numerous options here.)
• For each entry with the right hash code, compare the key we're searching for with the key in the entry.
  • If the existing key and the key we're searching for are equal, return the value for that entry
• No matches? Return null to indicate that result.

(The exact way in which the hash table is divided into buckets is an implementation detail. Sometimes each bucket only contains a single entry but can be chained to other buckets; in other cases a bucket can contain several entries. See the wikipedia entry on hash tables for more information.)

Here an "entry" is a {key, value, hash} tuple:

• The hash is derived entirely from the key; the value is irrelevant
• There will never be two equal keys
• There may be multiple entries with the same value; value equality is irrelevant
• There may be multiple entries with the same hash due to hash collisions; this is relevant as there are more entries to look through when trying to find a match for a specific key