Search code examples
javadata-structureshashtable

If Hashtables use separate chaining, why are duplicate keys not possible?

So I'm a bit confused about this one. If Hashtables use separate chaining (or linear probing), why won't the following print out both values?

         Hashtable<Character, Integer> map = new Hashtable<>();
         map.put('h', 0);
         map.put('h', 1);
         System.out.println(map.remove('h')); // outputs 1
         System.out.println(map.get('h')); // outputs null

I'm trying to understand why, given 2 identical keys, the hashtable won't use separate chaining in order to store both values. Did I understand this somewhat incorrectly or has Java just not implemented collision handling in their hashtable class?

Another question that might tie together would be, how does a hashtable using linear probing, given a key, know which value is the one we are looking for?

Thanks in advance!

Solution

  • I'm trying to understand why, given 2 identical keys, the hashtable won't use separate chaining in order to store both values.

    The specification for Map (i.e. the javadoc) says that only one value is stored for each key. So that's what HashTable and HashMap implementations do.

    Certainly the separate chaining doesn't stop someone from implementing a hash table with that property. The pseudo-code for put(key, value) on a hash table with separate chaining is broadly as follows:

    1. Compute the hash value for the key.
    2. Compute an index in the array of hash chains from the hash value. (The computation is index = hash % array.length or something similar.)
    3. Search the hash chain at the computed index for an entry that matches the key.
    4. If you found the entry for the key on the chain, update the value in the entry.
    5. If you didn't find the entry, create an entry and add it to the chain.

    If you repeat that for the same key, you will compute the same hash value, search the same chain, and find the same entry. You then update it, and there is still only one entry for that key ... as required by the specification.

    In short, the above algorithm has no problem meeting the Map.put API requirements.