免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

作者：阿進的寫字臺

主頁：www.cnblogs.com/homejim

一、HashMap在JAVA中的怎么工作的？

基于Hash的原理

二、什么是哈希？

最簡單形式的 hash，是一種在對任何變量/對象的屬性應用任何公式/算法后， 為其分配唯一代碼的方法。

一個真正的hash方法必須遵循下面的原則

哈希函數(shù)每次在相同或相等的對象上應用哈希函數(shù)時, 應每次返回相同的哈希碼。換句話說, 兩個相等的對象必須一致地生成相同的哈希碼。

Java 中所有的對象都有 Hash 方法。

Java中的所有對象都繼承 Object 類中定義的 hashCode() 函數(shù)的默認實現(xiàn)。 此函數(shù)通常通過將對象的內部地址轉換為整數(shù)來生成哈希碼，從而為所有不同的對象生成不同的哈希碼。

三、HashMap 中的 Node 類

Map的定義是： 將鍵映射到值的對象。

因此，HashMap 中必須有一些機制來存儲這個鍵值對。 答案是肯的。 HashMap 有一個內部類 Node，如下所示：

當然，Node 類具有存儲為屬性的鍵和值的映射。 key 已被標記為 final，另外還有兩個字段：next 和 hash。

在下面中， 我們將會理解這些屬性的必須性。

四、鍵值對在 HashMap中是如何存儲的

鍵值對在 HashMap 中是以 Node 內部類的數(shù)組存放的，如下所示：

transient Node<K,V>[] table;

哈希碼計算出來之后， 會轉換成該數(shù)組的下標， 在該下標中存儲對應哈希碼的鍵值對， 在此先不詳細講解hash碰撞的情況。

該數(shù)組的長度始終是2的次冪， 通過以下的函數(shù)實現(xiàn)該過程

其原理是將傳入?yún)?shù) (cap) 的低二進制全部變?yōu)?，最后加1即可獲得對應的大于 cap 的 2 的次冪作為數(shù)組長度。

為什么要使用2的次冪作為數(shù)組的容量呢？

在此有涉及到 HashMap 的 hash 函數(shù)及數(shù)組下標的計算， 鍵(key)所計算出來的哈希碼有可能是大于數(shù)組的容量的，那怎么辦？ 可以通過簡單的求余運算來獲得，但此方法效率太低。HashMap中通過以下的方法保證 hash 的值計算后都小于數(shù)組的容量。

(n - 1) & hash

這也正好解釋了為什么需要2的次冪作為數(shù)組的容量。由于n是2的次冪，因此，n-1類似于一個低位掩碼。通過與操作，高位的hash值全部歸零，保證低位才有效 從而保證獲得的值都小于n。

同時，在下一次 resize() 操作時， 重新計算每個 Node 的數(shù)組下標將會因此變得很簡單，具體的后文講解。以默認的初始值16為例

但是，使用了該功能之后，由于只取了低位，因此 hash 碰撞會也會相應的變得很嚴重。這時候就需要使用「擾動函數(shù)」

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

該函數(shù)通過將哈希碼的高16位的右移后與原哈希碼進行異或而得到，以上面的例子為例

此方法保證了高16位不變， 低16位根據(jù)異或后的結果改變。計算后的數(shù)組下標將會從原先的5變?yōu)?。

使用了 「擾動函數(shù)」 之后， hash 碰撞的概率將會下降。 有人專門做過類似的測試， 雖然使用該 「擾動函數(shù)」 并沒有獲得最大概率的避免 hash 碰撞，但考慮其計算性能和碰撞的概率， JDK 中使用了該方法，且只hash一次。

五、哈希碰撞及其處理

在理想的情況下， 哈希函數(shù)將每一個 key 都映射到一個唯一的 bucket， 然而， 這是不可能的。哪怕是設計在良好的哈希函數(shù)，也會產生哈希沖突。

前人研究了很多哈希沖突的解決方法，在維基百科中，總結出了四大類

在 Java 的 HashMap 中， 采用了第一種 Separate chaining 方法(大多數(shù)翻譯為拉鏈法)+鏈表和紅黑樹來解決沖突。

在 HashMap 中， 哈希碰撞之后會通過 Node 類內部的成員變量 Node<K,V> next; 來形成一個鏈表(節(jié)點小于8)或紅黑樹（節(jié)點大于8， 在小于6時會從新轉換為鏈表）， 從而達到解決沖突的目的。

六、HashMap 的初始化

 public HashMap();
 public HashMap(int initialCapacity);
 public HashMap(Map<? extends K, ? extends V> m);
 public HashMap(int initialCapacity, float loadFactor); 

HashMap 中有四個構造函數(shù)， 大多是初始化容量和負載因子的操作。以 public HashMap(int initialCapacity, float loadFactor) 為例

通過該函數(shù)進行了容量和負載因子的初始化，如果是調用的其他的構造函數(shù)， 則相應的負載因子和容量會使用默認值（默認負載因子=0.75， 默認容量=16）。在此時， 還沒有進行存儲容器 table 的初始化， 該初始化要延遲到第一次使用時進行。

七、HashMap 中哈希表的初始化或動態(tài)擴容

所謂的哈希表， 指的就是下面這個類型為內部類Node的 table 變量。

transient Node<K,V>[] table;

作為數(shù)組， 其在初始化時就需要指定長度。在實際使用過程中， 我們存儲的數(shù)量可能會大于該長度，因此 HashMap 中定義了一個閾值參數(shù)(threshold)， 在存儲的容量達到指定的閾值時， 需要進行擴容。

我個人認為初始化也是動態(tài)擴容的一種， 只不過其擴容是容量從 0 擴展到構造函數(shù)中的數(shù)值（默認16）。 而且不需要進行元素的重hash.

7.1 擴容發(fā)生的條件

初始化的話只要數(shù)值為空或者數(shù)組長度為 0 就會進行。 而擴容是在元素的數(shù)量大于閾值（threshold）時就會觸發(fā)。

比如 HashMap 中默認的 loadFactor=0.75, capacity=16, 則

threshold = loadFactor * capacity = 0.75 * 16 = 12

那么在元素數(shù)量大于 12 時， 就會進行擴容。 擴容后的 capacity 和 threshold 也會隨之而改變。

負載因子影響觸發(fā)的閾值，因此，它的值較小的時候，HashMap 中的 hash 碰撞就很少， 此時存取的性能都很高，對應的缺點是需要較多的內存；而它的值較大時，HashMap 中的 hash 碰撞就很多，此時存取的性能相對較低，對應優(yōu)點是需要較少的內存；不建議更改該默認值，如果要更改，建議進行相應的測試之后確定。

7.2 再談容量為2的整數(shù)次冪和數(shù)組索引計算

前面說過了數(shù)組的容量為 2 的整次冪， 同時， 數(shù)組的下標通過下面的代碼進行計算

該方法除了可以很快的計算出數(shù)組的索引之外， 在擴容之后， 進行重 hash 時也會很巧妙的就可以算出新的 hash 值。 由于數(shù)組擴容之后， 容量是現(xiàn)在的 2 倍， 擴容之后 n-1 的有效位會比原來多一位， 而多的這一位與原容量二進制在同一個位置。 示例

這樣就可以很快的計算出新的索引啦

7.3 步驟

• 先判斷是初始化還是擴容， 兩者在計算newCap和newThr時會不一樣

• 計算擴容后的容量，臨界值。

• 將hashMap的臨界值修改為擴容后的臨界值

• 根據(jù)擴容后的容量新建數(shù)組，然后將hashMap的table的引用指向新數(shù)組。

• 將舊數(shù)組的元素復制到table中。在該過程中， 涉及到幾種情況， 需要分開進行處理（只存有一個元素， 一般鏈表， 紅黑樹）

具體的看代碼吧

final Node<K, V>[] resize() {
        //新建oldTab數(shù)組保存擴容前的數(shù)組table
        Node<K, V>[] oldTab = table;
        //獲取原來數(shù)組的長度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //原來數(shù)組擴容的臨界值
        int oldThr = threshold;
        int newCap, newThr = 0;
        //如果擴容前的容量 > 0
        if (oldCap > 0) {
            //如果原來的數(shù)組長度大于最大值(2^30)
            if (oldCap >= MAXIMUM_CAPACITY) {
                //擴容臨界值提高到正無窮
                threshold = Integer.MAX_VALUE;
                //無法進行擴容，返回原來的數(shù)組
                return oldTab;
                //如果現(xiàn)在容量的兩倍小于MAXIMUM_CAPACITY且現(xiàn)在的容量大于DEFAULT_INITIAL_CAPACITY
            } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
                //臨界值變?yōu)樵瓉淼?倍
                newThr = oldThr << 1;
        } else if (oldThr > 0) //如果舊容量 <= 0，而且舊臨界值 > 0
            //數(shù)組的新容量設置為老數(shù)組擴容的臨界值
            newCap = oldThr;
        else { //如果舊容量 <= 0，且舊臨界值 <= 0，新容量擴充為默認初始化容量，新臨界值為DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY
            newCap = DEFAULT_INITIAL_CAPACITY;//新數(shù)組初始容量設置為默認值
            newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//計算默認容量下的閾值
        }
        // 計算新的resize上限
        if (newThr == 0) {//在當上面的條件判斷中，只有是初始化時(oldCap=0, oldThr > 0)時，newThr == 0
            //ft為臨時臨界值，下面會確定這個臨界值是否合法，如果合法，那就是真正的臨界值
            float ft = (float) newCap * loadFactor;
            //當新容量< MAXIMUM_CAPACITY且ft < (float)MAXIMUM_CAPACITY，新的臨界值為ft，否則為Integer.MAX_VALUE
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                    (int) ft : Integer.MAX_VALUE);
        }
        //將擴容后hashMap的臨界值設置為newThr
        threshold = newThr;
        //創(chuàng)建新的table，初始化容量為newCap
        @SuppressWarnings({'rawtypes', 'unchecked'})
        Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
        //修改hashMap的table為新建的newTab
        table = newTab;
        //如果舊table不為空，將舊table中的元素復制到新的table中
        if (oldTab != null) {
            //遍歷舊哈希表的每個桶，將舊哈希表中的桶復制到新的哈希表中
            for (int j = 0; j < oldCap; ++j) {
                Node<K, V> e;
                //如果舊桶不為null，使用e記錄舊桶
                if ((e = oldTab[j]) != null) {
                    //將舊桶置為null
                    oldTab[j] = null;
                    //如果舊桶中只有一個node
                    if (e.next == null)
                        //將e也就是oldTab[j]放入newTab中e.hash & (newCap - 1)的位置
                        newTab[e.hash & (newCap - 1)] = e;
                        //如果舊桶中的結構為紅黑樹
                    else if (e instanceof TreeNode)
                        //將樹中的node分離
                        ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                    else {  //如果舊桶中的結構為鏈表,鏈表重排，jdk1.8做的一系列優(yōu)化
                        Node<K, V> loHead = null, loTail = null;
                        Node<K, V> hiHead = null, hiTail = null;
                        Node<K, V> next;
                        //遍歷整個鏈表中的節(jié)點
                        do {
                            next = e.next;
                            // 原索引
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            } else {// 原索引+oldCap
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 原索引放到bucket里
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 原索引+oldCap放到bucket里
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
}

7.4 注意事項

雖然 HashMap 設計的非常優(yōu)秀， 但是應該盡可能少的避免 resize(), 該過程會很耗費時間。

同時， 由于 hashmap 不能自動的縮小容量 因此，如果你的 hashmap 容量很大，但執(zhí)行了很多 remove操作時，容量并不會減少。如果你覺得需要減少容量，請重新創(chuàng)建一個 hashmap。

八、HashMap.put() 函數(shù)內部是如何工作的？

在使用多次 HashMap 之后， 大體也能說出其添加元素的原理：計算每一個key的哈希值， 通過一定的計算之后算出其在哈希表中的位置，將鍵值對放入該位置，如果有哈希碰撞則進行哈希碰撞處理。

而其工作時的原理如下

源碼如下：

在此過程中， 會涉及到哈希碰撞的解決。

九、HashMap.get() 方法內部是如何工作的？

    /**
     * 返回指定的key映射的value，如果value為null，則返回null
     * get可以分為三個步驟：
     * 1.通過hash(Object key)方法計算key的哈希值hash。
     * 2.通過getNode( int hash, Object key)方法獲取node。
     * 3.如果node為null，返回null，否則返回node.value。
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        Node<K, V> e;
        //根據(jù)key及其hash值查詢node節(jié)點，如果存在，則返回該節(jié)點的value值
        return (e = getNode(hash(key), key)) == null ? null : e.value;
}

其最終是調用了 getNode 函數(shù)。 其邏輯如下

源碼如下：

注：今天打卡在頭條推文。