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
  • WPF 已知問題 監聽 WMI 事件導致觸摸失效
    示例項目結構 在 Visual Studio 中創建一個 WinForms 應用程式後，項目結構如下所示： MyWinFormsApp/ │ ├───Properties/ │ └───Settings.settings │ ├───bin/ │ ├───Debug/ │ └───Release/ ...
  • [STAThread]特性
    [STAThread] 特性用於需要與 COM 組件交互的應用程式，尤其是依賴單線程模型（如 Windows Forms 應用程式）的組件。在 STA 模式下，線程擁有自己的消息迴圈，這對於處理用戶界面和某些 COM 組件是必要的。 [STAThread] static void Main(stri ...
  • UWP WinUI3 傳入 AddHandler 的 RoutedEventHandler 類型與事件所需不匹配將拋出參數異常
    在WinForm中使用全局異常捕獲處理 在WinForm應用程式中，全局異常捕獲是確保程式穩定性的關鍵。通過在Program類的Main方法中設置全局異常處理，可以有效地捕獲並處理未預見的異常，從而避免程式崩潰。 註冊全局異常事件 [STAThread] static void Main() { / ...
  • .NET 多版本 WinForm 開源控制項庫 SunnyUI
    前言 給大家推薦一款開源的 Winform 控制項庫，可以幫助我們開發更加美觀、漂亮的 WinForm 界面。 項目介紹 SunnyUI.NET 是一個基於 .NET Framework 4.0+、.NET 6、.NET 7 和 .NET 8 的 WinForm 開源控制項庫，同時也提供了工具類庫、擴展 ...
  • .net core8 使用Swagger（附當前源碼）
    說明 該文章是屬於OverallAuth2.0系列文章，每周更新一篇該系列文章（從0到1完成系統開發）。 該系統文章，我會儘量說的非常詳細，做到不管新手、老手都能看懂。 說明：OverallAuth2.0 是一個簡單、易懂、功能強大的許可權+可視化流程管理系統。 有興趣的朋友，請關註我吧(*^▽^*) ...
  • WPF 什麼時候 VisualTreeHelper.GetDescendantBounds 將返回無窮大
    一、下載安裝 1.下載git 必須先下載並安裝git，再TortoiseGit下載安裝 git安裝參考教程：https://blog.csdn.net/mukes/article/details/115693833 2.TortoiseGit下載與安裝 TortoiseGit，Git客戶端，32/6 ...
  • C# 開源教程帶你輕鬆掌握數據結構與演算法
    前言 在項目開發過程中，理解數據結構和演算法如同掌握蓋房子的秘訣。演算法不僅能幫助我們編寫高效、優質的代碼，還能解決項目中遇到的各種難題。 給大家推薦一個支持C#的開源免費、新手友好的數據結構與演算法入門教程：Hello演算法。 項目介紹 《Hello Algo》是一本開源免費、新手友好的數據結構與演算法入門 ...
  • 第22篇 生成proto文件bat腳本
    1.生成單個Proto.bat內容 @rem Copyright 2016, Google Inc. @rem All rights reserved. @rem @rem Redistribution and use in source and binary forms, with or with ...
  • 記一次 .NET某上位機視覺程式 卡死分析
    一：背景 1. 講故事 前段時間有位朋友找到我，說他的窗體程式在客戶這邊出現了卡死，讓我幫忙看下怎麼回事？dump也生成了，既然有dump了那就上 windbg 分析吧。 二：WinDbg 分析 1. 為什麼會卡死 窗體程式的卡死，入口門檻很低，後續往下分析就不一定了，不管怎麼說先用 !clrsta ...
  • 醫學DICOM文件與PACS系統進行數據傳輸
    前言 人工智慧時代，人臉識別技術已成為安全驗證、身份識別和用戶交互的關鍵工具。 給大家推薦一款.NET 開源提供了強大的人臉識別 API，工具不僅易於集成，還具備高效處理能力。 本文將介紹一款如何利用這些API，為我們的項目添加智能識別的亮點。 項目介紹 GitHub 上擁有 1.2k 星標的 C# ...
所有分類