實現自定義HashMap代碼問題

Question

我正在準備自己的Java自定義HashMap實現。以下是我的強項。

public class Entry<K,V> { 

private final K key; 
private V value; 
private Entry<K,V> next; 

public Entry(K key, V value, Entry<K,V> next) { 
    this.key = key; 
    this.value = value; 
    this.next = next; 
} 

public V getValue() { 
    return value; 
} 

public void setValue(V value) { 
    this.value = value; 
} 

public Entry<K, V> getNext() { 
    return next; 
} 

public void setNext(Entry<K, V> next) { 
    this.next = next; 
} 

public K getKey() { 
    return key; 
} 
} 



public class MyCustomHashMap<K,V> { 

    private int DEFAULT_BUCKET_COUNT = 10; 

    private Entry<K,V>[] buckets; 

    public MyCustomHashMap() { 
     buckets = new Entry[DEFAULT_BUCKET_COUNT]; 
     for (int i = 0;i<DEFAULT_BUCKET_COUNT;i++) 
      buckets[i] = null;  
    } 

    public void put(K key,V value){ 

     /** 
     * This is the new node. 
     */ 
     Entry<K,V> newEntry = new Entry<K,V>(key, value, null); 

     /** 
     * If key is null, then null keys always map to hash 0, thus index 0 
     */ 
     if(key == null){ 
      buckets[0] = newEntry; 
     } 

     /** 
     * get the hashCode of the key. 
     */ 
     int hash = hash(key); 

     /** 
     * if the index does of the bucket does not contain any element then assign the node to the index. 
     */ 
     if(buckets[hash] == null) { 
      buckets[hash] = newEntry; 
     } else { 

      /** 
      * we need to traverse the list and compare the key with each of the keys till the keys match OR if the keys does not match then we need 
      * to add the node at the end of the linked list. 
      */ 

      Entry<K,V> previous = null; 
      Entry<K,V> current = buckets[hash]; 

      while(current != null) { 

       boolean done = false; 

       while(!done) { 

        if(current.getKey().equals(key)) { 
         current.setValue(value); 
         done = true; // if the keys are same then replace the old value with the new value; 
        } else if (current.getNext() == null) { 
         current.setNext(newEntry); 
         done = true; 
        }     
        current = current.getNext(); 
        previous = current; 
       } 
      } 
      previous.setNext(newEntry); 
     } 


    } 

    public V getKey(K key) { 

     int hash = hash(key); 

     if(buckets[hash] == null) { 
      return null; 
     } else { 
      Entry<K,V> temp = buckets[hash]; 
      while(temp != null) { 
       if(temp.getKey().equals(key)) 
        return temp.getValue(); // returns value corresponding to key. 
       temp = temp.getNext(); 
      } 
      return null; //return null if key is not found. 
     } 

    } 


    public void display() { 

     for(int i = 0; i < DEFAULT_BUCKET_COUNT; i++) { 

      if(buckets[i] != null) { 
       Entry<K,V> entry = buckets[i]; 

       while(entry != null){ 
        System.out.print("{"+entry.getKey()+"="+entry.getValue()+"}" +" "); 
        entry=entry.getNext(); 
       } 
      } 
     } 
    } 

    public int bucketIndexForKey(K key) { 
     int bucketIndex = key.hashCode() % buckets.length; 
     return bucketIndex; 
    } 


    /** 
     * 
     * @param key 
     * @return 
     */ 
    private int hash(K key){ 
     return Math.abs(key.hashCode()) % buckets.length; 
    } 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     MyCustomHashMap<String, Integer> myCustomHashMap = new MyCustomHashMap<String, Integer>(); 
     myCustomHashMap.put("S", 22); 
     myCustomHashMap.put("S", 1979); 
     myCustomHashMap.put("V", 5); 
     myCustomHashMap.put("R", 31); 


     System.out.println("Value corresponding to key R: "+myCustomHashMap.getKey("R")); 

     System.out.println("Value corresponding to key V: "+myCustomHashMap.getKey("V")); 

     System.out.println("Displaying the contents of the HashMap:: "); 

     myCustomHashMap.display(); 

    } 

} 

1）我覺得放（K鍵，V值）有點缺陷。請確認並讓我知道這裏有什麼問題。在輸入相同的密鑰時，它給了我錯誤的結果。我還沒有測試過具有不同密鑰的碰撞情況。

2）據說我們重新哈希hashCode，以便它消除了hashCode的錯誤實現。我該怎麼做，因爲如果我給密鑰hashCode即hash（key.hashCode（）），那麼它不會考慮，因爲它不能計算int的hashCode。這個怎麼做？

任何幫助將不勝感激。

感謝 希德

Answer 1

1. 您沒有正確處理空鍵：

   if(key == null){ 
       buckets[0] = newEntry; 
   } 
   

這有可能是buckets[0]已經包含條目，在這種情況下，你將失去這些條目。

下面的循環有一些問題：

Entry<K,V> previous = null; 
    Entry<K,V> current = buckets[hash]; 

    while(current != null) { 

     boolean done = false; 

     while(!done) { 

      if(current.getKey().equals(key)) { 
       current.setValue(value); 
       done = true; 
      } else if (current.getNext() == null) { 
       current.setNext(newEntry); 
       done = true; 
      }     
      current = current.getNext(); 
      previous = current; // you are not really setting previous to 
           // to the previous Entry in the list - you 
           // are setting it to the current Entry 
     } 
    } 
    previous.setNext(newEntry); // you don't need this statement. You 
           // already have a statement inside the 
           // loop that adds the new Entry to the list 

它看起來像移除相關previous將修復這個循環任何聲明。

編輯：

由於kolakao評論說，爲了讓您的實現有效率（即需要預期恆定的時間爲get和put），當條目數超過某個閾值，你必須調整HashMap（以每個桶中的平均條目數量由常數限定）。

據說我們重新哈希hashCode，以便它消除了hashCode的錯誤實現。我該怎麼做，因爲如果我給密鑰hashCode即hash（key.hashCode（）），那麼它不會考慮，因爲它不能計算int的hashCode。這個怎麼做？

重新哈希的想法不涉及調用hashCode的密鑰hashCode。它涉及對由key.hashCode()獲得的值運行一些硬編碼函數。

例如，在Java 7實施HashMap，下面的函數：

static int hash(int h) { 
    // This function ensures that hashCodes that differ only by 
    // constant multiples at each bit position have a bounded 
    // number of collisions (approximately 8 at default load factor). 
    h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
} 

然後你使用它：

int hash = hash(key.hashCode()); 
int bucket = hash % buckets.length;