摘要：這樣做的目的是提高取對象的效率。在單線程情況下效率較高在的多線程情況下，同步操作能保證程序執行的正確性。

突然發現整理了很多筆記，應該放這里做備用

主要區別：線程安全性，同步(synchronization)，以及速度。

HashMap幾乎可以等價于Hashtable，除了HashMap是非synchronized的，并可以接受null。Hashtable是線程安全的，多個線程可以共享一個Hashtable。

HashMap的同步問題可通過Collections的一個靜態方法得到解決，Map Collections.synchronizedMap(Map m) 返回一個同步的Map。

HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。fail-fast結構上更改時（刪除或者插入一個元素），將會拋出ConcurrentModificationException異常。

HashMap不能保證隨著時間的推移Map中的元素次序是不變的。

HashSet實現了Set接口，它不允許集合中有重復的值，當我們提到HashSet時，第一件事情就是在將對象存儲在HashSet之前，要先確保對象重寫equals()和hashCode()方法，這樣才能比較對象的值是否相等，以確保set中沒有儲存相等的對象。如果我們沒有重寫這兩個方法，將會使用這個方法的默認實現。

Map中不允許重復的鍵。Map接口有兩個基本的實現，HashMap和TreeMap。TreeMap保存了對象的排列次序，而HashMap則不能。HashMap允許鍵和值為null。

HashSet 和 HashMap 之間有很多相似之處，對于 HashSet 而言，系統采用 Hash 算法決定集合元素的存儲位置，這樣可以保證能快速存、取集合元素；對于 HashMap 而言，系統 key-value 當成一個整體進行處理，系統總是根據 Hash 算法來計算 key-value 的存儲位置，這樣可以保證能快速存、取 Map 的 key-value 對。

public V put(K key, V value) {   
    // 如果 key 為 null，調用 putForNullKey 方法進行處理  
    if (key == null)   
        return putForNullKey(value);   
    // 根據 key 的 keyCode 計算 Hash 值  
    int hash = hash(key.hashCode());   
    // 搜索指定 hash 值在對應 table 中的索引  
    int i = indexFor(hash, table.length);  
    // 如果 i 索引處的 Entry 不為 null，通過循環不斷遍歷 e 元素的下一個元素  
    for (Entry e = table[i]; e != null; e = e.next)   
    {   
        Object k;   
        // 找到指定 key 與需要放入的 key 相等（hash 值相同  
        // 通過 equals 比較放回 true）  
        if (e.hash == hash && ((k = e.key) == key   
            || key.equals(k)))   
        {   
            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;   
}  

Map.Entry，每個 Map.Entry 其實就是一個 key-value 對。

當系統決定存儲 HashMap 中的 key-value 對時，完全沒有考慮 Entry 中的 value，僅僅只是根據 key 來計算并決定每個 Entry 的存儲位置?？梢园?Map 集合中的 value 當成 key 的附屬。

indexFor(int h, int length) 方法來計算該對象應該保存在 table 數組的哪個索引處。

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

Map提供了一些常用方法，如keySet()、entrySet()等方法，keySet()方法返回值是Map中key值的集合；entrySet()的返回值也是返回一個Set集合，此集合的類型為Map.Entry，接口中有getKey()、getValue方法。

HashMap實際上是一個“鏈表散列”的數據結構，即數組和鏈表的結構，但是在jdk1.8里 ，加入了紅黑樹的實現，當鏈表的長度大于8時，轉換為紅黑樹的結構。

少于8個的時候，Java中HashMap采用了鏈地址法。

通過什么方式來控制map使得Hash碰撞的概率又小，哈希桶數組（Node[] table）占用空間又少呢？答案就是好的Hash算法和擴容機制。即使負載因子和Hash算法設計的再合理，也免不了會出現拉鏈過長的情況，一旦出現拉鏈過長，則會嚴重影響HashMap的性能。

而當鏈表長度太長（默認超過8）時，鏈表就轉換為紅黑樹，利用紅黑樹快速增刪改查的特點提高HashMap的性能。

indexFor方法一般想到的是把hash值對數組長度取模運算，但運算較大，因此1.7中使用以下方法，&比%具有更高的效率：

static int indexFor(int h, int length) { 
     return h & (length-1);  //第三步 取模運算
}

在JDK1.8的實現中，優化了高位運算的算法：(h = k.hashCode()) ^ (h >>> 16)

紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹。紅黑樹和AVL樹一樣都對插入時間、刪除時間和查找時間提供了最好可能的最壞情況擔保。除了O(log n)的時間之外，紅黑樹的持久版本對每次插入或刪除需要O(log n)的空間。

兩個obj，如果equals()相等，hashCode()一定相等。
兩個obj，如果hashCode()相等，equals()不一定相等（Hash散列值有沖突的情況，雖然概率很低）。

equals()和hashcode()這兩個方法都是從object類中繼承過來的。equals()是對兩個對象的地址值進行的比較（即比較引用是否相同），hashCode()是一個本地方法，它的實現是根據本地機器相關的。

JVM每new一個Object,它都會將這個Object丟到一個Hash哈希表中去,這樣的話,下次做Object的比較或者取這個對象的時候,它會根據對象的hashcode再從Hash表中取這個對象。這樣做的目的是提高取對象的效率。

如果不同的對象確產生了相同的hash值,也就是發生了Hash key相同導致沖突的情況,那么就在這個Hash key的地方產生一個鏈表,將所有產生相同hashcode的對象放到這個單鏈表上去,串在一起。比較兩個對象的時候,首先根據他們的hashcode去hash表中找他的對象，當兩個對象的hashcode相同，只能根據Object的equal方法來比較這個對象是否equal。

Object的equal方法默認是兩個對象的引用的比較，意思就是指向同一內存。

但是，String對象中equals方法是判斷值的，而==是地址判斷（因為JDK重寫了）。

我們很大部分時間都是進行兩個對象的比較（而不是比較引用），這個時候Object的equals()方法就不可以了，所以才會有String這些類對equals方法的改寫，依次類推Double、Integer、Math等等這些類都是重寫了equals()方法的，從而進行的是內容的比較。

java.lnag.Object中對hashCode的約定：

在一個應用程序執行期間，如果一個對象的equals方法做比較所用到的信息沒有被修改的話，則對該對象調用hashCode方法多次，它必須始終如一地返回同一個整數。

如果兩個對象根據equals(Object o)方法是相等的，則調用這兩個對象中任一對象的hashCode方法必須產生相同的整數結果。

如果兩個對象根據equals(Object o)方法是不相等的，則調用這兩個對象中任一個對象的hashCode方法，不要求產生不同的整數結果。但如果能不同，則可能提高散列表的性能。

只要改寫了就會違約，所以要繼續改寫。

ConcurrentHashMap融合了hashtable和hashmap二者的優勢。hashmap在單線程情況下效率較高；hashtable在的多線程情況下，同步操作能保證程序執行的正確性。

hashtable每次同步執行的時候都要鎖住整個結構：

ConcurrentHashMap鎖的方式是稍微細粒度的。

更令人驚訝的是ConcurrentHashMap的讀取并發，因為在讀取的大多數時候都沒有用到鎖定，所以讀取操作幾乎是完全的并發操作，而寫操作鎖定的粒度又非常細，比起之前又更加快速（這一點在桶更多時表現得更明顯些）。只有在求size等操作時才需要鎖定整個表。

在迭代時，使用弱一致迭代器，不再是拋出 ConcurrentModificationException，在改變時new新的數據從而不影響原有的數據，iterator完成后再將頭指針替換為新的數據。

答：“HashMap是基于hashing的原理，我們使用put(key, value)存儲對象到HashMap中，使用get(key)從HashMap中獲取對象。當我們給put()方法傳遞鍵和值時，我們先對鍵調用hashCode()方法，返回的hashCode用于找到bucket位置來儲存Entry對象?！?/p>

關鍵：HashMap是在bucket中儲存鍵對象和值對象，作為Map.Entry。

因為hashcode相同，所以它們的bucket位置相同，發生沖突，Entry(包含有鍵值對的Map.Entry對象)會存儲在鏈表中。

遍歷鏈表直到找到Entry對象，找到bucket位置之后，會調用keys.equals()方法去找到鏈表中正確的節點。

默認的負載因子大小為0.75，將會創建原來HashMap大小的兩倍的bucket數組，來重新調整map的大?。╮ehashing）。當多線程的情況下，可能產生條件競爭(race condition)，兩個線程都發現HashMap需要重新調整大小了，它們會同時試著調整大小。

先這樣吧

若有錯誤之處請指出，更多地關注煎魚。