JDK1.7的HashMap的put(key, value)源碼剖析

来源:https://www.cnblogs.com/zc-programer/archive/2018/11/10/9940591.html
-Advertisement-
Play Games

HashMap的put操作源碼解析 [toc] 1、官方文檔 1.1、繼承結構 1.2、類型參數： 2、put(key, value) HashMap是一種以鍵——值對的形式來存儲數據的數據結構。HashMap允許使用 null 值和 null 鍵，它並不能保證你存放數據和取出的順序是一致的。 接下 ...


目錄

HashMap的put操作源碼解析

1、官方文檔

1.1、繼承結構

java.lang.Object
  java.util.AbstractMap<K,V>
      java.util.HashMap<K,V>

1.2、類型參數：

K - 此映射所維護的鍵的類型
V - 所映射值的類型

2、put(key, value)

HashMap是一種以鍵——值對的形式來存儲數據的數據結構。HashMap允許使用 null 值和 null 鍵，它並不能保證你存放數據和取出的順序是一致的。

接下來就以下麵的代碼來看一下put是怎麼將數據存放到map中的。 

public class HashMapTest {
    public static void main(String[] args) {
        Map<String, Object> map = new HashMap<String, Object>();
        map.put(null, "map-value");
        map.put(map-key", "map-value");
        
        System.out.println(map);
    }
}

2.1、重點源碼部分截取

在map.put()這裡打個斷點F5(我用的eclipse)跟蹤進去。我們就會進到put方法中： 

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

這裡的EMPTY_TABLE是HashMap的一個靜態常量，是一個Entry數組，預設值是空數組，table是HashMap的一個屬性且其預設值就是EMPTY_TABLE，這個table也就是我們數據存放的地方，至此為止可以知道，HashMap其實是一個數組，但它又不是一個純粹的數組。下麵會進行解釋。 

static final Entry<?,?>[] EMPTY_TABLE = {};

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

而這個Entry其實是HashMap的一個內部類，定義如下(僅截取部分代碼)，記住這個類，記住這個構造方法：它在new Entry的時候接收了一個Entry對象，並將自己的next指向了傳入的Entry對象形成一個鏈表，其自身是表頭。

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

        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
}

從上面我們可以看出來這個Entry其實是一個鏈表，它存放了 key 和 value 並且還有一個指向下一個節點的引用 Entry， 剩下的這個 hash 就是 key 的哈希值。

現在我們可以捋一捋HashMap的結構了。首先HashMap是一個Entry數組，而這個Entry是一個單向鏈表，我們大致可以將其結構畫成如下圖所示：

2.2、put(key, value)源碼分析

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}
  1. 因為我們在實例化HashMap的時候使用的是無參構造方法，所以第一次 put 數據的時候table為空
if (table == EMPTY_TABLE) {
    inflateTable(threshold); 
}

上面這段代碼會被執行，inflateTable(threshold) 會將table初始化為一個長度為16的Entry數組。

  1. 它會對我們的key進行空判斷，如果是空就會執行下麵的代碼：
if (key == null)
        return putForNullKey(value);

  putForNullKey(value) 的實現如下：

private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}
2.2.1 、key為null的情況

  從上面可以看出來，如果key為null的話，它會從table中取出下標為0也就是第一個元素，沒忘記的話我們應該還知道它一個Entry，是一個鏈表，如果這個元素不是null，那麼就會遍歷這個鏈表，並判斷當前這個Entry節點對象的key是不是null。

  1. 如果是null(key相同了)： 使用oldValue來存放當前這個Entry節點對象的value，然後將我們新的值(map-value)賦給當前節點，再將原值oldValue返回回去。
  2. 如果遍歷完鏈表的所有節點都沒有找到key為null的節點就會調用addEntry(0, null, value, 0)，這個方法前面的if(){***}這塊代碼是判斷當前table是否要進行擴容。這裡只做簡單講述。

      size是當前table存放的Entry鏈表的個數，拿我上面畫的那個HapshMap結構來看就是4。

      如果我們實例化HashMap的時候沒有給大小那麼：threshold = loadFactor(負載因數預設為0.75f) * DEFAULT_INITIAL_CAPACITY(HashMap預設大小也就是table長度為16)，所以threshold = 12。

      如果我們給了大小為initialCapacity，那麼負載因數還是預設的0.75f，但是threshold不需要算了，值就是initialCapacity。如果我們同時給了HashMap的大小initialCapacity和負載因數loadFactor，那麼HashMap就使用我們給定的負載因數值作為新的負載因數，給定的HashMap大小作為threshold。ok第一個條件結束。

      null != table[bucketIndex]就很好理解了，就是我當前這個節點要存放的位置是空的。

      滿足上面兩個條件，HashMap就會進行擴容，擴容後的大小為擴容前的2倍，然後對key重新計算它的hash值以及數組下標。
  3. 繼續put內容，從上面源碼我們可以知道key為null的情況下它的hash值是0，至於bucketIndex的計算是這樣的h & (length-1)，也是將hash值與table的長度按位相與值也是。至此也就是確定了key為null的這個節點將存放在table的第一個位置上。然後就會調用createEntry(0, null, "map-value", 0);
  4. 在createEntry(int hash, K key, V value, int bucketIndex)這個方法里首先拿到table中下標為bucketIndex的鏈表的表頭：Entry<K,V> e = table[bucketIndex];然後再用Entry對象的構造方法new一個Entry將我們的hash值，key，value，鏈表的表頭作為參數傳入：table[bucketIndex] = new Entry<>(hash, key, value, e);就這樣我們的這個新節點就放在了原來的表頭的前面作為新的表頭了。沒看懂的再回到上面看一下Entry的構造方法，我有重點標註的。
2.2.2、 key不為null的情況

  源碼依舊拿下來

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}
  1. 首先說一下hash值：對於相同的key它們的hash值是相同的。但是hash值相同，它們的key卻不一定是相同的，這就是哈希碰撞。
  2. key不為null的話它會根據key算出這個key對就的hash值以及它的bucketIndex，然後拿到table中下標為bucketIndex的這個Entry鏈表，然後遍歷這個鏈表，判斷當前節點的hash其實也就是當前節點的key的hash是否等於我們傳入的map-key的hash，然後判斷當前節點的key是否與我們傳入的key相同。

      如果以上條件都滿足了，那麼就是key相同了，就會跟Key為null的分析中的第一條一樣將新值覆蓋舊值，並將舊值返回回去。

      如果遍歷完這個鏈表以上條件沒有得到滿足，那麼就會跟key為null的分析中的第四條一樣，獲得table下標為i的鏈表的表頭e，然後將我們的map-key, map-value, hash以及表頭e作為參數new一個新的Entry對象並將它的next指向原來的表頭e，它也就變成了新的表頭了。

3、完結

  最怕你的能力配不上你的野心。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Java設計模式中文版. pdf下載
    書中給出了模式的實際應用，我覺得很好。gong of four 中的例子太老了。有些例子可以歸入多個模式(Command 模式，是不是也是適配器模式呢？)，但是書中沒有提到，不知道是否是自己功力不夠，理解不到位。。。。 內容簡介 · · · · · · 《Java設計模式(第2版)》通過一個完整的J ...
  • SpringMVC入門學習(一)
    SpringMVC入門學習(一) ssm框架 spring SpringMVC是一個Java WEB框架，現在我們知道Spring了，那麼，何為MVC呢？ MVC是一種設計模式，其分為3個方面 model 模型：dao層和service層 view 視圖：例如jsp和Html controller ...
  • 《Nginx教程從入門到精通》免費下載
    很不錯的Nginx入門書，裡面有教你怎麼去做日誌切割，怎麼去做高併發，怎麼去統計流量帶寬等等。不要998，不要98，免費下載！！！ ...
  • java----類拾遺
    學了100多天java知道了要抓住本質、最底層學習，比如堆和棧啊，類是怎麼載入的啊，再深一點的話就要看編譯原理了，還是羡慕電腦專業的。 靜態成員不可調用非靜態成員，static稱為靜態，靜態成員的最根本作用是區分屬性，方法，內部類，初始化塊成員到底屬於類本身，還是屬於類的實例，有static修飾的 ...
  • PHP接收http請求頭信息
    1、PHP 自帶函數 getallheaders() 目前 getallheaders() 只能用於 apache 中。如果想在 nginx 中也能使用，可以使用自定義函數。 2、自定義函數 ...
  • rabbitmq學習筆記2——springboot 生產者項目
    創建項目 使用idea（版本2018.2），新建項目，使用spring initalizr，項目命名為名字為producer，選擇integration里的rabbitmq，確定。 配置rabbitmq服務 將預設生成的application.properties重命名為application.ym ...
  • PHP 匿名函數使用技巧
    之前寫過一篇閉包的使用(點擊此處進入),這次深入彙總下php中匿名函數的深入用法和理解： php中的匿名函數 也叫閉包函數 允許指定一個沒有名稱的函數。把匿名函數賦值給變數，通過變數來調用，舉個簡單的例子： 技巧1： 將匿名函數放在普通函數中，也可以將匿名函數返回，:這樣就構成了一個簡單的閉包 技巧 ...
  • HO引擎近況20181110
    公司的項目沒那麼忙了,而且可能項目組很快要去深圳了! 自己的引擎方面去掉了一些不必要的層級,儘量輕量級,簡單架構,模擬著一個新人接觸怎樣能上手來重新整理了一下! 游戲方面增加了C++類之後寫代碼熟多了,但是整體上大部分還是在藍圖中,有一些函數什麼的還在摸索! 女朋友還是一樣的每周末都住一下,好像一下 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類