map

image.png

HashMap:

image.png

JDK1.7
HashMap 里面是一個(gè)數(shù)組(transient Node<K,V>[] table)，然后數(shù)組中每個(gè)元素是一個(gè)單向鏈表,由Node內(nèi)部類實(shí)現(xiàn)；

數(shù)組的優(yōu)點(diǎn)是：
數(shù)組是順序存儲(chǔ)結(jié)構(gòu)，通過數(shù)組下標(biāo)可以快速實(shí)現(xiàn)對(duì)數(shù)組元素的訪問，效率極高；
數(shù)組的缺點(diǎn)是：
插入或刪除元素效率較低，因?yàn)榭赡苄枰獢?shù)組擴(kuò)容、移動(dòng)元素；

鏈表的優(yōu)點(diǎn)是：
鏈表是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，插入或刪除元素不需要移動(dòng)元素，只需要修改指向下一個(gè)節(jié)點(diǎn)的指針域，效率較高；
鏈表的缺點(diǎn)是：
鏈表訪問元素需要從頭到尾逐個(gè)遍歷，效率較低；

JDK1.8 hashMap優(yōu)化
1.數(shù)據(jù)存儲(chǔ)結(jié)構(gòu),1.8中,如果鏈表長(zhǎng)度超過了8,那么鏈表將轉(zhuǎn)換為紅黑樹(平衡二叉樹,TreeNode<K,V>),優(yōu)化鏈表的查詢速率,節(jié)點(diǎn)是根據(jù)hash值排序的

鏈表時(shí)的 復(fù)雜度為O(n),紅黑樹的時(shí)候O(log(n))

2.發(fā)生hash碰撞時(shí),1.7會(huì)在鏈表的頭部插入,而1.8會(huì)在鏈表的尾部插入
3.1.8中Entry被Node(實(shí)現(xiàn)Map.Entry接口)替代
4.hash的實(shí)現(xiàn),1.8中,是通過hashCode的高16位異或低16位實(shí)現(xiàn)的

(h = k.hashCode()) ^ (h >>> 16)

主要是從性能,hash碰撞來考慮,減少系統(tǒng)的開銷,也不會(huì)造成因?yàn)楦呶粵]有參與下表的計(jì)算,從而引起的碰撞(減少hash碰撞)

hash值的實(shí)現(xiàn)(JDK 1.8)

當(dāng)key為null時(shí),hash為0
其他key的hash為hashCode的高16位異或低16位,hash是32位
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

下標(biāo)的計(jì)算方式

i = (n - 1) & hash;//n為數(shù)組長(zhǎng)度

hashMap的擴(kuò)容
hashMap初始容量16,擴(kuò)容因子0.75,容量最大值2^30
如果當(dāng)HashMap的容量超過12時(shí),則進(jìn)行擴(kuò)容.
新建一個(gè)Node<K,V>[]數(shù)組,遍歷原數(shù)組數(shù)據(jù),賦值給新數(shù)組(需要重新計(jì)算每個(gè)元素的下標(biāo))
新hashMap容量為原Map的2倍

HashMap的put操作源碼分析
1、調(diào)用哈希函數(shù)獲取Key對(duì)應(yīng)的hash值，再計(jì)算其數(shù)組下標(biāo)；
2、如果沒有出現(xiàn)哈希沖突，則直接放入數(shù)組，如果出現(xiàn)哈希沖突，則以鏈表的方式放在鏈表后面；
3、如果鏈表長(zhǎng)度超過閥值( TREEIFY THRESHOLD==8)，就把鏈表轉(zhuǎn)成紅黑樹；
4、如果結(jié)點(diǎn)的key已經(jīng)存在，則替換其value即可；
5、如果集合中的鍵值對(duì)大于12，調(diào)用resize方法進(jìn)行數(shù)組擴(kuò)容

HashMap的get操作源碼分析
1、根據(jù)key的hash值計(jì)算數(shù)組的下標(biāo)；
2、根據(jù)計(jì)算得到的數(shù)組下標(biāo)訪問數(shù)組元素，如果數(shù)組元素為null，則返回空；
3、根據(jù)計(jì)算得到的數(shù)組下標(biāo)訪問數(shù)組元素，如果數(shù)組元素不為null，則遍歷該數(shù)組元素單向鏈表的每個(gè)節(jié)點(diǎn)，如果某個(gè)節(jié)點(diǎn)的key與當(dāng)前key相等，則把該節(jié)點(diǎn)的值返回；
4、根據(jù)計(jì)算得到的數(shù)組下標(biāo)訪問數(shù)組元素，如果數(shù)組元素不為null，則遍歷該數(shù)組元素單向鏈表的每個(gè)節(jié)點(diǎn)，如果某個(gè)節(jié)點(diǎn)的key與當(dāng)前key都不相等，則返回null；
5.判斷元素是否為要查詢的元素條件為
first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))
即hash值一致,key值一致

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

HashMap的常見面試
1、HashMap 的數(shù)據(jù)結(jié)構(gòu)？
哈希表結(jié)構(gòu)（數(shù)組+鏈表）實(shí)現(xiàn)，結(jié)合數(shù)組和鏈表的優(yōu)點(diǎn)，當(dāng)鏈表長(zhǎng)度超過8時(shí)，鏈表轉(zhuǎn)換為紅黑樹；

2、HashMap的hash運(yùn)算如何實(shí)現(xiàn)的？為什么這樣實(shí)現(xiàn)？
HashMap為什么不直接使用對(duì)象的原始hash值？它的實(shí)現(xiàn)代碼如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
JDK 1.8 中，是通過 hashCode() 的高 16 位異或低 16 位實(shí)現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)，主要是從性能，hash碰撞來考慮的，減少系統(tǒng)的開銷，也不會(huì)造成因?yàn)楦呶粵]有參與下標(biāo)的計(jì)算，從而引起的碰撞；
使用異或操作，一個(gè)是提高性能，一個(gè)減少hash碰撞；
通過移位和異或運(yùn)算，可以讓 hash 變得更復(fù)雜，進(jìn)而影響 hash 的分布性；

3、HashMap的容量是多少？加載因子是什么？容量如何變化？容量不夠怎么辦？
數(shù)組大小是由 capacity 這個(gè)參數(shù)確定的，默認(rèn)是16，也可以構(gòu)造時(shí)傳入，最大限制是1<<30；
loadFactor 是裝載因子，主要目的是用來確認(rèn)table 數(shù)組是否需要?jiǎng)討B(tài)擴(kuò)展，默認(rèn)值是0.75，比如table 數(shù)組大小為 16，裝載因子為 0.75 時(shí)，threshold 就是12，當(dāng) table 的實(shí)際大小超過 12 時(shí)，table就需要?jiǎng)討B(tài)擴(kuò)容；
擴(kuò)容時(shí)，調(diào)用 resize() 方法，將 table 長(zhǎng)度變?yōu)樵瓉淼膬杀叮?br> 擴(kuò)容時(shí)創(chuàng)建一個(gè)新的數(shù)組，其容量為舊數(shù)組的兩倍，并重新計(jì)算舊數(shù)組中結(jié)點(diǎn)的存儲(chǔ)位置；
如果數(shù)據(jù)量很大的情況下，擴(kuò)容時(shí)將會(huì)帶來性能的損失，在性能要求很高的地方，這種操作性能很低；

4、什么是hash碰撞，發(fā)生hash碰撞怎么辦？
如果兩個(gè)鍵計(jì)算出來的數(shù)組下標(biāo)一樣，那么就產(chǎn)生了hash碰撞，hash碰撞的解決辦法有

1. 開放地址法
2. 再哈希法
3. 鏈地址法（拉鏈法） -->hashmap采用是該辦法
4. 建立一個(gè)公共溢出區(qū)，
   HashMap采用的是3.鏈地址法（拉鏈法），當(dāng)發(fā)生沖突時(shí)，將新結(jié)點(diǎn)添加在鏈表后面；

5、HashMap 和 HashTable 有什么區(qū)別？
HashMap 是線程不安全的，HashTable 是線程安全的；
由于線程安全，所以 HashTable 的效率比不上 HashMap；
HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null，而 HashTable不允許；
HashMap 默認(rèn)初始化數(shù)組的大小為16，HashTable 為 11，前者擴(kuò)容時(shí)，擴(kuò)大兩倍，后者擴(kuò)大兩倍+1；
HashMap 需要重新計(jì)算 hash 值，而 HashTable 直接使用對(duì)象的 hashCode；

6、HashMap 與 ConcurrentHashMap 的區(qū)別？
除了加鎖之外，原理上無太大區(qū)別，ConcurrentHashMap 類（是 Java并發(fā)包 java.util.concurrent 中提供的一個(gè)線程安全且高效的 HashMap 實(shí)現(xiàn)）。
ConcurrentHashMap，在 JDK 1.7 中采用分段鎖的方式，JDK 1.8 中直接采用了CAS + synchronized，另外HashMap 的鍵值對(duì)允許有null，但是ConCurrentHashMap 都不允許。

7、我們能否讓HashMap實(shí)現(xiàn)同步（線程安全）？
當(dāng)然可以，使用Map map = Collections.synchronizeMap(hashMap);