HashMap原始碼個人理解-有解無憂

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 = https://www.cnblogs.com/ashes001/p/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 = https://www.cnblogs.com/ashes001/p/e.value;//記錄被取代的value
            if (!onlyIfAbsent || oldValue =https://www.cnblogs.com/ashes001/p/= null)
                e.value = https://www.cnblogs.com/ashes001/p/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;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/458427.html

標籤：Java

上一篇：Java語言基礎

下一篇：初學Java時沒有理解的一些概念