Map接口實作類總結

一、場景選擇

TreeMap和HashMap選擇

排序：排序的時候用TreeMap，其他用HashMap。

為什麼後者性能更好？

個人了解，排序需要犧牲性能，是以一般不排序都用後者。

LinkedHashMap和HashMap選擇

FIFO:插入疊代順序一緻用LinkedHashMap，其他用HashMap

LinkedHashMap 繼承HashMap底層連結清單結構，插入順序與疊代順序一緻

Hashtable（棄用）

線程安全，不推薦使用，使用ConcurrentHashMap代替多線程場景，性能更好。

ConcurrentHashMap

3個字：多線程

二、HashMap專題

特點：key不重複

ArrayList 底層是數組結構， LinkedList底層是連結清單結構

hashmap底層結構？

HashMap結合以上兩點，數組+單連結清單結構

什麼是bucket？

bucket可以了解為對象的存儲空間/位址。

hashmap是怎麼插入資料，插入資料的過程？

通過鍵值對（entry）對象計算hashcode 确定插入bucket位置，存儲entry對象，hashcode相同，bucket就相同，發生沖突，通過單連結清單來解決碰撞問題，如果碰撞就存到連結清單的下一個節點。

hashmap怎麼取資料？

通過get方法，使用鍵值對象的hashcode去找bucket位置，找到bucket位置之後，會調用keys.equals()方法去找到連結清單中正确的節點，最終找到要找的值對象。

hashmap怎麼實作同步？

HashMap可以通過下面的語句進行同步：

Map m = Collections.synchronizeMap(hashMap);

什麼是碰撞？為什麼String Integer作為key？

碰撞就是通過hash算法計算出來的hashcode如果一樣，就是發生存儲位址碰撞。而String是不可變的，重寫了hashcode equals方法，比較适合做key。

為什麼hashmap是線程不安全的？

因為如果兩個線程put時，key的hash值一樣，而hashmap時根據hashcode值存儲的，就會存到同一個位置，出現資料覆寫。

hashmap初始數組大小，如何擴容？

初始16的數組，容量達到3/4的時候2倍擴容，16*0.75=12   16*2=32   0~31

三、key-value是否為null

可以搞個表格，但是不想去翻表格，怎麼記？總不能每次突然問你，你都去翻表格吧

key： hashmap 可空，其他都不行。（TreeMap/ConcurrentHashMap/HashTable）。 linkedhashmap就是繼承hashmap的，記一個就夠了。

value：hashmap/TreeMap可空。

口訣：H2T控   =   hashmap  keyvalue可空， treemap  value 可空，key排序肯定不能為null

哈哈哈哈

四、HashMap源碼分析

put操作

Map<String, Object> map = new HashMap<>();

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)//初始化時， putVal中的table==null，進入這裡，調用resize，resize會初始化容量為16，table也會有值
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)//判斷容量内是否指派
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)//是否是紅黑樹
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);//JDK1.8容量大于=8的時候使用紅黑樹，否則使用連結清單
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
           

jdk1.7和jdk1.8的差別

（1）初始數組

jdk7:在建立hashmap對象的時候，就初始table的容量為16

jdk8:在建立hashmap對象的時候，并沒有初始table，就初始了加載因子，隻有當我們第一次添加的時候，才會初始table的容量為16

（2）table類型

jdk7：table的類型為Entry

jdk8：table的類型為Node，為了轉為樹結構

（3）結構

jdk7：哈希表為數組+連結清單，不管連結清單的總結點數為多少，都不會變成樹結構

jdk8：哈希表為數組+連結清單+紅黑樹，連結清單的節點數（沖突節點數）>=8 &&

桶的總個數(table的容量，也就是我們開發中map的大小了) >= 64的時候，會講連結清單結構（沖突的連結清單結構）變成紅黑樹TreeNode