2

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?

Carl0s1z
  • 4,683
  • 7
  • 32
  • 47
Ubuntix
  • 324
  • 4
  • 15
  • Have a look at [my answer here](http://stackoverflow.com/questions/6493605/how-does-a-hashmap-work-in-java/6493946#6493946). – Jesper Feb 06 '14 at 13:54
  • 2
    `each value should get its own bucket`---the word *bucket* itself should already be a strong hint that this is not true. – Marko Topolnik Feb 06 '14 at 13:55
  • `put this hashvalues into a table`---wrong. It puts the *key* into the bucket addressed by the hash value. Many hash values address the same bucket. – Marko Topolnik Feb 06 '14 at 13:56
  • each value doesn't get its own bucket. each *entry* is stored in a bucket, the bucket is chosen based on the hash of the key, usually a mod of the hash (polygenelubricants notwithstanding - it's not just a mod) – Bohemian Feb 06 '14 at 13:56
  • None of these comments, nor Jon skeet's answer, address the specific question the poster seems to have: the hash value is computed from the key, and the key only. The value is not used in the calculation. – Ernest Friedman-Hill Feb 06 '14 at 14:09
  • @ErnestFriedman-Hill: Will edit my answer to clarify that, although the fact that the first step is "compute hash code of key we're searching for" is pretty suggestive, IMO. – Jon Skeet Feb 06 '14 at 14:13
  • thanks a lot guys. that answers my question! but what is the difference between HashMap and HashSet? I know how to use them and what the difference is in java. But i dont see a key in an hashset? the hashfunction calculates the hashcode from the data object? but wheres the key here.. – Ubuntix Feb 06 '14 at 14:46

1 Answers1

4

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
Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
  • I have a doubt. "Find all entries which have the same hash code"- same hash code will cause collision while entering. So in case if some collision resolution techniques like linked list is used, will we get many entries or one? – pratim_b Feb 06 '14 at 14:07
  • @techG: Many. An entry consists of {key, value, hash}. Several entries can have the same hash, and many entries can have the same value (which isn't even detectable easily), but there'll only ever be one entry for a particular key. – Jon Skeet Feb 06 '14 at 14:12