【Java】HashMap源碼分析——基本概念

来源:https://www.cnblogs.com/a526583280/archive/2018/10/10/9769766.html
-Advertisement-
Play Games

在JDK1.8後,對HashMap源碼進行了更改,引入了紅黑樹。在這之前,HashMap實際上就是就是數組+鏈表的結構,由於HashMap是一張哈希表,其會產生哈希衝突,為瞭解決哈希衝突,HashMap採用了開鏈法,即對於用對象hashCode值計算哈希表數組下表時,當出現相同情況時,會在相同的地方 ...


在JDK1.8後,對HashMap源碼進行了更改,引入了紅黑樹。
在這之前,HashMap實際上就是就是數組+鏈表的結構,由於HashMap是一張哈希表,其會產生哈希衝突,為瞭解決哈希衝突,HashMap採用了開鏈法,即對於用對象hashCode值計算哈希表數組下表時,當出現相同情況時,會在相同的地方追加形成鏈表的形式。對於分佈均勻的情況下,僅僅是一個一維數組,查詢時時間複雜度為O(1),當分佈不均勻的時候,在有的地方會形成鏈表,極端情況下完全退化成一個鏈表,查詢時就需要遍歷整個鏈表,時間複雜度就為O(n),極為耗時。
在引入紅黑樹後,當滿足一定條件時,鏈表就會轉換成一棵紅黑樹。紅黑樹是一種AVL樹(自平衡查找二叉樹),相比於鏈表,其查找時的時間複雜度還是很優秀的(O(logn))!

先瞭解一下HashMap的模型:

其中的Node結點存放我們的鍵值對<K, V>;
首先,我們先瞭解HashMap給出的幾個重要指標:

1 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  // 預設的初始化容量大小為16
2 static final int MAXIMUM_CAPACITY = 1 << 30; // HashMap最大容量1G
3 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 預設負載因數值0.75,用於擴容時的計算
4 static final int TREEIFY_THRESHOLD = 8; // 樹的閾值,當鏈表長度大於等於8時,由鏈表轉換成紅黑樹
5 static final int UNTREEIFY_THRESHOLD = 6; // 鏈表的閾值,暫時不清楚
6 static final int MIN_TREEIFY_CAPACITY = 64; // 最小樹容量64

以上就是幾個基本指標,其規定了在以後操作中的界限!
其中Node<K, V>是一個內部類,封裝了這個結點的所有信息,有如下幾個成員

1 final int hash;   
2 final K key;      
3 V value;       
4 Node<K,V> next;

key和value不必多說,其中的hash是利用key對象的hashCode計算得到的,具有唯一性:

1  static final int hash(Object key) {
2         int h;
3         // 可以看到hash是根據對象的hashCode值來計算
4         // hashCode是一個int值,有32位
5         // 最後改變的是其低16位
6         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
7  }

其中的next就是為瞭解決哈希衝突,當產生哈希衝突時,next就可以指向一張鏈表,或者一棵黑樹!

 

接下來是幾個重要的成員:

1  transient Node<K,V>[] table; // 這就是真正的HashMap,一張哈希表,實際上就是由Node結點組成的一維數組
2  transient int size; // 記錄table中真正有效的結點個數,也就是鍵值對的個數
3  int threshold;  // 用來記錄當前容量下,最適合存放多少鍵值對(容量*負載因數)
4  final float loadFactor; // 負載因數,若在構造方法沒有特別設置,都是預設0.75
5  transient int modCount;  // 用來記錄操作數

看到這,我們先不急著往下進行,先仔細分析下這些成員之間的關係:
table:真正開闢的空間,其length就是真正的容量大小
size: 真正使用的空間,總的鍵值對的個數
threshold:這個就比較有意思,其決定了是否需要進行擴容的操作,是一個閾值!
比如說,在初始化時,預設的容量是16,那麼table的length就是16,其threshold=容量×負載因數=16×0.75=12,這就代表著,當size大於12時,就會進行擴容(容量會×2,threshold會根據新容量重新計算)的操作!
這樣做的目的很明確,就是為了減少哈希衝突!有效元素的個數少於哈希表的總大小時,其產生哈希衝突的可能性一定是小於相等情況的!
綜上可知,在非極限情況下(容量=threshold=MAXIMUM_CAPACITY=2^30)時,threshold總是小於容量,size總是不大於threshold!
這一切的做法,都是為了能夠減少哈希衝突產生的可能性!


說到這裡還是不能往下進行,我們需要知道Node中的hash成員是如何與table中的下標產生對應關係的,以及哈希衝突是如何產生的:

首先是關於hash值和table下標的映射:

1 index =   hash  & (table.length - 1)

這是一個非常巧妙的運算,當table.length滿足二的整數冪時,就滿足:
hash & (table.length - 1) == hash % table.length
例如:2%8 = 2 即:
0000 0010 2
&
0000 0111 (8 - 1)
0000 0010
二的整數冪減一得到的二進位數,其有效位全是1,通過&可以直接得到符合條件的有效位的值!
其實就是取餘,用餘數作為table的下標,而位運算的速度是比其餘快的多,所以採用了這種方式!
所以這就是為什麼table的大小必須是二的整數冪,以及擴容時都是乘2!

哈希衝突的產生:
以初始table.length = 16為例
對於hash = 1, 和 hash = 17來說,其對於16取餘的結果都是1,那麼這兩個不同的hash值對應了同一個table的下標,這就產生了哈希衝突!

先將HashMap簡單介紹到這,後續我會繼續分析HashMap,若有錯誤或不足之處,還請指出!

 

我在CSDN也放了一篇【Java】HashMap源碼分析——基本概念


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

-Advertisement-
Play Games
更多相關文章
  • 題目: Farmer John likes to play mathematics games with his N cows. Recently, they are attracted by recursive sequences. In each turn, the cows would sta ...
  • 8、redis集群怎麼做 1、Redis集群提供了以下兩個好處1、將數據自動切分(split)到多個節點2、當集群中的某一個節點故障時,redis還可以繼續處理客戶端的請求。2、集群的方案: redis-cluster集群,採用無中心結構,每個節點保存數據和整個集群狀態,每個節點都和其他所有節點連接 ...
  • 主要內容來自中文版的同名教程 "Go語言之旅" 其目的為總結要點 包,函數和變數 包 import 語法,多個用括弧換行擴起,包之間不需要間隔符,用引號引起 go import ( "fmt" "math/rand" ) // 官方認為分組導入比多個導入更好 // 用 引用包內對象,僅有首字母大寫的 ...
  • 引言 - 一切才剛剛開始 structc 是 C 結構基礎庫. 簡單有態度. structc - https://github.com/wangzhione/structc 之前推過幾次 structc, 沒什麼效果. 這次乘著最近加班不多, 來詳細解說哈 structc 的思考初衷. 0.0 整體 ...
  • 示例: 什麼是對象  《JAVA編程思想》對於對象的定義是:將問題空間中的元素以及它們在方案空間的表示物稱作“對象”。  1. 問題空間:實際解決的問題模型;  2. 方案空間: 電腦(機器模型)。  實際的問題在電腦(機器模型)中的表示稱為對象。在上面示 ...
  • [TOC] Dubbo入門 Editor:SimpleWu Dubbo是 阿裡巴巴公司開源的一個高性能優秀的服務框架使得應用可通過高性能的 RPC 實現服務的輸出和輸入功能,可以和 Spring框架無縫集成。 背景 隨著互聯網的發展,網站應用的規模不斷擴大,常規的垂直應用架構已無法應對,分散式服務架 ...
  • 經過上一篇教程的學習,我們知道對象將它的狀態存在域中。然而,Java中也使用了“變數”這個術語。在這一篇教程中,我們將會討論它們之間的關係,以及變數命名的規則和慣例,基本數據類型以及它們的預設值和字面量。 ...
  • JVM學習筆記1:Java虛擬機記憶體模型 學習JVM,Java虛擬機對理解Java程式執行過程和Java程式性能調優具有很大幫助。本系列博客旨在由淺到深學習並理解JVM。參考閱讀:《深入理解Java虛擬機 JVM高級特性和最佳實踐》。這個書寫的非常好,推薦有條件的讀者買一本來閱讀,網上也有電子版的。 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 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 ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...