主頁 > 後端開發 > hashMap get put resize方法原始碼決議

hashMap get put resize方法原始碼決議

2022-10-28 06:29:59 後端開發

hashMap get put resize方法原始碼決議

hashMap原始碼學習

簡單介紹一下hashMap,hashMap的頂級父類介面為Map為key-value存貯,在在根據key查找單個元素時時間復雜度為ON(1),但是不能保證元素順序,即元素存進去和取出來的順序不一致,在jdk1.7采用陣列+鏈表實作執行緒不安全,但是在大量存貯元素時可能會出現某種極端情況,鏈表過長(或元素全部存貯到一條鏈表上),查找元素變慢;在jdk1.8時為了解決這個問題,hashMap底層使用了陣列+鏈表+紅黑樹的方式實作,當鏈表元素過長時jdk將會把鏈表轉化為紅黑樹來增加查找速率,但1.8的hashMap仍然不是執行緒安全的,

為什么jdk1.8采用紅黑樹而不采用其他的樹:

而二叉樹在有種極端情況,所有元素全部存盤到樹的一邊上,這樣的話樹在查找某個元素時就和鏈表類似,沒有體現出樹的優勢,而二叉樹是一種平衡二叉樹,樹的左右子樹高度相差不超過一,超過時通過左旋或右旋調整,

參考https://juejin.cn/post/6844903519632228365#comment

下面我們來看一下具體jdk1.8底層是怎么實作的:

靜態變數

靜態變數來定制hashMpa中一些規范如:初始容量、擴容閾值等


    /**
     * The default initial capacity - MUST be a power of two.
     * 默認初始容量-必須是2的冪,
     * 初始容量
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     * 如果隱式指定了更高的值,則使用最大容量由帶有引數的建構式之一執行,
     * 必須是2的冪<=1<<30,
     * HashMap的最大容量
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     * 建構式中未指定時使用的負載系數
     * 容量到達容器的0.75時HashMap將會進行擴容操作
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     * 對于bin使用樹而不是串列的bin計數閾值,將元素添加到具有至少這么多節點的bin時,
     * bin將轉換為樹,該值必須大于2,并且至少應為8,
     * 以便與樹木移除中關于收縮時轉換回普通箱的假設相匹配
     * 
     * 當鏈表長度超過8時HashMap會將鏈表轉換為紅黑樹
     * HashMap會優先將陣列擴容到64時才會進行紅黑樹的轉化
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     * 在調整大小操作程序中取消篩選(拆分)垃圾箱的垃圾箱計數閾值,
     * 應小于TREEIFY_THRESHOLD,最多為6,以便在移除時進行收縮檢測
     * 
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
	 * 可將箱子樹化的最小作業臺容量,
	 *(否則,如果bin中的節點過多,將調整表的大小,)
	 * 應至少為4*TREEIFY_THRESHOLD以避免沖突
	 * 在調整大小和樹化閾值之間,
	 * 
	 * 當陣列長度到達64時且鏈表長度大于等于8時鏈表轉換為紅黑樹
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

構造方法及相關屬性


	//初始無參構造
	//Constructs an empty HashMap with the default initial capacity (16) and the default load factor (0.75).
	//使用默認初始容量(16)和默認負載因子(0.75)構建一個空的HashMap
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }



    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
	//使用指定的初始容量和默認負載因子(0.75)構造空HashMap, 
	//引數: initialCapacity–初始容量, 
	//拋出: IllegalArgumentException–如果初始容量為負數
	//構造一個含有初始容量的HashMap
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }


    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity 初始化容量
     * @param  loadFactor      the load factor      負載因子
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
	//使用外部傳入的HashMap的初始化容量和負載因子
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) //判斷外部傳入的初始化容量是否小于0,小于0則拋出例外
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY) //判斷初始化容量是否超過最大容量
            initialCapacity = MAXIMUM_CAPACITY; //如果大于最大容量則使用最大容量
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) //判斷負載因子是否小于0或者不是數字
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor); //拋出例外
        this.loadFactor = loadFactor;     			    //負載因子賦值
        this.threshold = tableSizeFor(initialCapacity); //將初始化容量先賦給容器界限
    }
	
	//Returns a power of two size for the given target capacity.
	//回傳給定目標容量的兩次冪,
	//得到一個大于獲等于他的2的冪并回傳
	static final int tableSizeFor(int cap) {
        // >>>為無符號右移 將數字轉換為二進制向右移動 高位補0
        // |為或運算,兩個數轉化為二進制,有1則為1,全0則為0
        // |= 與+=類似 a|=b 等價于 a=a|b
        
        //防止傳進來的數本身就是2^n,如果不減一則傳出的值為2^n+1
        int n = cap - 1;
        //右移一位并與自己進行或運算,則原來是1則變成11,
        //例如傳進來數為100001001,右移一位得到0110000100,與自己進行或運算得到110001101
        //一位1變成兩位1,所以下面各右移1、2、4、8、16位
        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;
    }
	


get相關方法和屬性


    /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
	//回傳指定鍵映射到的值,如果此映射不包含該鍵的映射,則回傳null, 
	//更正式地說,如果這個映射包含從鍵k到值v的映射,使得(key==null k==null:key.equals(k))那么這個方法回傳v;否則回傳null,(最多可以有一個這樣的映射,)
	//回傳值null不一定表示映射不包含鍵的映射;映射也可能將鍵顯式映射為null,containsKey操作可用于區分這兩種情況, 請參閱: put(物件,物件
	//在HashMpa中可以存貯最多一個value值為null的鍵值對,但是如果在HashMap中沒有找到對應鍵的時候也會回傳null,可以使用containsKey方法來判斷此鍵是否存在于HashMap中
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    /**
     * Computes key.hashCode() and spreads (XORs) higher bits of hash
     * to lower.  Because the table uses power-of-two masking, sets of
     * hashes that vary only in bits above the current mask will
     * always collide. (Among known examples are sets of Float keys
     * holding consecutive whole numbers in small tables.)  So we
     * apply a transform that spreads the impact of higher bits
     * downward. There is a tradeoff between speed, utility, and
     * quality of bit-spreading. Because many common sets of hashes
     * are already reasonably distributed (so don't benefit from
     * spreading), and because we use trees to handle large sets of
     * collisions in bins, we just XOR some shifted bits in the
     * cheapest possible way to reduce systematic lossage, as well as
     * to incorporate impact of the highest bits that would otherwise
     * never be used in index calculations because of table bounds.
     */
	//計算鍵,hashCode()并將哈希的高位擴展(XOR)到低位,因為該表使用兩個掩碼的冪,所以僅在當前掩碼之上的位中變化的哈希集將始終發生沖突,(在已知的例子中,有一組浮點鍵在小表中保持連續的整數,)因此,我們應用了一種將高位的影響向下擴散的變換,位元擴展的速度、效用和質量之間存在權衡,因為許多常見的散列集已經被合理地分布(因此不會從擴展中受益),并且因為我們使用樹來處理bin中的大量沖突,我們只需以最便宜的方式對一些移位的位進行異或,以減少系統損失,并合并由于表邊界而永遠不會用于索引計算的最高位的影響,
	// 獲取鍵的hash值,HashMap中鍵的hash值都是經過處理的,使得平均分布在陣列上而不會集中分布在某一位置,jdk1.8使用的是高低位異或(16位)

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    /**
     * Implements Map.get and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
	//實施映射,get和相關方法, 引數: hash–密鑰的哈希 key–鑰匙 回傳值: 節點,如果沒有,則為null
	// hash為鍵的hash值,key為外部傳入的鍵
	// 因為初始獲得的Hash的值太長了無法直接在陣列中使用,所以HashMap使用HashMap使用hash確定元素下標的方式為:hash值與陣列長度取余,又因為 任何數 & 2的n次冪 -1 = 任何數 % 2的n次冪,而&運算要比%快,所以HashMap確定陣列下標的公式為:hash & n-1,也所以HashMpa中陣列長度也必須為2的n次冪.
	//
    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 && //判斷HashMpa是否為空
            (first = tab[(n - 1) & hash]) != null) {		 //為空則直接回傳null
            //找到對應陣列下標下的鏈表,判斷頭節點是否就是要找的元素,是則直接回傳頭節點
            if (first.hash == hash && //always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //判斷鏈表中是否只有一個元素,是則直接回傳null,否則繼續向下查詢
            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;
    }

put添加相關方法和屬性


    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
	//將指定值與此映射中的指定鍵相關聯,如果映射之前包含鍵的映射,則替換舊值, 
	//引數: key–與指定值關聯的鍵 value–與指定鍵關聯的值 
	//回傳值: 與鍵關聯的前一個值,如果沒有鍵的映射,則為null,(null回傳還可以指示映射先前將null與鍵關聯,)
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
	//實施映射,put和相關方法, 
	//引數: hash–密鑰的哈希 key–鑰匙 value–要放置的值 onlyIfAbsent–如果為true,則不更改現有值 evict-如果為false,則表處于創建模式, 
	//回傳值: 上一個值,如果沒有則為null
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //檢查HashMap中是否為空,為空則使用resize初始化,并給n賦值
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //檢查陣列下標處是否為空,是則直接賦值((n - 1) & hash 為下標)
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //檢查陣列下標處key是否與新值重復,是則e的值為 key
            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 {
                // 回圈遍歷鏈表,如果找到相同key則替換,沒有找到則插入到鏈表最后并檢查是否超過8,是則將鏈表轉化為紅黑樹
                for (int binCount = 0; ; ++binCount) {
                    // 檢查p是否為最后一個元素,此時結束回圈e為 null
                    if ((e = p.next) == null) {
                        //新元素尾插到末尾
                        p.next = newNode(hash, key, value, null);
                        //檢查鏈表長度是否超過八,是則轉化為紅黑樹,
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //構造樹的具體方法
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 檢查元素是否與新元素相同,是則退出回圈,此時結束回圈e值為 key
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 這句話的意思其實是判斷上面的回圈走完了嗎?如果走完鏈表則e應該是null,如果e不為空則表示新值還沒有被替換,再這里替換
            if (e != null) { // existing mapping for key
                // 將e的值賦給oldValue做中轉
                V oldValue = https://www.cnblogs.com/zzkCultivateBlog/p/e.value;
               	// 判斷條件是 是否改變現有值 新值是否為null
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                // 回傳替換前的值
                return oldValue;
            }
        }
        ++modCount;
        // 判斷是否到達擴容界限 threshold = 容量 * 負載因子(默認0.75)
        if (++size > threshold)
            // 擴容
            resize();
        afterNodeInsertion(evict);
        return null;
    }

    /**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *
     * @return the table
     */
	//初始化或加倍表大小,如果為空,則根據欄位閾值中保持的初始容量目標進行分配,
	//因為我們使用的是二次冪展開,所以每個bin中的元素必須保持在同一索引中,或者在新表中以二次冪偏移量移動,
	//回傳值: table
	//HashMpa的擴容方法
	final Node[] resize() {
        
        Node[] oldTab = table;
        // 判斷HahsMap是否為空給oldCap(舊容量)賦值
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 舊的容量界限
        int oldThr = threshold;
        // 新的容量和新的容量界限
        int newCap, newThr = 0;
        // 判斷是否HashMap第一次初始化
        if (oldCap > 0) {
            // 判斷舊容量是否大于等于最大,是則提升界限,并將容器直接回傳
            if (oldCap >= MAXIMUM_CAPACITY) {
                // 將界限提升到2的31次方 - 1 
                threshold = Integer.MAX_VALUE;
                // 回傳原容器
                return oldTab;
            }
            //判斷舊容量擴大2倍后是否超過最大容量,判斷舊容量界限是否大于等于初始容量(保證不是第一次初始化容器)
            // << 為有符號左移 每移動一位數字擴大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
            // oldCap = 0 且 oldThr <=0 就是容器第一次初始化(即無參構造生成)
            // 將初始(默認)容量賦給新容量
            newCap = DEFAULT_INITIAL_CAPACITY;
             // 默認界限 = 默認容量 * 默認負載因子 = 16 * 0.75
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 針對建構式外部傳入初始容量或負載因子情況,
        //將界限賦值為:新容量 * 外部傳入負載因子(新容量也是外部傳入且經過處理的 tableSizeFor方法)
        
        if (newThr == 0) {
            //新容量界限 = 容量 * 負載因子
            float ft = (float)newCap * loadFactor;
            //判斷是否超過最大容量
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // 將處理好的界限賦值給threshold
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        //初始化node陣列
        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) {
                    //將陣列值置為空,
                    oldTab[j] = null;
                    //判斷鏈表是否只有頭結點,是則把此節點放在擴容后下標處即hash&新容量-1
                    if (e.next == null)
                        //將頭節點放在擴容后陣列的下標處
                        newTab[e.hash & (newCap - 1)] = e;
                    //判斷是否是一個紅黑樹
                    else if (e instanceof TreeNode)
                        ((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;
                        
                        
                        //回圈鏈表,并轉移
                        // e.hash & oldCap 根據這個條件來判斷改元素在新陣列中的偏移量,只有兩種情況:當e.hash & oldCap = 0時則 e.hash & newCap-1 = e.hash & oldCap-1即該元素在新陣列中下標不變;當e.hash & oldCap != 0時則 e.hash & newCap-1 = (e.hash & oldCap-1)+ oldCap即該元素在新陣列下標等于 原下標 + 舊陣列容量
                        // 參考https://blog.csdn.net/u010425839/article/details/106620440#comments_23442640
                        do {
                            // 回圈鏈表
                            next = e.next;
                            // 判斷下標偏移量,為0則不偏移,不為零則偏移oldCap(原下標+oldCap)
                            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;
    }

remove洗掉方法


    /**
     * Removes the mapping for the specified key from this map if present.
     *
     * @param  key key whose mapping is to be removed from the map
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
	//從該映射中洗掉指定鍵的映射(如果存在),
	//引數: key–要從映射中洗掉其映射的鍵 
	//回傳值: 與鍵關聯的前一個值,如果沒有鍵的映射,則為null,(null回傳還可以指示映射先前將null與鍵關聯,)
    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }


	//實施映射,移除和相關方法, 
	//引數: hash–密鑰的哈希 key–鑰匙 
	//value 如果matchValue為ture要對比的值,為matchValue為false則忽略
	//matchValue 如果為true,則僅在值相等時洗掉
	//可移動–如果為false,則在洗掉時不要移動其他節點 
	//回傳值: 節點,如果沒有,則為null
    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        // 判斷容器是否為慷訓者陣列對應下標處沒有元素,并將元素所對陣列下標處元素賦值給p
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            // node就是目標要洗掉的元素
            Node<K,V> node = null, e; K k; V v;
            // 判斷要洗掉的元素是否就是頭節點,并賦值給node
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            // 判斷陣列下標處是否只有頭節點,是則表明鏈表只有一個元素且不是要洗掉的元素
            else if ((e = p.next) != null) {
                // 判斷此時是不是紅黑樹
                if (p instanceof TreeNode)
                   	// 使用紅黑樹方式查找到要洗掉的元素并賦值給node
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    // 遍歷鏈表并找到要洗掉的元素賦值給node
                    do {
                        // 檢查是否當前元素是否是要洗掉的元素
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            // 賦值給node并退出回圈
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            // 判斷容器是否包含要洗掉的元素,判斷是否采用值相等時才洗掉的模式,判斷外部傳入的值是否與容器內值相等
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                // 判斷是否是紅黑樹,是則采用紅黑樹方式洗掉
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                // 判斷是否為鏈表頭節點
                else if (node == p)
                    tab[index] = node.next;
                // 鏈表普通元素,直接洗掉
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                // 回傳洗掉的元素
                return node;
            }
        }
        return null;
    }
	

參考:
https://pdai.tech/md/java/collection/java-map-HashMap&HashSet.html
https://blog.csdn.net/u010425839/article/details/106620440#comments_23442640
https://juejin.cn/post/6844903519632228365#comment

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

標籤:Java

上一篇:IDEA 一鍵生成 Maven 依賴關系圖,太強大了。。

下一篇:java計算一個實體物件占用空間大小的方法分享

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C#(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 【C++】Microsoft C++、C 和匯編程式檔案

    ......

    uj5u.com 2020-09-10 00:57:23 more
  • 例外宣告

    相比于斷言適用于排除邏輯上不可能存在的狀態,例外通常是用于邏輯上可能發生的錯誤。 例外宣告 Item 1:當函式不可能拋出例外或不能接受拋出例外時,使用noexcept 理由 如果不打算拋出例外的話,程式就會認為無法處理這種錯誤,并且應當盡早終止,如此可以有效地阻止例外的傳播與擴散。 示例 //不可 ......

    uj5u.com 2020-09-10 00:57:27 more
  • Codeforces 1400E Clear the Multiset(貪心 + 分治)

    鏈接:https://codeforces.com/problemset/problem/1400/E 來源:Codeforces 思路:給你一個陣列,現在你可以進行兩種操作,操作1:將一段沒有 0 的區間進行減一的操作,操作2:將 i 位置上的元素歸零。最終問:將這個陣列的全部元素歸零后操作的最少 ......

    uj5u.com 2020-09-10 00:57:30 more
  • UVA11610 【Reverse Prime】

    本人看到此題沒有翻譯,就附帶了一個自己的翻譯版本 思考 這一題,它的第一個要求是找出所有 $7$ 位反向質數及其質因數的個數。 我們應該需要質數篩篩選1~$10^{7}$的所有數,這里就不慢慢介紹了。但是,重讀題,我們突然發現反向質數都是 $7$ 位,而將它反過來后的數字卻是 $6$ 位數,這就說明 ......

    uj5u.com 2020-09-10 00:57:36 more
  • 統計區間素數數量

    1 #pragma GCC optimize(2) 2 #include <bits/stdc++.h> 3 using namespace std; 4 bool isprime[1000000010]; 5 vector<int> prime; 6 inline int getlist(int ......

    uj5u.com 2020-09-10 00:57:47 more
  • C/C++編程筆記:C++中的 const 變數詳解,教你正確認識const用法

    1、C中的const 1、區域const變數存放在堆疊區中,會分配記憶體(也就是說可以通過地址間接修改變數的值)。測驗代碼如下: 運行結果: 2、全域const變數存放在只讀資料段(不能通過地址修改,會發生寫入錯誤), 默認為外部聯編,可以給其他源檔案使用(需要用extern關鍵字修飾) 運行結果: ......

    uj5u.com 2020-09-10 00:58:04 more
  • 【C++犯錯記錄】VS2019 MFC添加資源不懂如何修改資源宏ID

    1. 首先在資源視圖中,添加資源 2. 點擊新添加的資源,復制自動生成的ID 3. 在解決方案資源管理器中找到Resource.h檔案,編輯,使用整個專案搜索和替換的方式快速替換 宏宣告 4. Ctrl+Shift+F 全域搜索,點擊查找全部,然后逐個替換 5. 為什么使用搜索替換而不使用屬性視窗直 ......

    uj5u.com 2020-09-10 00:59:11 more
  • 【C++犯錯記錄】VS2019 MFC不懂的批量添加資源

    1. 打開資源頭檔案Resource.h,在其中預先定義好宏 ID(不清楚其實ID值應該設定多少,可以先新建一個相同的資源項,再在這個資源的ID值的基礎上遞增即可) 2. 在資源視圖中選中專案資源,按F7編輯資源檔案,按 ID 型別 相對路徑的形式添加 資源。(別忘了先把檔案拷貝到專案中的res檔案 ......

    uj5u.com 2020-09-10 01:00:19 more
  • C/C++編程筆記:關于C++的參考型別,專供新手入門使用

    今天要講的是C++中我最喜歡的一個用法——參考,也叫別名。 參考就是給一個變數名取一個變數名,方便我們間接地使用這個變數。我們可以給一個變數創建N個參考,這N + 1個變數共享了同一塊記憶體區域。(參考型別的變數會占用記憶體空間,占用的記憶體空間的大小和指標型別的大小是相同的。雖然參考是一個物件的別名,但 ......

    uj5u.com 2020-09-10 01:00:22 more
  • 【C/C++編程筆記】從頭開始學習C ++:初學者完整指南

    眾所周知,C ++的學習曲線陡峭,但是花時間學習這種語言將為您的職業帶來奇跡,并使您與其他開發人員區分開。您會更輕松地學習新語言,形成真正的解決問題的技能,并在編程的基礎上打下堅實的基礎。 C ++將幫助您養成良好的編程習慣(即清晰一致的編碼風格,在撰寫代碼時注釋代碼,并限制類內部的可見性),并且由 ......

    uj5u.com 2020-09-10 01:00:41 more
最新发布
  • Rust中的智能指標:Box<T> Rc<T> Arc<T> Cell<T> RefCell<T> Weak

    Rust中的智能指標是什么 智能指標(smart pointers)是一類資料結構,是擁有資料所有權和額外功能的指標。是指標的進一步發展 指標(pointer)是一個包含記憶體地址的變數的通用概念。這個地址參考,或 ” 指向”(points at)一些其 他資料 。參考以 & 符號為標志并借用了他們所 ......

    uj5u.com 2023-04-20 07:24:10 more
  • Java的值傳遞和參考傳遞

    值傳遞不會改變本身,參考傳遞(如果傳遞的值需要實體化到堆里)如果發生修改了會改變本身。 1.基本資料型別都是值傳遞 package com.example.basic; public class Test { public static void main(String[] args) { int ......

    uj5u.com 2023-04-20 07:24:04 more
  • [2]SpinalHDL教程——Scala簡單入門

    第一個 Scala 程式 shell里面輸入 $ scala scala> 1 + 1 res0: Int = 2 scala> println("Hello World!") Hello World! 檔案形式 object HelloWorld { /* 這是我的第一個 Scala 程式 * 以 ......

    uj5u.com 2023-04-20 07:23:58 more
  • 理解函式指標和回呼函式

    理解 函式指標 指向函式的指標。比如: 理解函式指標的偽代碼 void (*p)(int type, char *data); // 定義一個函式指標p void func(int type, char *data); // 宣告一個函式func p = func; // 將指標p指向函式func ......

    uj5u.com 2023-04-20 07:23:52 more
  • Django筆記二十五之資料庫函式之日期函式

    本文首發于公眾號:Hunter后端 原文鏈接:Django筆記二十五之資料庫函式之日期函式 日期函式主要介紹兩個大類,Extract() 和 Trunc() Extract() 函式作用是提取日期,比如我們可以提取一個日期欄位的年份,月份,日等資料 Trunc() 的作用則是截取,比如 2022-0 ......

    uj5u.com 2023-04-20 07:23:45 more
  • 一天吃透JVM面試八股文

    什么是JVM? JVM,全稱Java Virtual Machine(Java虛擬機),是通過在實際的計算機上仿真模擬各種計算機功能來實作的。由一套位元組碼指令集、一組暫存器、一個堆疊、一個垃圾回收堆和一個存盤方法域等組成。JVM屏蔽了與作業系統平臺相關的資訊,使得Java程式只需要生成在Java虛擬機 ......

    uj5u.com 2023-04-20 07:23:31 more
  • 使用Java接入小程式訂閱訊息!

    更新完微信服務號的模板訊息之后,我又趕緊把微信小程式的訂閱訊息給實作了!之前我一直以為微信小程式也是要企業才能申請,沒想到小程式個人就能申請。 訊息推送平臺🔥推送下發【郵件】【短信】【微信服務號】【微信小程式】【企業微信】【釘釘】等訊息型別。 https://gitee.com/zhongfuch ......

    uj5u.com 2023-04-20 07:22:59 more
  • java -- 緩沖流、轉換流、序列化流

    緩沖流 緩沖流, 也叫高效流, 按照資料型別分類: 位元組緩沖流:BufferedInputStream,BufferedOutputStream 字符緩沖流:BufferedReader,BufferedWriter 緩沖流的基本原理,是在創建流物件時,會創建一個內置的默認大小的緩沖區陣列,通過緩沖 ......

    uj5u.com 2023-04-20 07:22:49 more
  • Java-SpringBoot-Range請求頭設定實作視頻分段傳輸

    老實說,人太懶了,現在基本都不喜歡寫筆記了,但是網上有關Range請求頭的文章都太水了 下面是抄的一段StackOverflow的代碼...自己大修改過的,寫的注釋挺全的,應該直接看得懂,就不解釋了 寫的不好...只是希望能給視頻網站開發的新手一點點幫助吧. 業務場景:視頻分段傳輸、視頻多段傳輸(理 ......

    uj5u.com 2023-04-20 07:22:42 more
  • Windows 10開發教程_編程入門自學教程_菜鳥教程-免費教程分享

    教程簡介 Windows 10開發入門教程 - 從簡單的步驟了解Windows 10開發,從基本到高級概念,包括簡介,UWP,第一個應用程式,商店,XAML控制元件,資料系結,XAML性能,自適應設計,自適應UI,自適應代碼,檔案管理,SQLite資料庫,應用程式到應用程式通信,應用程式本地化,應用程式 ......

    uj5u.com 2023-04-20 07:22:35 more