如何被散列映射在內部使用鏈表或陣列

Question

Java實現如何被散列映射內部實現？我在某處讀到它使用鏈表，而在某些地方它被稱爲數組。

我想攻讀的HashSet的代碼，發現進入陣列，那麼這裏就是鏈表使用

Answer 1

它基本上是這樣的：

this is the main array 
    ↓ 
[Entry] → Entry → Entry  ← here is the linked-list 
[Entry] 
[Entry] → Entry 
[Entry] 
[null ] 
[null ] 

所以，你必須在主數組，其中每個索引對應於一些散列值（mod'ed *爲數組的大小）。

然後他們每個人都會指向相同的哈希值（再次mod「版。*）的下一個條目。這是鏈表進入的地方。

*：作爲技術說明，it's first hashed with a different function之前是mod'編輯，但作爲一個基本的實現，只是modding會起作用。

Answer 2

散列表的條目存儲在「桶」中：每個散列表都有一個Array，並且在該Array中根據關鍵碼散列碼（例如position = hashcode％arraysize）將條目放置在一個位置。

如果不止一個條目在同一個桶的條目存儲在一個鏈表結束（見Dukelings答案）。因此，桶比喻：每個數組條目是一個「桶」，你只需要在所有匹配鍵中轉儲。

你，因爲你需要在這個列表訪問隨機位置使用的桶陣列以獲得deried「固定時間」的行爲。而內鬥，你必須遍歷所有元素，直到反正findeing所需的密鑰，所以你可以使用一個鏈表，因爲它更容易追加到（無需調整大小）。

這也顯示了良好的散列函數的需要，因爲如果所有的鍵散列到只有幾個值，你會得到龍鏈表來搜索和大量的（快速訪問）空水桶。

Answer 3

HashMap具有HashMap.Entry對象的數組：

/** 
* The table, resized as necessary. Length MUST Always be a power of two. 
*/ 
transient Entry<K,V>[] table; 

我們可以說是進入一個單向鏈表（例如HashMap.Entry聯動被稱爲「鬥」），但它實際上不是一個java.util.LinkedList。

見自己：

static class Entry<K,V> implements Map.Entry<K,V> { 
     final K key; 
     V value; 
     Entry<K,V> next; 
     int hash; 

     /** 
     * Creates new entry. 
     */ 
     Entry(int h, K k, V v, Entry<K,V> n) { 
      value = v; 
      next = n; 
      key = k; 
      hash = h; 
     } 

     public final K getKey() { 
      return key; 
     } 

     public final V getValue() { 
      return value; 
     } 

     public final V setValue(V newValue) { 
      V oldValue = value; 
      value = newValue; 
      return oldValue; 
     } 

     public final boolean equals(Object o) { 
      if (!(o instanceof Map.Entry)) 
       return false; 
      Map.Entry e = (Map.Entry)o; 
      Object k1 = getKey(); 
      Object k2 = e.getKey(); 
      if (k1 == k2 || (k1 != null && k1.equals(k2))) { 
       Object v1 = getValue(); 
       Object v2 = e.getValue(); 
       if (v1 == v2 || (v1 != null && v1.equals(v2))) 
        return true; 
      } 
      return false; 
     } 

     public final int hashCode() { 
      return (key==null ? 0 : key.hashCode())^
        (value==null ? 0 : value.hashCode()); 
     } 

     public final String toString() { 
      return getKey() + "=" + getValue(); 
     } 

     /** 
     * This method is invoked whenever the value in an entry is 
     * overwritten by an invocation of put(k,v) for a key k that's already 
     * in the HashMap. 
     */ 
     void recordAccess(HashMap<K,V> m) { 
     } 

     /** 
     * This method is invoked whenever the entry is 
     * removed from the table. 
     */ 
     void recordRemoval(HashMap<K,V> m) { 
     } 
    } 

Answer 4

HashMap的內部使用條目來存儲鍵值對。條目屬於LinkedList類型。

條目包含以下 - >

K鍵，

V值和

條目下一個>即在桶的該位置下一個條目。

static class Entry<K, V> { 
    K key; 
    V value; 
    Entry<K,V> next; 

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

的HashMap圖 -

來源：http://www.javamadesoeasy.com/2015/02/hashmap-custom-implementation.html