HashMap是最常用的集合類框架之一，它實現(xiàn)了Map接口，所以存儲的元素也是鍵值對映射的結(jié)構(gòu)，并允許使用null值和null鍵，其內(nèi)元素是無序的，如果要保證有序，可以使用LinkedHashMap。HashMap是線程不安全的，下篇文章會討論。HashMap的類關(guān)系如下：

　　　　java.util?

　　　　Class HashMap<K,V>

　　　　　　java.lang.Object

??　　　　　　　　|--java.util.AbstractMap<K,V>

????　　　　　　　　　　??|--java.util.HashMap<K,V>

所有已實現(xiàn)的接口：

　　Serializable,Cloneable,Map<K,V>

直接已知子類：

　　LinkedHashMap,PrinterStateReasons

　　HashMap中用的最多的方法就屬put() 和 get() 方法；HashMap的Key值是唯一的，那如何保證唯一性呢？我們首先想到的是用equals比較，沒錯，這樣可以實現(xiàn)，但隨著內(nèi)部元素的增多，put和get的效率將越來越低，這里的時間復(fù)雜度是O(n)，假如有1000個元素，put時最差情況需要比較1000次。實際上，HashMap很少會用到equals方法，因為其內(nèi)通過一個哈希表管理所有元素，哈希是通過hash單詞音譯過來的，也可以稱為散列表，哈希算法可以快速的存取元素，當(dāng)我們調(diào)用put存值時，HashMap首先會調(diào)用Key的hash方法，計算出哈希碼，通過哈希碼快速找到某個存放位置（桶），這個位置可以被稱之為bucketIndex，但可能會存在多個元素找到了相同的bucketIndex，有個專業(yè)名詞叫碰撞，當(dāng)碰撞發(fā)生時，這時會取到bucketIndex位置已存儲的元素，最終通過equals來比較，equals方法就是碰撞時才會執(zhí)行的方法，所以前面說HashMap很少會用到equals。HashMap通過hashCode和equals最終判斷出Key是否已存在，如果已存在，則使用新Value值替換舊Value值，并返回舊Value值，如果不存在?，則存放新的鍵值對<K, V>到bucketIndex位置。通過下面的流程圖來梳理一下整個put過程。

最終HashMap的存儲結(jié)構(gòu)會有這三種情況，我們當(dāng)然期望情形3是最少發(fā)生的（效率最低）。

?

HashMap 碰撞問題處理：

　　碰撞：所謂“碰撞”就上面所述是多個元素計算得出相同的hashCode，在put時出現(xiàn)沖突。

　　處理方法：

　　Java中HashMap是利用“拉鏈法”處理HashCode的碰撞問題。在調(diào)用HashMap的put方法或get方法時，都會首先調(diào)用hashcode方法，去查找相關(guān)的key，當(dāng)有沖突時，再調(diào)用equals方法。hashMap基于hasing原理，我們通過put和get方法存取對象。當(dāng)我們將鍵值對傳遞給put方法時，他調(diào)用鍵對象的hashCode()方法來計算hashCode，然后找到bucket（哈希桶）位置來存儲對象。當(dāng)獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象。HashMap使用鏈表來解決碰撞問題，當(dāng)碰撞發(fā)生了，對象將會存儲在鏈表的下一個節(jié)點中。hashMap在每個鏈表節(jié)點存儲鍵值對對象。當(dāng)兩個不同的鍵卻有相同的hashCode時，他們會存儲在同一個bucket位置的鏈表中。鍵對象的equals()來找到鍵值對。

?HashMap基本結(jié)構(gòu)概念圖：

?

到目前為止，我們了解了兩件事：

　　1、HashMap通過鍵的hashCode來快速的存取元素。

　　2、當(dāng)不同的對象發(fā)生碰撞時，HashMap通過單鏈表來解決，將新元素加入鏈表表頭，通過next指向原有的元素。單鏈表在Java中的實現(xiàn)就是對象的引用(復(fù)合)。

?

?HashMap.put()和get()源碼：

/** * Returns the value to which the specified key is mapped, * or if this map contains no mapping for the key. * * 獲取key對應(yīng)的value */ public V get(Object key) { if (key == null) return getForNullKey(); //獲取key的hash值 int hash = hash(key.hashCode()); // 在“該hash值對應(yīng)的鏈表”上查找“鍵值等于key”的元素 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; } /** * Offloaded version of get() to look up null keys. Null keys map * to index 0. * 獲取key為null的鍵值對，HashMap將此鍵值對存儲到table[0]的位置 */ private V getForNullKey() { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; } /** * Returns <tt>true</tt> if this map contains a mapping for the * specified key. * * HashMap是否包含key */ public boolean containsKey(Object key) { return getEntry(key) != null; } /** * Returns the entry associated with the specified key in the * HashMap. * 返回鍵為key的鍵值對 */ final Entry<K,V> getEntry(Object key) { //先獲取哈希值。如果key為null，hash = 0；這是因為key為null的鍵值對存儲在table[0]的位置。 int hash = (key == null) ? 0 : hash(key.hashCode()); //在該哈希值對應(yīng)的鏈表上查找鍵值與key相等的元素。 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; } /** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * 將“key-value”添加到HashMap中，如果hashMap中包含了key，那么原來的值將會被新值取代 */ public V put(K key, V value) { //如果key是null，那么調(diào)用putForNullKey(),將該鍵值對添加到table[0]中 if (key == null) return putForNullKey(value); //如果key不為null，則計算key的哈希值，然后將其添加到哈希值對應(yīng)的鏈表中 int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; //如果這個key對應(yīng)的鍵值對已經(jīng)存在，就用新的value代替老的value。 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; }

從HashMap的put()和get方法實現(xiàn)中可以與拉鏈法解決hashCode沖突解決方法相互印證。并且從put方法中可以看出HashMap是使用Entry<K,V>來存儲數(shù)據(jù)。

?

?

?

?

?

?

總結(jié)

以上是生活随笔為你收集整理的HashMap碰撞问题解析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。