【Java】HashMap源碼(1.7)

Life is not a ridiculous number of life, the meaning of life lies in life itself

HashMap源碼

散列集

數組和鏈表可以保持元素插入的順序,對數組來說,他的優點是擁有連續的存儲空間,因此可以使用元素下標快速訪問,但缺點在于如果要在數組中第n位刪除或插入一個新元素,就需要移動n后面的所有元素,比如在ArrayList中刪除某個元素就是調用系統的arraycopy方法將數組要刪除的元素后面的所有元素向前復制一位得到的。

private void fastRemove(int index) {modCount++;int numMoved = size - index - 1;if (numMoved > 0)// 將elementData中從index + 1開始的numMoved長度的元素復制到elementData的index位置System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // clear to let GC do its work
}

并且定義數組時必須指定容量,如果需要擴容就得重新申請一個更大的數組,然后把原來的數據復制到新數組中,

這就導致數組查詢很快,但增刪性能不高。

而對鏈表來說,它的內存空間不是連續的,也就不需要考慮容量問題,但這就導致鏈表的查詢需要逐個遍歷LinkedList中雖然可以通過索引來get元素,但也是從頭部開始遍歷的(如果索引大于size/2就從尾部遍歷),效率很低。

散列集(hash table)可以說是數組與鏈表的組合,

UTOOLS1586163610224.png

往散列集中添加元素時,通過hash函數可以得到一個該元素的一個哈希值,Java中哈希值的范圍在-2147483648~2147483647之間,Object類的hashCode()方法可以返回對象的哈希值,通過hashCode可以確定將該元素存到哪一個數組中,

不能直接使用hashCode,因為它的范圍將近40億,不可能有這么大的數組空間,所以需要對hashCode值做一定的處理,使之在數組容量范圍內,最簡單的辦法是對數組容量取余,但取余有效率問題,所以Java使用了&操作,

如果key是null, 就返回0,否則返回原來哈希值與哈希值右移16位后的結果

比如一個元素的hashCode經過運算得到的值是5,他就會被放在第六個數組中。

應為數組容量是有限的,就一定存在運算后得到同樣索引值的情況,稱為哈希碰撞,解決哈希碰撞有兩種方法:開放地址法拉鏈法 ,開放地址法是指如果當前的數組已經有元素了,就通過別的算法算出一個新位置插入,像python中dict的實現就使用了開放地址法;而Java中則使用了后者——拉鏈法,他的思路是如果當前位置有元素了,就把新元素鏈到舊元素上。

jdk 1.7 以及之前拉鏈使用一個鏈表實現,每次有沖突的新元素過來就會把新元素放到數組中,原來的舊鏈鏈接到新元素后面【頭插法】;

jdk 1.8 開始加入了紅黑樹,如果數組某個位置的長度超過8并且數組容量超過32就會把鏈表轉換為紅黑樹,如果紅黑樹經過刪除節點數小于6,就會把樹重新轉換回鏈表,以此來提高效率。

JDK 1.7 中的實現

jdk 1.7 以及之前那個數組是Entry類型的,里面封裝了key和value,也就是鏈表的一個節點。

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

基本屬性

// 數組的默認大小,必須是2的倍數, 默認16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16// 數組最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;// 默認負載因子,如果數組中75%被占滿,就要擴容
static final float DEFAULT_LOAD_FACTOR = 0.75f;// hashMap中數據的數量
transient int size;// 與快速失敗有關
transient int modCount;

put方法

public V put(K key, V value) {if (table == EMPTY_TABLE) {// 初始化一個數組inflateTable(threshold);}// key為null的情況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;
}

如果當前table是空的的時候(實例化后第一次執行put),需要通過inflateTable()對哈希表進行初始化

private void inflateTable(int toSize) {// Find a power of 2 >= toSize// 計算實際的數組大小int capacity = roundUpToPowerOf2(toSize);// 計算出擴容的臨界值thresholdthreshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);// 實例化一個新數組table = new Entry[capacity];initHashSeedAsNeeded(capacity);
}

由于數組容量要求是2的倍數,所以這個方法會先通過roundUpToPowerOf2()根據我們指定的數組容量計算出真實的數組容量capacity,然后實例化一個capacity大小的Entry數組。最后這個initHashSeedAsNeeded()允許你配置一個哈希種子,來手動影響散列結果。

初始化后,由于HashMap允許null作為key值,所以如果key是null,就執行putForNullKey()方法把null: value存入哈希表.

private V putForNullKey(V value) {// 遍歷數組0位的鏈表for (Entry<K,V> e = table[0]; e != null; e = e.next) {// 如果數組0位鏈表某個節點key也是null,就替換該節點的值,返回舊值。if (e.key == null) {V oldValue = e.value;e.value = value;// 空方法e.recordAccess(this);return oldValue;}}// 如果0位沒有key為null的節點,就創建新節點并加入鏈表modCount++;addEntry(0, null, value, 0);return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {// 如果HashMap中元素的數量大于臨界值并且發生了沖突,就擴容if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length);hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}// 創建新的Entry對象createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {// 原來的鏈表Entry<K,V> e = table[bucketIndex];// 實例化一個新的Entry對象,next指向舊的鏈表etable[bucketIndex] = new Entry<>(hash, key, value, e);// 元素個數加一size++;
}
  1. HashMap允許null作為key,并且這個元素始終放在數組第0位

回到正常情況,key是null就確定它存放在數組0位,但其他的key就需要通過計算得到index值,jdk1.7中首先在hash()方法中對對象原本的hashCode做一系列移位操作后,再在indexFor()方法中與數組長度做與運算得出對象最終應該被放在數組的哪一位。

final int hash(Object k) {// 可以設置環境變量來提供一個哈希種子int h = hashSeed;if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}// 這個種子會通過與對象原來的hashCode做異或從而影響最終散列效果h ^= k.hashCode();h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {return h & (length-1);
}

出于性能的考慮,在獲得最終的index時,Java采用了&操作而不是更簡單的取余,這就導致數組長度必須是2的倍數,同時hash()方法中多次移位和異或也是應為這樣。

比如一個字符串 “重地” 通過 hashCode()方法得到它原先的hashCode值為 1179395,假設數組沒擴容,哈希種子是默認值0,那它計算index的過程應該是:

  1. 與hashSeed做異或,得到的還是它本身

  2. 右移20位的結果與右移12位的結果做異或

    h =         : 0000 0000 0001 0001 1111 1111 0000 0011 (1179395)
    a = h >>> 20: 0000 0000 0000 0000 0000 0000 0000 0001 (1)
    b = h >>> 12: 0000 0000 0000 0000 0000 0001 0001 1111? (287)
    ----------------------------------------------------------------
    a ^ b =     : 0000 0000 0000 0000 0000 0001 0001 1110 (286)
    h =         : 0000 0000 0001 0001 1111 1111 0000 0011 (1179395)
    ----------------------------------------------------------------
    h =         : 0000 0000 0001 0001 1111 1110 0001 1101 (1179165)
    c = h >>> 7 : 0000 0000 0000 0000 0010 0011 1111 1100
    ----------------------------------------------------------------
    h ^ c =     : 0000 0000 0001 0001 1101 1101 1110 0001
    d = h >>> 4 : 0000 0000 0000 0001 0001 1101 1101 1110
    ----------------------------------------------------------------
    h ^ d =     : 0000 0000 0001 0000 1100 0000 0011 1111
    len - 1     : 0000 0000 0000 0000 0000 0000 0000 1111
    ----------------------------------------------------------------
    index &     : 0000 0000 0000 0000 0000 0000 0000 1111
    

    到最后發現,真正參與運算的只有低四位,之所以做多次位移和異或運算,就是為了把hashCode的高位也參與到最后的與運算中,讓得到的index盡量分散,如果把最高位用A表示,可以看到經過上面的算法,最高位究竟影響了哪些位置:

    h =         : A000 0000 0001 0001 1111 1111 0000 0011 (1179395)
    a = h >>> 20: 0000 0000 0000 0000 000A 0000 0000 0001 (1)
    b = h >>> 12: 0000 0000 0000 A000 0000 0001 0001 1111? (287)
    ----------------------------------------------------------------
    a ^ b =     : 0000 0000 0000 A000 000A 0001 0001 1110 (286)
    h =         : 0000 0000 0001 0001 1111 1111 0000 0011 (1179395)
    ----------------------------------------------------------------
    h =         : 0000 0000 0001 A001 111A 1110 0001 1101 (1179165)
    c = h >>> 7 : 0000 0000 0000 0000 001A 0011 11A1 1100
    ----------------------------------------------------------------
    h ^ c =     : 0000 0000 0001 A001 110A 1101 11A0 0001
    d = h >>> 4 : 0000 0000 0000 0001 A001 110A 1101 11A0
    ----------------------------------------------------------------
    h ^ d =     : 0000 0000 0001 A000 110A 000A 00A1 11A1
    len - 1     : 0000 0000 0000 0000 0000 0000 0000 1111
    ----------------------------------------------------------------
    index &     : 0000 0000 0000 A000 000A 000A 00A0 11A1
    

    最高位最后影響了低四位。

    為什么數組容量要是2的倍數

    讓與運算之后的結果分布在 0 ~ (len -1) 之間

算出index之后的代碼邏輯就和putForNullKey差不多了,唯一的區別在于:

if (e.hash == hash && ((k = e.key) == key || key.equals(k))){...}

這樣設計的原因在于:

  • 哈希值不同一定不是同一個對象
  • 同一個對象哈希值不一定相同

擴容

是否擴容的判斷在addEntry方法中,如果滿足擴容條件,是先擴容,再添加新元素

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

擴容需要滿足兩個條件:

  1. HashMap中元素個數大于等于threshold
  2. 即將要新插入的元素發生了沖突

第一個條件 size是總元素個數,但threshold是根據數組容量算的。

threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
void resize(int newCapacity) {// 得到舊數組的引用Entry[] oldTable = table;int oldCapacity = oldTable.length;// 如果舊數組已經不能再長了,就不擴容了if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}// 創建一個2倍舊數組大小的新數組Entry[] newTable = new Entry[newCapacity];// 將舊數組的元素轉移到新數組transfer(newTable, initHashSeedAsNeeded(newCapacity));table = newTable;// 重新計算擴容臨界值threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

擴容最核心的就是數據轉移,也就是transfer()方法

void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;// 第一重循環遍歷數組for (Entry<K,V> e : table) {// 第二重循環遍歷鏈表while(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}int i = indexFor(e.hash, newCapacity);// 到這又變成了尾插e.next = newTable[i];newTable[i] = e;e = next;}}
}

由于數組容量變了兩倍,所以index也許需要重新計算,但計算中其實前面的步驟都一樣,只不過最后一步時 length - 1 在最前面多了一個1,所以哪怕index值改變,變化后的index與原來的也是2的倍數關系(1.8中用到了這個規律)

擴容過程中出現的循環鏈表的情況

UTOOLS1586269660885.png

這是兩個線程進入transfer后一開始的情況(兩個線程現在都有了自己新的數組),如果線程1正常執行完成,線程2阻塞在Entry<K,V> next = e.next;之后,那結果就是:

UTOOLS1586274296957.png

然后線程2開始執行

UTOOLS1586274868757.png

就出現了循環鏈表的情況。

參考

參考2

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/457472.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/457472.shtml
英文地址,請注明出處:http://en.pswp.cn/news/457472.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Docker 基本用法

1.安裝&#xff1a; wget http://mirrors.yun-idc.com/epel/6/i386/epel-release-6-8.noarch.rpm rpm -ivh epel-release-6-8.noarch.rpm yum install docker-io -y2.獲取鏡像 pull docker pull ubuntu docker pull ubuntu:14.043.運行這個鏡像&#xff0c;在其中運行bash應用…

畫刷的使用

1.畫刷的定義&#xff1a; HBRUSH hBrush; windows 自定義的畫刷&#xff1a; WHITE_BRUSH、LTGRAY_BRUSH、GRAY_BRUSH、DKGRAY_BRUSH、BLACK_BRUSH和NULL_BRUSH &#xff08;也叫HOLLOW_BRUSH&#xff09; 獲取方法如下&#xff1a; hBrush (HBRUSH) GetStockObject (GRAY_BR…

dataframe 控對象_iOS知識 - 常用小技巧大雜燴

1&#xff0c;打印View所有子視圖po [[self view]recursiveDescription]2&#xff0c;layoutSubviews調用的調用時機* 當視圖第一次顯示的時候會被調用。* 添加子視圖也會調用這個方法。* 當本視圖的大小發生改變的時候是會調用的。* 當子視圖的frame發生改變的時候是會調用的。…

【Java】jdk 1.8 新特性——Lambda表達式

Lambda表達式 jdk 1.8 新加入的特性&#xff0c;簡化了簡單接口的實現 函數式接口 函數式中只有一個待實現的方法&#xff0c;可以使用FunctionalInterface注解標注函數式接口.這個接口中只能有一個待實現的方法&#xff0c;但可以包含默認方法&#xff0c;靜態方法以及Obje…

【Todo】Java8新特性學習

參考這篇文章吧&#xff1a; http://blog.csdn.net/vchen_hao/article/details/53301073 還有一個系列轉載于:https://www.cnblogs.com/charlesblc/p/6123380.html

jsp調整字體大小font_html font標簽如何設置字體大小?

首先我們先來看看htmlfont標簽是如何來設置字體大小的&#xff1a;都只到htmlfont標簽是個專門用來設置字體的標簽&#xff0c;雖然在html5中用的會很少(因為都用css樣式來設置font標簽里面的屬性)&#xff0c;但是個人覺得font標簽還是相當強大的標簽的&#xff0c;為什么這么…

runtime官方文檔

OC是一種面向對象的動態語言&#xff0c;作為初學者可能大多數人對面向對象這個概念理解的比較深&#xff0c;而對OC是動態語言這一特性了解的比較少。那么什么是動態語言&#xff1f;動態語言就是在運行時來執行靜態語言的編譯鏈接的工作。這就要求除了編譯器之外還要有一種運…

【Java】synchronized關鍵字筆記

Java Synchronized 關鍵字 壹. Java并發編程存在的問題 1. 可見性問題 可見性問題是指一個線程不能立刻拿到另外一個線程對共享變量的修改的結果。 如&#xff1a; package Note.concurrency;public class Demo07 {private static boolean s true;public static void mai…

sql語句分析是否走索引_MySql 的SQL執行計劃查看,判斷是否走索引

在select窗口中&#xff0c;執行以下語句&#xff1a;set profiling 1; -- 打開profile分析工具show variables like %profil%; -- 查看是否生效show processlist; -- 查看進程use cmc; -- 選擇數據庫show PROFILE all; -- 全部分析的類型show index from t_log_account; ##查看…

SQL Server-數據類型(七)

前言 前面幾篇文章我們講解了索引有關知識&#xff0c;這一節我們再繼續我們下面內容講解&#xff0c;簡短的內容&#xff0c;深入的理解&#xff0c;Always to review the basics。 數據類型 SQL Server支持兩種字符數據類型&#xff0c;一種是常規&#xff0c;另外一種則是Un…

【隨記】SQL Server連接字符串參數說明

廢話不多說&#xff0c;請參見 SqlConnection.ConnectionString 。 轉載于:https://www.cnblogs.com/xiesong/p/5749037.html

【設計模式 00】設計模式的六大原則

設計模式的六大原則 參考&#xff1a; 設計模式六大原則 1. 單一職責原則 一個類只負責一個明確的功能 優點&#xff1a; 降低類的復雜度&#xff0c;提高代碼可讀性和可維護性降低變更時對其他功能的影響 2. 里氏替換原則 **原則一&#xff1a;**若 o1 是 C1 的一個實例化…

pb retrieve時停止工作_大佬們掛在嘴邊的PE、PB是什么?

在緊鑼密鼓地準備科創50ETF的發行工作間隙&#xff0c;今天小夏先帶你讀懂最簡單的PE、PB估值指標這兩大指標。01、什么是PE&#xff08;市盈率&#xff09;PE&#xff0c;也就是市價盈利比率&#xff0c;簡稱市盈率。市盈率是指股票價格與每股收益&#xff08;每股收益&#x…

EF CodeFirst 如何通過配置自動創建數據庫當模型改變時

最近悟出來一個道理&#xff0c;在這兒分享給大家&#xff1a;學歷代表你的過去&#xff0c;能力代表你的現在&#xff0c;學習代表你的將來。 十年河東十年河西&#xff0c;莫欺少年窮 學無止境&#xff0c;精益求精 本篇為進階篇&#xff0c;也是彌補自己之前沒搞明白的地方,…

對AutoIt中控件和窗口的理解

經過嘗試&#xff0c;對AutoIt中Control和Window有了新的認識&#xff0c;分享一下 1.Control 現在我想對一個WinForm架構的應用程序進行自動化操作&#xff0c;得到控件Advanced Mode屬性為[Name:XXX]。 然而在該窗口中有多個相同屬性的Control&#xff0c;而依該屬性只能操作…

【設計模式 01】簡單工廠模式(Simple factory pattern)

簡單工廠模式 可以根據參數的不同返回不同類的實例 參考&#xff1a; CSDN|簡單工廠模式 簡單工廠通過傳給工廠類的參數的不同&#xff0c;返回不同的對象&#xff0c;包括三部分組成&#xff1a; 具體的”產品“工廠類&#xff08;實例化并返回”產品“&#xff09;客戶端&am…

[Hadoop]MapReduce多路徑輸入與多個輸入

1. 多路徑輸入 FileInputFormat是所有使用文件作為其數據源的 InputFormat 實現的基類&#xff0c;它的主要作用是指出作業的輸入文件位置。因為作業的輸入被設定為一組路徑&#xff0c; 這對指定作業輸入提供了很強的靈活性。FileInputFormat 提供了四種靜態方法來設定 Job 的…

pvrect r語言 聚類_R語言實現KEGG通路富集可視化

用過KEGG的朋友應該都很熟悉里面的通路地圖。你是否想過如果自己可以控制通路圖將自己的基因繪制在一個通路圖中&#xff0c;那么今天給大家介紹一個新推出的Bioconductor軟件包pathview。這個包可以進行KEGG富集分析。首先&#xff0c;我們不耐煩的介紹下Bioconductor包的安裝…

【設計模式 02】策略模式( Strategy)

策略模式 參考&#xff1a; CSDN | 策略模式百家號 | 策略模式 如果某個系統需要不同的算法&#xff08;如超市收銀的優惠算法&#xff09;&#xff0c;那么可以把這些算法獨立出來&#xff0c;使之之間可以相互替換&#xff0c;這種模式叫做策略模式&#xff0c;它同樣具有三個…

PL/SQL復合變量

復合變量可以將不同數據類型的多個值存儲在一個單元中。由于復合類型可以由用戶自己根據需要定義其結構&#xff0c;所以復合數據類型也稱為自定義數據類型。在PL/SQL中&#xff0c;使用%TYPE聲明的變量類型與數據表中字段的數據類型相同&#xff0c;當數據表中字段數據類型修改…