摘要：根據(jù)的重新計(jì)算值。如果這兩個的通過比較返回，新添加的將覆蓋集合中原有的，但不會覆蓋。如果這兩個的通過比較返回，新添加的將與集合中原有形成鏈，而且新添加的位于鏈的頭部具體說明繼續(xù)看方法的說明。

hashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，hashCode是用來在散列存儲結(jié)構(gòu)中確定對象的存儲地址的.

1.hashcode是用來查找的，如果你學(xué)過數(shù)據(jù)結(jié)構(gòu)就應(yīng)該知道，在查找和排序這一章有
例如內(nèi)存中有這樣的位置
0  1  2  3  4  5  6  7 
而我有個類，這個類有個字段叫ID,我要把這個類存放在以上8個位置之一，如果不用hashcode而任意存放，那么當(dāng)查找時就需要到這八個位置里挨個去找，或者用二分法一類的算法。
但如果用hashcode那就會使效率提高很多。
我們這個類中有個字段叫ID,那么我們就定義我們的hashcode為ID％8，然后把我們的類存放在取得得余數(shù)那個位置。比如我們的ID為9，9除8的余數(shù)為1，那么我們就把該類存在1這個位置，如果ID是13，求得的余數(shù)是5，那么我們就把該類放在5這個位置。這樣，以后在查找該類時就可以通過ID除 8求余數(shù)直接找到存放的位置了。
2.但是如果兩個類有相同的hashcode怎么辦那（我們假設(shè)上面的類的ID不是唯一的），例如9除以8和17除以8的余數(shù)都是1，那么這是不是合法的，回答是：可以這樣。那么如何判斷呢？在這個時候就需要定義 equals了。
也就是說，我們先通過 hashcode來判斷兩個類是否存放某個桶里，但這個桶里可能有很多類，那么我們就需要再通過 equals 來在這個桶里找到我們要的類。
那么。重寫了equals()，為什么還要重寫hashCode()呢？
想想，你要在一個桶里找東西，你必須先要找到這個桶啊，你不通過重寫hashcode()來找到桶，光重寫equals()有什么用啊

HashMap概述

HashMap是基于哈希表的Map接口的非同步實(shí)現(xiàn)。此實(shí)現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。
在java編程語言中，最基本的結(jié)構(gòu)就是兩種，一個是數(shù)組，另外一個是模擬指針（引用），所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個基本結(jié)構(gòu)來構(gòu)造的，HashMap也不例外。HashMap實(shí)際上是一個“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體。

內(nèi)部存儲

HashMap的內(nèi)部存儲是一個數(shù)組（bucket），數(shù)組的元素Node實(shí)現(xiàn)了是Map.Entry接口(hash, key, value, next)，next非空時指向定位相同的另一個Entry，如圖：

hashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，hashCode是用來在散列存儲結(jié)構(gòu)中確定對象的存儲地址的.

1.hashcode是用來查找的，如果你學(xué)過數(shù)據(jù)結(jié)構(gòu)就應(yīng)該知道，在查找和排序這一章有
例如內(nèi)存中有這樣的位置
0  1  2  3  4  5  6  7 
而我有個類，這個類有個字段叫ID,我要把這個類存放在以上8個位置之一，如果不用hashcode而任意存放，那么當(dāng)查找時就需要到這八個位置里挨個去找，或者用二分法一類的算法。
但如果用hashcode那就會使效率提高很多。
我們這個類中有個字段叫ID,那么我們就定義我們的hashcode為ID％8，然后把我們的類存放在取得得余數(shù)那個位置。比如我們的ID為9，9除8的余數(shù)為1，那么我們就把該類存在1這個位置，如果ID是13，求得的余數(shù)是5，那么我們就把該類放在5這個位置。這樣，以后在查找該類時就可以通過ID除 8求余數(shù)直接找到存放的位置了。
2.但是如果兩個類有相同的hashcode怎么辦那（我們假設(shè)上面的類的ID不是唯一的），例如9除以8和17除以8的余數(shù)都是1，那么這是不是合法的，回答是：可以這樣。那么如何判斷呢？在這個時候就需要定義 equals了。
也就是說，我們先通過 hashcode來判斷兩個類是否存放某個桶里，但這個桶里可能有很多類，那么我們就需要再通過 equals 來在這個桶里找到我們要的類。
那么。重寫了equals()，為什么還要重寫hashCode()呢？
想想，你要在一個桶里找東西，你必須先要找到這個桶啊，你不通過重寫hashcode()來找到桶，光重寫equals()有什么用啊

HashMap概述

HashMap是基于哈希表的Map接口的非同步實(shí)現(xiàn)。此實(shí)現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。
在java編程語言中，最基本的結(jié)構(gòu)就是兩種，一個是數(shù)組，另外一個是模擬指針（引用），所有的數(shù)據(jù)結(jié)構(gòu)都可以用這兩個基本結(jié)構(gòu)來構(gòu)造的，HashMap也不例外。HashMap實(shí)際上是一個“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體。

內(nèi)部存儲

HashMap的內(nèi)部存儲是一個數(shù)組（bucket），數(shù)組的元素Node實(shí)現(xiàn)了是Map.Entry接口(hash, key, value, next)，next非空時指向定位相同的另一個Entry，如圖：

存儲

public V put(K key, V value) {
      // HashMap允許存放null鍵和null值。
     // 當(dāng)key為null時，調(diào)用putForNullKey方法，將value放置在數(shù)組第一個位置。
     if (key == null)
         return putForNullKey(value);
     // 根據(jù)key的keyCode重新計(jì)算hash值。
     int hash = hash(key.hashCode());
     // 搜索指定hash值在對應(yīng)table中的索引。
     int i = indexFor(hash, table.length);
     // 如果 i 索引處的 Entry 不為 null，通過循環(huán)不斷遍歷 e 元素的下一個元素。
     for (Entry e = table[i]; e != null; e = e.next) {
         Object k;
         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
             // 如果發(fā)現(xiàn)已有該鍵值，則存儲新的值，并返回原始值
             V oldValue = e.value;
             e.value = value;
             e.recordAccess(this);
             return oldValue;
         }
     }
     // 如果i索引處的Entry為null，表明此處還沒有Entry。
     modCount++;
     // 將key、value添加到i索引處。
     addEntry(hash, key, value, i);
     return null;
 }

根據(jù)hash值得到這個元素在數(shù)組中的位置（即下標(biāo)），如果數(shù)組該位置上已經(jīng)存放有其他元素了，那么在這個位置上的元素將以鏈表的形式存放，新加入的放在鏈頭，最先加入的放在鏈尾。如果數(shù)組該位置上沒有元素，就直接將該元素放到此數(shù)組中的該位置上。
hash(int h)方法根據(jù)key的hashCode重新計(jì)算一次散列。此算法加入了高位計(jì)算，防止低位不變，高位變化時，造成的hash沖突。

 static int hash(int h) {
     h ^= (h >>> 20) ^ (h >>> 12);
     return h ^ (h >>> 7) ^ (h >>> 4);
 }

HashMap中要找到某個元素，需要根據(jù)key的hash值來求得對應(yīng)數(shù)組中的位置。如何計(jì)算這個位置就是hash算法。前面說過HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合，所以我們當(dāng)然希望這個HashMap里面的元素位置盡量的分布均勻些，盡量使得每個位置上的元素?cái)?shù)量只有一個，那么當(dāng)我們用hash算法求得這個位置的時候，馬上就可以知道對應(yīng)位置的元素就是我們要的，而不用再去遍歷鏈表，這樣就大大優(yōu)化了查詢的效率。

根據(jù)上面 put 方法的源代碼可以看出，當(dāng)程序試圖將一個key-value對放入HashMap中時，程序首先根據(jù)該 key的 hashCode() 返回值決定該 Entry 的存儲位置：如果兩個 Entry 的 key 的 hashCode() 返回值相同，那它們的存儲位置相同。如果這兩個 Entry 的 key 通過 equals 比較返回 true，新添加 Entry 的 value 將覆蓋集合中原有 Entry的 value，但key不會覆蓋。如果這兩個 Entry 的 key 通過 equals 比較返回 false，新添加的 Entry 將與集合中原有 Entry 形成 Entry 鏈，而且新添加的 Entry 位于 Entry 鏈的頭部——具體說明繼續(xù)看 addEntry() 方法的說明。

具體如何根據(jù)hash計(jì)算下標(biāo)呢，參見

JDK 源碼中 HashMap 的 hash 方法原理是什么？

獲取

 public V get(Object key) {
     if (key == null)
         return getForNullKey();
     int hash = hash(key.hashCode());
     for (Entry 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;
 }

從HashMap中g(shù)et元素時，首先計(jì)算key的hashCode，找到數(shù)組中對應(yīng)位置的某一元素，然后通過key的equals方法在對應(yīng)位置的鏈表中找到需要的元素。

HashMap的resize

當(dāng)hashmap中的元素越來越多的時候，碰撞的幾率也就越來越高（因?yàn)閿?shù)組的長度是固定的），所以為了提高查詢的效率，就要對hashmap的數(shù)組進(jìn)行擴(kuò)容，數(shù)組擴(kuò)容這個操作也會出現(xiàn)在ArrayList中，所以這是一個通用的操作，很多人對它的性能表示過懷疑，不過想想我們的“均攤”原理，就釋然了，而在hashmap數(shù)組擴(kuò)容之后，最消耗性能的點(diǎn)就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計(jì)算其在新數(shù)組中的位置，并放進(jìn)去，這就是resize。
那么hashmap什么時候進(jìn)行擴(kuò)容呢？當(dāng)hashmap中的元素個數(shù)超過數(shù)組大小loadFactor時，就會進(jìn)行數(shù)組擴(kuò)容，loadFactor的默認(rèn)值為0.75，也就是說，默認(rèn)情況下，數(shù)組大小為16，那么當(dāng)hashmap中元素個數(shù)超過160.75=12的時候，就把數(shù)組的大小擴(kuò)展為216=32，即擴(kuò)大一倍，然后重新計(jì)算每個元素在數(shù)組中的位置，而這是一個非常消耗性能的操作，所以如果我們已經(jīng)預(yù)知hashmap中元素的個數(shù)，那么預(yù)設(shè)元素的個數(shù)能夠有效的提高h(yuǎn)ashmap的性能。比如說，我們有1000個元素new HashMap(1000), 但是理論上來講new HashMap(1024)更合適，不過上面annegu已經(jīng)說過，即使是1000，hashmap也自動會將其設(shè)置為1024。 但是new HashMap(1024)還不是更合適的，因?yàn)?.751000 < 1000, 也就是說為了讓0.75 * size > 1000, 我們必須這樣new HashMap(2048)才最合適，既考慮了&的問題，也避免了resize的問題。

1.8的優(yōu)化

Java8做的改變:
1.HashMap是數(shù)組+鏈表+紅黑樹(JDK1.8增加了紅黑樹部分),當(dāng)鏈表長度>=8時轉(zhuǎn)化為紅黑樹
在JDK1.8版本中,對數(shù)據(jù)結(jié)構(gòu)做了進(jìn)一步的優(yōu)化,引入了紅黑樹。而當(dāng)鏈表長度太長(默認(rèn)超過8)時，鏈表就轉(zhuǎn)換為紅黑樹，利用紅黑樹快速增刪改查的特點(diǎn)提高HashMap的性能，其中會用到紅黑樹的插入、刪除、查找等算法。

java8 中對hashmap護(hù)容不是重新計(jì)算所有元素在數(shù)組的位置，而是我們使用的是2次冪的擴(kuò)展(指長度擴(kuò)為原來2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移動2次冪的位置在擴(kuò)充HashMap的時候，不需要像JDK1.7的實(shí)現(xiàn)那樣重新計(jì)算hash,只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap"。

面試中通常被問到的。

HashMap高并發(fā)情況下會出現(xiàn)什么問題?

擴(kuò)容問題
HashMap的存放自定義類時，需要實(shí)現(xiàn)自定義類的什么方法?

hashCode和equals.通過hash(hashCode)然后模運(yùn)算(其實(shí)是與的位操作)定位在Entry數(shù)組中的下標(biāo)，然后遍歷這之后的鏈表，通過equals比較有沒有相同的key,如果有直接覆蓋value,如果沒有就重新創(chuàng)建一一個Entry。

hashmap為什么可以插入空值?

HashMap中添加key == null的Entry時會調(diào)用putForNullKey方法直接去遍歷table[0]Entry鏈表，尋找e.key == null的Entry或者沒有找到遍歷結(jié)束如果找到了e.key==null,就保存null值對應(yīng)的原值oldValue,然后覆蓋原值，并返回oldValue如果在table[O]Entrty鏈表中沒有找到就調(diào)用addEntry方法添加一個key為null的Entry

Hashmap 為什么線程不安全(hash 碰撞和擴(kuò)容導(dǎo)致)

HashMap擴(kuò)容的的時候可能會形成環(huán)形鏈表，造成死循環(huán)。