有沒有辦法處理HashTable中的衝突，使得一個鍵與一個值沒有關聯？

Question

我實現了一類具有下面的頭

public class HashTable<K,V> 

要處理，我使用分離鏈與鏈表的碰撞。然而，有沒有工具的方法的方式來獲得一個給定值的關鍵，如

public V get(K key) 

不知道V具有的是得到它的鍵（因爲它是通用）的方法？我看不到的是如何知道鏈表中的哪個值返回，如果一個鍵哈希到數組中的同一個索引，即在碰撞的情況下返回什麼。

Answer 1

由於您正在爲插入傳遞鍵和值對，因此可以將兩者都存儲在表中。

使用鏈表的數組實現HashTable。 LinkedList的每個節點都將（key，value）對存儲爲單個對象。您將散列密鑰並將其存儲（密鑰，值）對象置於散列值位置。該對象可以像下面的一個，

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

而在GET（K key）方法，散列密鑰和通過所有的（鍵，值）對在散列值位置對象迭代然後爲返回值鍵。

下面的代碼片段展示瞭如何做到這一點，

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

您需要同時使用hashcode和equals方法。

使用散列碼方法查找適當的列表，然後使用equals方法查找完全匹配。

如果例如K1和K2具有相同的哈希碼，則它們將在相同的列表上結束。當你以後用K2來獲得時，你將不得不遍歷列表尋找key.equals（K2）的條目。