• <noscript id="e0iig"><kbd id="e0iig"></kbd></noscript>
  • <td id="e0iig"></td>
  • <option id="e0iig"></option>
  • <noscript id="e0iig"><source id="e0iig"></source></noscript>
  • HashMap實現原理及源碼分析

    1.HashMap介紹

    HashMap為Map接口的一個實現類,實現了所有Map的操作。HashMap除了允許key和value保存null值和非線程安全外,其他實現幾乎和HashTable一致。

    HashMap使用散列存儲的方式保存kay-value鍵值對,因此其不支持數據保存的順序。如果想要使用有序容器可以使用LinkedHashMap。

    在性能上當HashMap中保存的key的哈希算法能夠均勻的分布在每個bucket中的是時候,HashMap在基本的get和set操作的的時間復雜度都是O(n)。

    在遍歷HashMap的時候,其遍歷節點的個數為bucket的個數+HashMap中保存的節點個數。因此當遍歷操作比較頻繁的時候需要注意HashMap的初始化容量不應該太大。 這一點其實比較好理解:當保存的節點個數一致的時候,bucket越少,遍歷次數越少。

    另外HashMap在resize的時候會有很大的性能消耗,因此當需要在保存HashMap中保存大量數據的時候,傳入適當的默認容量以避免resize可以很大的提高性能。 具體的resize操作請參考下面對此方法的分析

    HashMap是非線程安全的類,當作為共享可變資源使用的時候會出現線程安全問題。需要使用線程安全容器:

    Map m = new ConcurrentHashMap();或者
    Map m = Collections.synchronizedMap(new HashMap());

    具體的HashMap會出現的線程安全問題分析請參考9中的分析。

    2.數據結構介紹

    HashMap使用數組+鏈表+樹形結構的數據結構。其結構圖如下所示。

    929184-20180624160014497-2120500803.png

    3.HashMap源碼分析(基于JDK1.8)

    3.1關鍵屬性分析

    transient Node<K,V>[] table; //Node類型的數組,記我們常說的bucket數組,其中每個元素為鏈表或者樹形結構
    
    transient int size;//HashMap中保存的數據個數
    
    int threshold;//HashMap需要resize操作的閾值
    
    final float loadFactor;//負載因子,用于計算threshold。計算公式為:threshold = loadFactor * capacity
    
    其中還有一些默認值得屬性,有默認容量2^4,默認負載因子0.75等.用于構造函數沒有指定數值情況下的默認值。
     

    3.2構造函數分析

    HashMap提供了三個不同的構造函數,主要區別為是否傳入初始化容量和負載因子。分別文以下三個。

    //此構造函數創建一個空的HashMap,其中負載因子為默認值0.75
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    
    //傳入默認的容量大小,創造一個指定容量大小和默認負載因子為0.75的HashMap
     public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    //創建一個指定容量和指定負載因為HashMap,以下代碼刪除了入參檢查
    public HashMap(int initialCapacity, float loadFactor) {
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

    注意:此處的initialCapacity為數組table的大小,即bucket的個數。

    其中在指定初始化容量的時候,會根據傳入的參數來確定HashMap的容量大小。
    初始化this.threshold的值為入參initialCapacity距離最近的一個2的n次方的值。取值方法如下:

    case initialCapacity = 0:  
    
         this.threshold = 1;  
         
    case initialCapacity為非0且不為2的n次方:  
    
        this.threshold = 大于initialCapacity中第一個2的n次方的數。  
        
    case initialCapacity = 2^n:  
    
        this.threshold = initialCapacity

    具體的計算方法為tableSizeFor(int cap)函數。計算方法是將入參的最高位下面的所有位都設置為1,然后加1

    下面以入參為134217729為例分析計算過程。
    首先將int轉換為二進制如下:
    cap = 0000 1000 0000 0000 0000 0000 0000 0001

    static final int tableSizeFor(int cap) {
            
            int n = cap - 1; //n =0000 1000 0000 0000 0000 0000 0000 0000  此操作為了處理cap=2的n次方的情況,如果不減1,計算的結果位2的n+1方,添加次操作當cap = 2^n的時候計算結果為2^n
            //以下操作將n的最高位到最低位之間的各位全部設置為1
    
            // n = 0000 1000 0000 0000 0000 0000 0000 0000   
                  |0000 01000 0000 0000 0000 0000 0000 000 
                 = 0000 1100 0000 0000 0000 0000 0000 0000
            //最高兩位設置為1
            n |= n >>> 1;
            
            
            // n = 0000 1100 0000 0000 0000 0000 0000 0000 
                 | 0000 0011 0000 0000 0000 0000 0000 0000 
                 = 0000 1111 0000 0000 0000 0000 0000 0000
            //最高四位設置為1
            n |= n >>> 2;
            
            //n = 0000 1111 0000 0000 0000 0000 0000 0000 
                | 0000 0000 1111 0000 0000 0000 0000 0000  
                = 0000 1111 1111 0000 0000 0000 0000 0000
            //最高8為設置為1
            n |= n >>> 4;
            
            //n = 0000 1111 1111 0000 0000 0000 0000 0000 
                | 0000 0000 0000 1111 1111 0000 0000 0000  
                = 0000 1111 1111 1111 1111 0000 0000 0000
            //最高16為設置為1
            n |= n >>> 8;
            
            //n = 0000 1111 1111 1111 1111 0000 0000 0000 
                | 0000 0000 0000 0000 0000 1111 1111 1111 
                = 0000 1111 1111 1111 1111 1111 1111 1111
           //不足32位,最高28位設置位1
            n |= n >>> 16;
    
            //n = n + 1 = 0000 1111 1111 1111 1111 1111 1111 1111 + 1 = 0001 0000 0000 0000 0000 0000 0000 0000
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }

    另外此處賦值為this.threshold,是因為構造函數的時候并不會創建table,只有實際插入數據的時候才會創建。目的應該是為了節省內存空間吧。
    在第一次插入數據的時候,會將table的capacity設置為threshold,同時將threshold更新為loadFactor * capacity

    3.3關鍵函數源碼分析

    3.3.1 第一次插入數據的操作

    HashMap在插入數據的時候傳入key-value鍵值對。使用hash尋址確定保存數據的bucket。當第一次插入數據的時候會進行HashMap中容器的初始化。具體操作如下:

            Node<K,V>[] tab; 
            int n, i;
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            

    其中resize函數的源碼如下,主要操作為根據cap和loadFactory創建初始化table

        Node<K, V>[] oldTab = table;
        int oldThr = threshold;  //oldThr 根據傳入的初始化cap決定 2的n次方
    
        int newCap, newThr = 0;
        if (oldThr > 0) // 當構造函數中傳入了capacity的時候
            newCap = oldThr;  //newCap = threshold  2的n次方,即構造函數的時候的初始化容量
         else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        float ft = (float)newCap * loadFactor;  // 2的n次方 * loadFactory
    
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                (int)ft : Integer.MAX_VALUE);
    
        threshold = newThr; //新的threshold== newCap * loadFactory
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //長度為2的n次方的數組
        table = newTab;

    在初始化table之后,將數據插入到指定位置,其中bucket的確定方法為:

     i = (n - 1) & hash // 此處n-1必定為 0000 1111 1111....的格式,取&操作之后的值一定在數組的容量范圍內。
     

    其中hash的取值方式為:

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

    具體操作如下,創建Node并將node放到table的第i個元素中

    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = new Node(hash, key, value, null);

    3.3.2 非第一次插入數據的操作源碼分析

    當HashMap中已有數據的時候,再次插入數據,會多出來在鏈表或者樹中尋址的操作,和當size到達閾值時候的resize操作。多出來的步驟如下:

            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = new Node(hash, key, value, null);
            else {
                Node<K,V> e; K k;
                // hash相等,且key地址相等或者equals為true的時候直接替換
                if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                else if (p instanceof TreeNode)
                    //  當bucket的此節點為樹結構的時候,在樹中插入一個節點
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
                    //便利此bucket節點,插入到鏈表尾部
                    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);//當鏈表節點樹大于TREEIFY_THRESHOLD的時候,轉換為樹形結構
                            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();

    另外,在resize操作中也和第一次插入數據的操作不同,當HashMap不為空的時候resize操作需要將之前的數據節點復制到新的table中。操作如下:

            if (oldTab != null) {
                for (int j = 0; j < oldCap; ++j) {
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
                        oldTab[j] = null;
                        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;
                            do {
                                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;
                            }
                        }
                    }
                }
            }

    3.4Cloneable和Serializable分析

    在HashMap的定義中實現了Cloneable接口,Cloneable是一個標識接口,主要用來標識 Object.clone()的合法性,在沒有實現此接口的實例中調用 Object.clone()方法會拋出CloneNotSupportedException異常。可以看到HashMap中重寫了clone方法。

    HashMap實現Serializable接口主要用于支持序列化。同樣的Serializable也是一個標識接口,本身沒有定義任何方法和屬性。另外HashMap自定義了

    private void writeObject(java.io.ObjectOutputStream s) throws IOException
    
    private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException

    兩個方法實現了自定義序列化操作。

    注意:支持序列化的類必須有無參構造函數。這點不難理解,反序列化的過程中需要通過反射創建對象。

    4.HashMap的遍歷

    以下討論兩種遍歷方式,測試代碼如下:

    方法一:

    通過map.keySet()獲取key的集合,然后通過遍歷key的集合來遍歷map 

    方法二:

    通過map.entrySet()方法獲取map中節點集合,然后遍歷此集合遍歷map

    測試代碼如下:

    public static void main(String[] args) throws Exception {
            Map<String, Object> map = new HashMap<>();
            map.put("name", "test");
            map.put("age", "25");
            map.put("address", "HZ");
            
            Set<String> keySet = map.keySet();
            for (String key : keySet) {
                System.out.println(map.get(key));
            }
    
            Set<Map.Entry<String, Object>> set = map.entrySet();
            for (Map.Entry<String, Object> entry : set) {
                System.out.println("key is : " + entry.getKey() + ".  value is " + entry.getValue());
            }
        }

    輸出如下:

    HZ
    test
    25
    key is : address.  value is HZ
    key is : name.  value is test
    key is : age.  value is 25

    我的博客即將搬運同步至騰訊云+社區,邀請大家一同入駐:https://cloud.tencent.com/developer/support-plan?invite_code=3c3z5rvu0g00g

    版權聲明:本文為weixin_34218579原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。
    本文鏈接:https://blog.csdn.net/weixin_34218579/article/details/93224100

    智能推薦

    HashMap源碼實現原理

    這幾天學習了HashMap的底層實現,但是發現好幾個版本的,代碼不一,而且看了Android包的HashMap和JDK中的HashMap的也不是一樣,原來他們沒有指定JDK版本,很多文章都是舊版本JDK1.6.JDK1.7的。現在我來分析一哈最新的JDK1.8的HashMap及性能優化。 在JDK1.6,JDK1.7中,HashMap采用位桶+鏈表實現,即使用鏈表處理沖突,同一hash值的鏈表都存...

    HashMap實現原理分析

    HashMap的原理實現,需要掌握的重要性就不多說了,今天花時間和經歷去查閱資料查看源碼學習了,等下會附上參考文章的原地址,寫的真的很好,自己在這再總結一下經常用到并且需要掌握的地方,需要更詳細的可以看一下原博客的位置。自己看完之后,對于其中的一點還是有點不太懂,就是hash算法原理,這個還是要去研究一下的,位運算是怎樣計算的。 原博客的地址:https://www.cnblogs.com/sky...

    HashMap實現原理分析

    前言:         HashMap的包結構 HashMap是基于哈希表的 Map 接口的實現。此實現提供所有可選的映射操作,并允許使用 null 值和 null 鍵。(除了非同步和允許使用 null 之外,HashMap 類與 Hashtable 大致相同。)此類不保證映射的順序,特別是它不保證該順序恒久不變。 *注意,此實現不是同步的。 好吧&ldqu...

    數組刪除其中某個對象的方法

    數組刪除其中的對象或元素,在前端是比較常見的需求。 我現在比較常用的方法如下: 這種方法只適合刪除具有唯一標識的對象。 有沒有想要脫單的小伙伴,加入我們的脫單星球,認識更多優秀的小哥哥小姐姐 特此聲明,星球是免費的,但是創建星球的時候說是必須輸入金額,所以只能先私聊,我再加你免費加入!...

    圖床搭建以及圖床工具的使用

    為什么要用圖床和圖床工具? 比較下面三種md中的圖片url地址(均免費),你會使用哪一種? 選1?由于是本地路徑,文檔分享后給其他人打開后很可能顯示圖片加載失敗。 選2?雖然分享后可以顯示圖片,但能保證加載速度? 選3?我肯定選這種,即兼容2的瀏覽器訪問,又能保證訪問速度。 這樣就可以回答上面的問題了!保證瀏覽器訪問要用圖床,保證加載速度要用圖床工具,又不花錢想想就開心。 除此之外本篇博客還會講解...

    猜你喜歡

    并發編程理論篇

    一、必備知識回顧 計算機又叫電腦,即通電的大腦,發明計算機是為了讓他通電之后能夠像人一樣去工作,并且它比人的工作效率更高,因為可以24小時不間斷 計算機五大組成部分 控制器 運算器 存儲器 輸入設備 輸出設備 計算機的核心真正干活的是CPU(控制器+運算器=中央處理器) 程序要想被計算機運行,它的代碼必須要先由硬盤讀到內存,之后cpu取指再執行 并發 看起來像同時運行的就可以稱之為并發 并行 真正...

    Java LinkedHashMap

    Java LinkedHashMap 前言 Map是我們在實際使用過程中常用的集合,HashMap在Java的實際開發中出鏡率很高,它通過hash算法實現了高效的非線程安全的集合,它有一個缺點就是,用戶插入集合的數據時無序,在我們需要一些有序的map的時候,我們就需要引入另外一個集合:LinkedHashMap。 LinkedHashMap是一個有序的非線程安全的集合,它是HashMap的子類,基...

    Spark Streaming處理文件(本地文件以及hdfs上面的文件)

    標題介紹文件流之前先介紹一下Dstream 下面是來自官網一段的說明,Discretized Streams或DStream是Spark Streaming提供的基本抽象。它表示連續的數據流,可以是從源接收的輸入數據流,也可以是通過轉換輸入流生成的已處理數據流。在內部,DStream由一系列連續的RDD表示,這是Spark對不可變的分布式數據集的抽象(有關更多詳細信息,請參見Spark編程指南)。...

    《痞子衡嵌入式半月刊》 第 8 期

    痞子衡嵌入式半月刊: 第 8 期 這里分享嵌入式領域有用有趣的項目/工具以及一些熱點新聞,農歷年分二十四節氣,希望在每個交節之日準時發布一期。 本期刊是開源項目(GitHub: JayHeng/pzh-mcu-bi-weekly),歡迎提交 issue,投稿或推薦你知道的嵌入式那些事兒。 上期回顧 :《痞子衡嵌入式半月刊: 第 7 期》 嘮兩句 今天是小滿,小滿節氣意味著進入了大幅降水的雨季。痞子...

    (C++)二叉樹的線索化 / 線索二叉樹

    好久不見,朋友們!雖然我知道沒人看我的博客,但我還是想叨逼叨一下。啊,好久沒編程了(其實也就一周沒編),但你們知道,程序員一天不編程那能叫程序員么???雖然我不是程序員哈哈哈哈哈,但還是要有基本素養嘛。 繼續寫二叉樹,給自己立一個flag,就是這幾天要寫完之前沒做完的幾道題,和二叉樹紅黑樹各種樹之類的~~雖然有這個flag,但我還是很實誠地遵從自己的內心,買了一張明天的電影票,等我回來告訴你們好不...

    精品国产乱码久久久久久蜜桃不卡