HashMap源碼個人理解_ZenDei技術網路在線

HashMap<Integer, String> map = new HashMap<>();map.put(11,"張三");map.put(12,"李四");map.put(13,"王五");map.put(12,"趙六");map.put(14,"陳皮");System.out.println ...

HashMap<Integer, String> map = new HashMap<>();
map.put(11,"張三");
map.put(12,"李四");
map.put(13,"王五");
map.put(12,"趙六");
map.put(14,"陳皮");
System.out.println(map.size()); //長度為4  說明相同key存在某種操作(是替換還是不替換(丟棄))？

System.out.println(map.toString());//{11=張三, 12=趙六, 13=王五, 14=陳皮}  這是key-value一起換了 還是只換了value

查看源碼(JDK1.8) 只截取出相關代碼

有個疑問　　HashMap繼承了AbstractMap,而AbstractMap自己也實現了Map<K,V>介面，那為什麼HashMap也要實現Map<K,V>介面呢？

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {

　　static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //預設初始容量左移4位 也就是2^4=16

　　static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量 2^30

　　static final float DEFAULT_LOAD_FACTOR = 0.75f; //預設載入因數0.75(也就是當存放的數據達到容量的75%的時候會實現擴容)

　　//靜態內部類
　　//HashMap底層其實是數據+鏈表的結構(1.7之前)　　1.8之後就是數據+鏈表+紅黑樹
　　//這個就是節點的類類型(需要掌握點數據結構相關知識)

　　static class Node<K,V> implements Map.Entry<K,V> {
    　　final int hash;
    　　final K key;
    　　V value;
    　　Node<K,V> next;

    　　Node(int hash, K key, V value, Node<K,V> next) {
        　　this.hash = hash;
        　　this.key = key;
        　　this.value = value;
        　　this.next = next;
    　　}

　　transient int size; //記錄當前map中(也就是最上層數組中元素的個數)

　　int threshold; //擴容的臨界值(達到這個值的時候數組就要擴容了)

　　final float loadFactor; //載入因數

　　transient Node<K,V>[] table; //hashMap的主數組

　　static final int hash(Object key) { //通過key計算hash值的方法

    　　int h;
    　　return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
　　}

　　//構造方法　　
　　//無參構造初始化載入因數

　　public HashMap() {
    　　this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
　　}
　　//自定義出事容量個載入因數

　　public HashMap(int initialCapacity, float loadFactor) {
　　　　//以下三個if不用看 是為了代碼的健壯性考慮
    　　if (initialCapacity < 0) 
　　　　　　throw new IllegalArgumentException("Illegal initial capacity: " + nitialCapacity);
    　　if (initialCapacity > MAXIMUM_CAPACITY) 
　　　　　　initialCapacity = MAXIMUM_CAPACITY;
    　　if (loadFactor <= 0 || Float.isNaN(loadFactor)) 
　　　　　　throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
　　　　//初始化載入因數
    　　this.loadFactor = loadFactor;
　　　　//初始化容量
    　　this.threshold = tableSizeFor(initialCapacity);
　　}

　　//自定義初始化容量

　　public HashMap(int initialCapacity) {
    　　this(initialCapacity, DEFAULT_LOAD_FACTOR);
　　}
　　
　　//右移對應的位之後進行或(位)運算(無符號右移)　　　　>>這是帶符號的右移 註意

　　static final int tableSizeFor(int cap) {
    　　int n = cap - 1;
    　　n |= n >>> 1;
    　　n |= n >>> 2;
    　　n |= n >>> 4;
    　　n |= n >>> 8;
    　　n |= n >>> 16;
    　　return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
　　}
　　解釋

　　//這就是向put中添加

　　public V put(K key, V value) {
    　　return putVal(hash(key), key, value, false, true);
　　}

　　//onlyIfAbsent if true, don't change existing value　　這是官方註釋 如果這個參數為true 就不需要改變現有的把value
　　//evict if false, the table is in creation mode.　　　　如果為false　　就是建表模式

　　//這是真正實現插入的方法

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)
　　　　　//這是數組的擴容和初始化　　跳到下麵的方法
        n = (tab = resize()).length;
　　//這是計算該hash值的數據在數組中的位置　　註意 這是拿數組的最大長度和該key的hash做與運算 所以不可能大於最大長度 不會發生越界問題
    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))))//這裡註意 如果hash值相同 key也相同 短路或 後面的value就不用比了
            e = p;//記錄下 改原鏈表中相同的節點
        else if (p instanceof TreeNode)//這是紅黑樹 不看
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {//這是插入操作 也就是hash值不同或者hash值相同 key不同
            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);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))//找到就break
                    break;
                p = e;//繼續往後找
            }
        }
        if (e != null) { // existing mapping for key 
            V oldValue = e.value;//記錄被取代的value
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;//返回被取代的value
        }
    }
    ++modCount;
    if (++size > threshold)//map長度+1
        resize();
    afterNodeInsertion(evict);
    return null;
}

//這是數組的擴容方法和初始化

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
　　//判斷是初始化還是擴容　　
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
　　//擴容
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }//如果擴容前的數組長度小於最大容量 
　　　　　　//(舊數組的容量左移一位(也就是2倍)賦值給新數組的容量 ，且容量不能大於最大容量 )&& 舊數組的容量要大於等於出事容量 
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
　　　　　　　　//擴容的閾值也擴大兩倍
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
　　//這裡就是初始化數組
    else {               // zero initial threshold signifies using defaults
　　　　　//初始化容量
        newCap = DEFAULT_INITIAL_CAPACITY;
　　　　 //初始化載入因數 也就是達到這個值就要擴容
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
　　//這裡是數組擴容的時候修改載入因數
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
　　//修改閾值
    threshold = newThr;

    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//主數組
    table = newTab;
    if (oldTab != null) {//如果擴容前的數組不為空 就需要將原來的數據存進去
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;//創建新節點
            if ((e = oldTab[j]) != null) {//判斷原來的節點是不是null 取出來存著
                oldTab[j] = null;//再將就數組中的節點清空(原來的數據已經用e存著了)等著gc回收
                if (e.next == null)//判斷該數組中的元素 所在的鏈表是否有後續節點
                    newTab[e.hash & (newCap - 1)] = e;//將該節點重新計算hash值並存入新數組
                else if (e instanceof TreeNode)//這是jdk1.8之後引入的紅黑樹的概念 這裡就不看了 這是因為當鏈表中的個數大於等於8的時候此時就不再採用鏈表存儲了，而是採用紅黑樹存儲，這是為提高查找效率(時間複雜度)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order(保持順序)　　這是保持原來的鏈表順序
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {//這裡說明下 jdk1.7之前採用的是頭插法　　1.8之後採用的尾插法
                        next = e.next;//記錄後續的鏈表的頭結點
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}