關於hashmap的理解

来源:http://www.cnblogs.com/jwLee/archive/2017/09/16/7533105.html
-Advertisement-
Play Games

首先分析第一個比較重要的方法 put 方法,源碼如下 分析上面的源碼,我們可以得到下麵的結論: 當我們試圖將一個key-value 調用put方法放入HashMap的時候,首先會調用key的hashCode方法算出該Entry存放的位置,若兩個key的hashCode相同則在table中的存儲位置相 ...


首先分析第一個比較重要的方法 put 方法,源碼如下

public V put(K key, V value) {
if (key == null)
return putForNullKey(value);  //這裡判斷key是否為空,若為空則調用putForNullKey處理null值
int hash = hash(key); //根據key的hashCode計算hash值
int i = indexFor(hash, table.length);//搜索該key的hash值在table中的索引,其中table是當HashMap用於存放entry的一個數組

//這裡迴圈遍歷table中對應該索引的entry,若發現存在key與put進來的key相同則覆蓋其value值
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++;

//將key value 添加到 索引i處
addEntry(hash, key, value, i);
return null;
}

 

 

分析上面的源碼,我們可以得到下麵的結論:

當我們試圖將一個key-value 調用put方法放入HashMap的時候,首先會調用key的hashCode方法算出該Entry存放的位置,若兩個key的hashCode相同則在table中的存儲位置相同,則先調用equals方法判斷兩個key是否相同,相同則覆蓋,不相同則產生一個Entry鏈表(因為table數組中一個索引位置只能放入一個Entry,所以當有多個key的hashCode相同時,這些key就會以鏈表的形式存在,並且最後put進來的key在鏈表的最前面)

 

然後則是HashMap的構造方法,這裡以 HashMap(int initialCapacity, float loadFactor)這個構造器為例,源碼如下

public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);

// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;

this.loadFactor = loadFactor;
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();
}

 

從上面的源碼可以看出 ,初始容量不能為負數,若初始容量大於最大容量,則讓它等於最大容量,負載因數必須大於0,並且傳入的initialCapacity不是HashMap的容量大小,

實際容量大小的計算規則是大於傳入的initialCapacity的最小的2的n次方,比如傳入的initialCapacity是5 那麼實際容量則是8 因為2的3次方大於5。

 

下麵再分析一下HashMap的存儲性能,下麵的 get方法的源碼

public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);

return null == entry ? null : entry.getValue();
}

 

 

 

final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}

 

再次強調一下table的概念,table就是當我們初始化一個HashMap時,會自動創建一個長度為capacity的Entry數組,我們把這個數組存放元素的位置叫“桶”,並且每個桶只存儲一個Entry元素(也就是我們的鍵值對),並且當我們put一個鍵值對時,先計算key的hashCode來判斷這個鍵值對會放入哪一個桶,所以若多個key的hashCode相同時,他們都要被放入一個桶裡面,但是一個桶裡面只能放入一個Entry(鍵值對),要解決這個問題先看下麵的代碼

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

 

這時Entry的構造方法,我們可以看出Entry對象包含一個Entry的引用,用來指向下一個Entry,這樣就解決了hashCode相同,存放衝突的問題,所以當有多個key的hashCode相同時,就會形成一個Entry鏈,我們從get方法可以看出當系統通過key的hashCode找到了對應的桶的時候,會遍歷這個Entry鏈,來找到我們要取的value的key,這個時候,若剛好這個Entry在鏈表的末端(也就是我們最開始put進去的Entry)那麼當這個鏈表太長了,勢必會影響我們的查詢性能,這個時候就引出了loadFactor(負載因數的說法),HashMap的預設附在因數是0.75,我對負載因數的理解就是,表示HashMap在什麼時候擴容,也就是說若我們初始的HashMap容量是16 負載因數是0.75,那麼當有12個“桶”有了Entry時,HashMap

就會擴容,並且擴大的容量是原來容量的2倍,為什麼是12呢?因為0.75x16=12。並且負載因數是可以更改的,修改它的前提是如果記憶體比較緊張就可以適當的增加負載因數,

若空間,記憶體比較充足,更關註查詢效率則減少負載因數。為什麼會這樣呢?因為若負載因數減少了,比如說減少到了0.5,預設HashMap容量大小還是16,那麼當我有8個"桶"中存放了Entry數組時我就會擴容了,該桶里的Entry鏈相比於之前就不會那麼長,從而提升了查詢性能。

 

今天先到這裡,下次再寫。

 


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

-Advertisement-
Play Games
更多相關文章
  • 本文地址:http://www.cnblogs.com/aiweixiao/p/7535351.html 歡迎關註我的微信公眾號哈 “ 程式員的文娛情懷” http://t.cn/RotyZtu 【背景】:由於 file函數是一次性將所有內容讀入記憶體,而php為了防止一些寫的比較糟糕的程式占用太多的 ...
  • 博客園是個非常好的學習知識的地方,相信有很多人跟我一樣,園齡3年,從博客園不知道拷了多少代碼,看了多少博客,自己卻一篇博客都沒寫過。真是罪過。 這次準備寫幾篇關於這個項目源碼的閱讀和理解的文章,大家一起相互學習學習,我可能不會單單就寫源碼一類的東西,還會做很多擴展,比如新的c++的語法,其他的一些工 ...
  • 1 異常概述 2 異常體系 3 異常的原理 4 異常對象的拋出 5 自定義異常&異常類的拋出(throws) 6 異常的分類 7 throw和throws的區別? 8 異常的捕獲 9 異常處理的原則 10 異常的註意事項 ...
  • 簡介 網路無處不在,移動互聯時代也早已到來,單機版程式慢慢的已沒有生命力,所有的程式都要能夠訪問網路,比如 QQ 網路聊天程式、迅雷下載程式等,這些程式都要同網路打交道,本次將與各位小伙伴們分享的就是 Java 中的網路編程—— Socket 通信。 網路基礎知識 兩台電腦要通過網路進行通信,必須 ...
  • 一、添加 devtools 依賴 當配置了 devtools 後,我們在classpath修改任何文件項目都將會自動重啟。 (1)某些資源在更改時不一定需要觸發重新啟動。例如, Thymeleaf 模板可以就地進行編輯。預設情況下更改資源路徑包括了:/META-INF/maven, /META-IN ...
  • 最近做了幾道關於二分法的題目,覺得比較典型,因此拿出來說一說。 首先,先把題目分享一下。 題目描述:上題中講了一個故事,故事大意不用過多關註,有用部分為:某地主有一個大糧倉,這個糧倉容量為 n 個單位,但這個糧倉有個小口,每天會有一部分麻雀過來偷吃糧食,同時地主每天也會從別的地方運來糧食填補。開始的 ...
  • 我是一名建築學的學生,第一次瞭解到Python這門課是選課的時候。說實話,學c語言的時候我學的就並不好,感覺自己並沒有天分。我只是按照我的人才培養方案看課的時候才第一次看到這門課。起初並不知道這門課意味著什麼,就給軟工的朋友打電話咨詢。然後又上百度搜索,感覺還挺有用,就選了這門課。 一個建築生,平時 ...
  • 自己以前從來沒有寫博客的想法,但是學Python,裡面的老師也說了,寫博客可以加深自己的記憶,也能回顧內容。還能給別人參考。挺值的。2017-09-16 一、 Python介紹 python的創始人為吉多·範羅蘇姆(Guido van Rossum)。1989年的聖誕節期間,吉多·範羅蘇姆為了在阿姆 ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...