Is there a way to handle collisions in a HashTable such that a key is not associated with a value?

Question

I am implementing a class with the following header

public class HashTable<K,V>

To handle collisions I am using separate chaining with linked lists. However, is there a way to implement a method to get a value given a key such as

public V get(K key)

without knowing that V has a method that gets its key (since it is generic)? What I cannot see is how to know which value in the linked list to return if a key hashes to the same index in the array, i.e., what to return in the case of a collision.

Answer 1

Since you are passing the key and value pair for the insertion you can store both in the table.

Implement the HashTable using array of Linked list. In each node of the LinkedList store the (key, value) pair as a single object. You will be hashing the key and store (key, value) pair object in the hashvalue location. The object can be like the below one,

public static class WrapObject
{
    K key;
    V value;
    public WrapObject(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

And in get(K key) method , hash the key and iterate through all the (key, value) pair objects in the hashvalue location then return the value for the key.

The following code snippet shows how to do it,

    LinkedList<WrapObject>[] arrList = new LinkedList[10001];
public V get(K key)
{
    int hashValue=hash(key);
    if(arrList[hashValue]==null)
    {
        return null;
    }
    LinkedList<WrapObject> lList = arrList[ hashValue ];
    for(WrapObject obj : lList)
    {

        if((obj.key).compareTo(key)==0)
        {
            return obj.value;
        }
    }
    return null;
}

Answer 2

You need to use both the hashcode and equals method.

Use the hashcode method to find the proper list, and then use the equals method to find the exact match.

If for example K1 and K2 have the same hashcode, then they will end up on the same list. When you later do your get with K2 you will have to iterate over the list looking for entry whose key.equals(K2).