資訊專欄INFORMATION COLUMN
摘要：加載因子是哈希表在其容量自動增加之前可以達(dá)到多滿的一種尺度。當(dāng)哈希表中的條目數(shù)超出了加載因子與當(dāng)前容量的乘積時，則要對該哈希表進行操作即重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)，從而哈希表將具有大約兩倍的桶數(shù)。
一. hashmap簡介
HashMap是基于哈希表的Map接口的非同步實現(xiàn)。此實現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。
HashMap 是一個散列表，它存儲的內(nèi)容是鍵值對(key-value)映射。
HashMap 繼承于AbstractMap，實現(xiàn)了Map、Cloneable、java.io.Serializable接口。
HashMap 的實現(xiàn)不是同步的，這意味著它不是線程安全的。它的key、value都可以為null。此外，HashMap中的映射不是有序的。
HashMap 的實例有兩個參數(shù)影響其性能：“初始容量” 和 “加載因子”。容量 是哈希表中桶的數(shù)量，初始容量 只是哈希表在創(chuàng)建時的容量。加載因子 是哈希表在其容量自動增加之前可以達(dá)到多滿的一種尺度。當(dāng)哈希表中的條目數(shù)超出了加載因子與當(dāng)前容量的乘積時，則要對該哈希表進行 rehash 操作（即重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)），從而哈希表將具有大約兩倍的桶數(shù)。
通常，默認(rèn)加載因子是 0.75, 這是在時間和空間成本上尋求一種折衷。加載因子過高雖然減少了空間開銷，但同時也增加了查詢成本（在大多數(shù) HashMap 類的操作中，包括 get 和 put 操作，都反映了這一點）。在設(shè)置初始容量時應(yīng)該考慮到映射中所需的條目數(shù)及其加載因子，以便最大限度地減少 rehash 操作次數(shù)。如果初始容量大于最大條目數(shù)除以加載因子，則不會發(fā)生 rehash 操作。
二. hashmap數(shù)據(jù)結(jié)構(gòu)
大概了解hashmap之后，知道了hashmap的鍵值對映射，知道了hashmap的線程不安全，知道了hashmap的put，get方法。覺得自己足夠了解hashmap了嗎？并不是，接著，讓我們先去了解一下hashmap的底層數(shù)據(jù)結(jié)構(gòu)。
首先，ArrayList和LinkedList的數(shù)據(jù)結(jié)構(gòu)我們非常了解
ArrayList :
?>ArrayList 底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，查詢效率比較高，增刪效率比較低。
可以參照一下Arraylist的源碼，可以看出Arraylist的數(shù)據(jù)結(jié)構(gòu)為數(shù)組
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
LinkedList:
LinkedList 底層數(shù)據(jù)是鏈表（雙向鏈表），查詢效率比較低，增刪效率比較高。
源碼驗證：可以看出LinkedList為雙向鏈表結(jié)構(gòu)
1 private static class Node{ 2 //數(shù)據(jù) 3 E item; 4 //后面數(shù)據(jù) 5 Node next; 6 //前面數(shù)據(jù) 7 Node prev; 8 9 Node(Node prev, E element, Node next) { 10 this.item = element; 11 this.next = next; 12 this.prev = prev; 13 } 14 }
由此看來，ArrayList查詢速度快，增刪慢，LinkedList查詢速度慢，增刪快，那么，如果我們想查詢速度快并且增刪慢的話，將兩種數(shù)據(jù)結(jié)構(gòu)相結(jié)合，就是我們要講的HashMap
HashMap : 數(shù)組? +? 鏈表
在這樣的數(shù)據(jù)結(jié)構(gòu)中，如果我們想存放數(shù)據(jù)的話，除了map中一定要有的Key和Value，還要有指向下個單元的next，根據(jù)剛才數(shù)據(jù)結(jié)構(gòu)的分析，可以猜想到Hashmap的存儲單元應(yīng)該是這樣的：
Class Node{
Key;
Value;
Node next;
}
讓我們帶著我們的猜想去看一下HashMap的源碼，果然，我們的猜想是正確的，源碼如下
/** * Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.) *
* 基本的hash存儲單元
/
static class Node implements Map.Entry { final int hash; final K key;
V value;
Node next;
Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = value; this.next = next;
} public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value);
} public final V setValue(V newValue) {
V oldValue = value;
value = newValue; return oldValue;
} public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) {
Map.Entry e = (Map.Entry)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true;
} return false;
}
}
?大家看到源碼中的變量，正如我們所猜想的一樣，有Key、Value還有Node
那么，在HashMap中，數(shù)組和鏈表究竟是怎樣表示的？在源碼中是如何體現(xiàn)的呢？我們接著去猜想驗證。
1. 數(shù)組的表示
平時我們表示數(shù)組，如字符串?dāng)?shù)組，是String[]，整型數(shù)組是Integer[]，那在HashMap中，他的基本單元是node，那假如我們是HashMap的源碼編寫人員，那么我們可以寫成
Node[] table;
table是我們隨意取的變量值。接著，我們?nèi)ピ创a中去看看在HashMap中數(shù)組是如何定義表示的：
/** * The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.) */
transient Node[] table;
果然和我們猜想的一樣，在HashMap中的數(shù)組是以Node
2. 數(shù)組的大小是如何定義設(shè)置的呢
初始化大小：
/** * The default initial capacity - MUST be a power of two.必須是2的n次冪 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
這里我們可以看到數(shù)組的初始化大小為 1 << 4 ，這里是個位運算，1 << 4 是 1000，轉(zhuǎn)化為十進制是16(位運算更快一些)
最大容量：
/** * The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30. */
static final int MAXIMUM_CAPACITY = 1 << 30;
當(dāng)數(shù)組的大小如果不夠用了，就要進行擴容。但是并不是全部都用完了再去擴容，如果全部用完再去擴容的話，性能會下降，存取效率也會受到影響。在HashMap中，如果用了數(shù)組大小的0.75倍，也就是四分之三的容量之后，就需要擴容
/** * The load factor used when none specified in constructor. */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
如數(shù)組大小定義為16,當(dāng)超過12的時候，就要求去進行擴容，那么在HashMap中肯定會有一個值去記錄目前占用的空間內(nèi)存:
/** * The number of key-value mappings contained in this map. */ transient int size;
我們用size來記錄目前占用的空間內(nèi)存，大家看一下HashMap中最常用的put方法中有這么一串代碼：
if (++size > threshold)
resize();
// (The javadoc description is true upon serialization. // Additionally, if the table array has not been allocated, this // field holds the initial array capacity, or zero signifying // DEFAULT_INITIAL_CAPACITY.)
int threshold;
這串代碼的含義是什么呢？
每當(dāng)我們往HashMap中put一個值后，size就會增加1，這個threshold我們通過英文注釋可以了解到，這個變量就是我們之前說的那個要求擴容的臨界值，是現(xiàn)有內(nèi)存的0.75倍。當(dāng)現(xiàn)在的內(nèi)容超過這個臨界值時，就需要進行擴容了。
?3.鏈表的長度是如何限制的呢？
讓我們?nèi)ピ创a中看一下在Hashmap中鏈表的長度是如何限制的呢？
/** * The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage. */
static final int TREEIFY_THRESHOLD = 8;
在源碼中我們可以看到HashMap鏈表的長度限制為8。但是，通過英文注釋我們可以看到，當(dāng)鏈表的長度并不是不能超過8，當(dāng)長度大于8時，數(shù)據(jù)結(jié)構(gòu)會變形，表現(xiàn)形式就變成了紅黑樹(JDK1.8之后)。
?三. 源碼分析
基本的數(shù)據(jù)結(jié)構(gòu)和Hashmap的設(shè)計思想我們已經(jīng)大概了解了，現(xiàn)在我們要去正式的走近HashMap的源碼了
HashMap最核心的代碼肯定是我們經(jīng)常用的put和get方法。
put方法：
/** * Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with key, or
* null if there was no mapping for key.
* (A null return can also indicate that the map
* previously associated null with key.) */
public V put(K key, V value) { return putVal(hash(key), key, value, false, true);
}
在put方法中，key和value這兩個參數(shù)我們已經(jīng)了解了，那么，這個hash(key)是什么含義呢？
首先，我們要先考慮一個問題，每當(dāng)一個node結(jié)點進入HashMap中時，究竟該放入哪里呢？
結(jié)論就是：這個key值通過這個hash函數(shù)過濾之后的數(shù)值就是存放位置的一個標(biāo)識，讓我們?nèi)タ匆幌逻@個hash函數(shù)是如何實現(xiàn)的
static final int hash(Object key) {
int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
從這里我們可以看出，這個不僅僅是得到key的hashcode值那么簡單，還做了一些操作，那么為什么要如此復(fù)雜的計算這個數(shù)值呢？
這是因為hashcode容易重復(fù)，不同的元素存儲時容易處在同一個數(shù)組的下標(biāo)位置，還有一個問題，這個hashcode值較大，容易出現(xiàn)數(shù)組越界的問題。?
這里將hashcode值與他本身向右位移了16位的值做了一個異或。總結(jié)一下就是：
hash函數(shù)就是將高16位和低16位做一個異或運算，然后得到一個結(jié)果來確定node節(jié)點的存放位置
作用：盡量讓Node落點分布均勻，減少碰撞的一個概率，如果碰撞概率高了，就勢必導(dǎo)致數(shù)組下標(biāo)下的鏈表長度太長。
在這里，我們舉個具體的數(shù)值去觀察一下，一個Key的hashcode如果是3254239，他的高16位不變，與他的低16位做一個異或得到的值為3812。
那我們存放的位置就是table[3812]嗎？，顯然這個長度太大了，我們還是得去限制一下這個長度，保證這個數(shù)組下標(biāo)的位置在我們定義的數(shù)組大小之內(nèi)。
那么假如我們的數(shù)組大小為16的話，我們可以將3812對16取余
3812 % 16 < 16，我們發(fā)現(xiàn)，這樣去做的話取到的數(shù)值一定會小于我們定義的數(shù)組大小。那么，在hashmap源碼中是這樣實現(xiàn)的嗎？
n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null)
奇怪的是，我們設(shè)想的方式是取模，為什么源碼中取了(n-1)和hash值的與運算呢？讓我們?nèi)タ匆幌滤麄兊闹凳欠袷堑葍r的。
按照源碼中來說，這個數(shù)組下標(biāo)就是 (16 - 1) & 3812 = 15 & 3812，
那么我們就要去證明?
15 & 3812? ===? 3812 % 16
這個是否成立
15用二進制表示是 001111， 那么不管3812的二進制數(shù)是什么，他們的與運算的值也永遠(yuǎn)不會超過15，就是>=15，我們發(fā)現(xiàn)這和我們的取模運算的結(jié)果是一樣的，這是hashmap源碼里一個比較精秒的地方。
那為什么要用這種方式呢？
因為與運算要比我們的取模運算速度快，效率高
我們再回過頭看一串代碼
/** * The default initial capacity - MUST be a power of two. */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
在這里，為什么要一定強調(diào) 數(shù)組的大小必須是2的n次冪呢，讓我們舉個例子來看一下，如果數(shù)組的自定義初始化大小為15
那么 15 -1 = 14 ，14用二進制表示就是001110，那么與hash值做了與運算之后，得到的這個數(shù)值可能就會大于這個數(shù)組大小的規(guī)定值，還有就是不論hash值的這位數(shù)字是0還是1，得到的這個位數(shù)總會是0，那么結(jié)點的落點位置就很可能會重疊在一起，所以，這個數(shù)組的大小必須是2的n次冪。
那么，2的n次冪減1的二進制數(shù)的后幾位一定是1嗎？我們驗證一下
16? 15? 01111
32? 31? 011111
64? ?63? 0111111，沒有問題
推出： 數(shù)組大小不夠用了，我希望擴大數(shù)組的大小，也要 * 2
做了這么多的鋪墊，接下來讓我們完整的去看一下HashMap中的put方法
1 /**
2 * Implements Map.put and related methods
3 *
4 * @param hash hash for key
5 * @param key the key
6 * @param value the value to put
7 * @param onlyIfAbsent if true, don"t change existing value
8 * @param evict if false, the table is in creation mode.
9 * @return previous value, or null if none
10 */
11 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
12 boolean evict) {
13 //定義幾個局部變量供接下來使用
14 Node[] tab; Node p; int n, i;
15 //這里將全局變量table，也就是我們剛才說的數(shù)組形式，賦給了局部變量tab
16 if ((tab = table) == null || (n = tab.length) == 0)
17 //如果數(shù)組的大小為空，就用resize方法來對數(shù)組進行初始化
18 n = (tab = resize()).length;
19 //計算節(jié)點的落點位置
20 if ((p = tab[i = (n - 1) & hash]) == null)
21 //如果為空則可以放置
22 tab[i] = newNode(hash, key, value, null);
23 else {
24 //如果數(shù)組該位置有節(jié)點，則往下壓，為鏈表結(jié)構(gòu)
25 Node e; K k;
26 //如果key的值是一樣的，則保留老值
27 if (p.hash == hash &&
28 ((k = p.key) == key || (key != null && key.equals(k))))
29 e = p;
30 else if (p instanceof TreeNode)
31 //如果發(fā)現(xiàn)下面的結(jié)構(gòu)已經(jīng)是一個二叉樹的話，就用紅黑樹的方式去儲存
32 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
33 else {
34 //遍歷鏈表
35 for (int binCount = 0; ; ++binCount) {
36 if ((e = p.next) == null) {
37 //如果下一個節(jié)點為空，則可以放置
38 p.next = newNode(hash, key, value, null);
39 //如果放置之后正好為8的話，要進行鏈表向紅黑樹轉(zhuǎn)化的過程
40 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
41 treeifyBin(tab, hash);
42 break;
43 }
44 if (e.hash == hash &&
45 ((k = e.key) == key || (key != null && key.equals(k))))
46 break;
47 p = e;
48 }
49 }
50 if (e != null) { // existing mapping for key
51 //key值重復(fù)的話，保留老的值
52 V oldValue = e.value;
53 if (!onlyIfAbsent || oldValue == null)
54 e.value = value;
55 afterNodeAccess(e);
56 return oldValue;
57 }
58 }
59 ++modCount;
60 //判斷數(shù)組的大小是否超過了一個閾值，0.75倍的值
61 if (++size > threshold)
62 //超過大小后重新初始化
63 resize();
64 afterNodeInsertion(evict);
65 return null;
66 }
我們發(fā)現(xiàn)這個resize()方法調(diào)用了兩次，他的作用是：
1.數(shù)組的初始化
2.數(shù)組的擴容
源碼分析：resize()
/** * Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table */
final Node[] resize() { //定義數(shù)組
Node[] oldTab = table; //如果數(shù)組存在，oldCap代表數(shù)組的長度
int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { //如果數(shù)組的大小大于0
if (oldCap >= MAXIMUM_CAPACITY) { //如果數(shù)組的大小大于最大值，不需要擴容
threshold = Integer.MAX_VALUE; return oldTab;
} //進行擴容，位運算，相當(dāng)于乘以2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //相應(yīng)的臨界值（閾值）也要乘2
newThr = oldThr << 1; // double threshold
} else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr; else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
} if (newThr == 0) { float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap]; //擴容之后要把原來的部分?jǐn)?shù)據(jù)移到擴容的部分
table = newTab; if (oldTab != null) { //遍歷之前的節(jié)點
for (int j = 0; j < oldCap; ++j) {
Node e; if ((e = oldTab[j]) != null) { //如果該節(jié)點不為空，則將他置為空
oldTab[j] = null; //判斷下面的節(jié)點是否為空
if (e.next == null) //計算新的落點
newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) //如果下面是紅黑樹
((TreeNode)e).split(this, newTab, j, oldCap); else { // preserve order //如果是鏈表
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next; //判斷鏈表的下一個是否為空
do {
next = e.next; if ((e.hash & oldCap) == 0) { //省去了e.hash和oldcap-1 的與操作，如果為0，則hash的第5位是0，則不需要去移動
if (loTail == null)
loHead = e; else loTail.next = e;
loTail = e;
} else { //如果需要移動的話
if (hiTail == null)
hiHead = e; else hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null); if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
} if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead; //鏈表的移動就是自己所處的位
置加上原來老的容量
}
}
}
}
} return newTab;
}
接著，我們?nèi)タ戳丝磄et方法的源碼，發(fā)現(xiàn)和put方法大同小異，也是通過key去找到對應(yīng)的節(jié)點，然后根據(jù)數(shù)組或者紅黑樹這些結(jié)構(gòu)去判斷，然后獲取節(jié)點的key和value。
分享阿里的一個hashmap的面試題：
通過hashmap的初步了解，到hashmap數(shù)據(jù)結(jié)構(gòu)的分析，到源碼的透徹分析，相信你們對hashmap已經(jīng)有了充分的了解.
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/77439.html
摘要：所以，剛開始我并沒有直接就投遞阿里，畢竟心里還是有一點點小害怕的。操作系統(tǒng)的內(nèi)存管理機制進程和線程的區(qū)別說下你對線程安全的理解有什么作用，和有什么區(qū)別實現(xiàn)原理用過么什么場景下用的底層原理。 作者：ppxyn。本文來自讀者投稿。該文已加入筆主的開源項目——JavaGuide（一份涵蓋大部分Java程序員所需要掌握的核心知識的文檔類項目),地址:https://github.com/Sna...
摘要：用戶態(tài)不能干擾內(nèi)核態(tài)所以指令就有兩種特權(quán)指令和非特權(quán)指令不同的狀態(tài)對應(yīng)不同的指令。非特權(quán)指令所有程序均可直接使用。用戶態(tài)常態(tài)目態(tài)執(zhí)行非特權(quán)指令。 這是我今年從三月份開始，主要的大廠面試經(jīng)過，有些企業(yè)面試的還沒來得及整理，可能有些沒有帶答案就發(fā)出來了，還請各位先思考如果是你怎么回答面試官？這篇文章會持續(xù)更新，請各位持續(xù)關(guān)注，希望對你有所幫助！ 面試清單 平安產(chǎn)險 飛豬 上汽大通 浩鯨科...
摘要：把內(nèi)存分成兩種，一種叫做棧內(nèi)存，一種叫做堆內(nèi)存在函數(shù)中定義的一些基本類型的變量和對象的引用變量都是在函數(shù)的棧內(nèi)存中分配。堆內(nèi)存用于存放由創(chuàng)建的對象和數(shù)組。 一次慘痛的阿里技術(shù)面 就在昨天，有幸接到了阿里的面試通知，本來我以為自己的簡歷應(yīng)該不會的到面試的機會了，然而機會卻這么來了，我卻沒有做好準(zhǔn)備，被面試官大大一通血虐。因此，我想寫點東西紀(jì)念一下這次的經(jīng)歷，也當(dāng)一次教訓(xùn)了。其實面試官大大...
摘要：記得，那是一個周末，棧長去某知名互聯(lián)網(wǎng)公司面試，好像不到五分鐘，我就被面試官親切地趕出來了，當(dāng)時我那個尷尬，內(nèi)心深受打擊。。。 你們可能會想，棧長這么菜的嗎？5分鐘都堅持不了？ 本文說起來會有點尷尬，畢竟這是棧長我曾經(jīng)經(jīng)歷過的故事。。。 那時候的棧長還真菜，每天寫著 if/ for 及一些簡單的業(yè)務(wù)邏輯代碼，雖工作有些日子了，但技術(shù)水平還停留在剛畢業(yè)的起步階段。。。 記得，那是一個周末...
摘要：作者重慶森林鏈接來源牛客網(wǎng)整個三月份通過牛客網(wǎng)和網(wǎng)友分享的經(jīng)驗學(xué)到了很多東西，現(xiàn)在反饋一下我的面試經(jīng)歷，希望對同學(xué)們有幫助。個人情況大三本方向渣碩，經(jīng)過實驗室學(xué)長內(nèi)推，于三月底完成面試。校招是實力和運氣的結(jié)合，缺一不可。 歡迎關(guān)注我的微信公眾號：Java面試通關(guān)手冊（堅持原創(chuàng)，分享美文，分享各種Java學(xué)習(xí)資源，面試題，以及企業(yè)級Java實戰(zhàn)項目回復(fù)關(guān)鍵字免費領(lǐng)取）：showImg(h...
閱讀 3274·2023-04-25 18:03
閱讀 1143·2021-11-15 11:38
閱讀 5522·2021-10-25 09:45
閱讀 840·2021-09-24 09:48
閱讀 2272·2021-09-22 15:34
閱讀 1734·2019-08-30 15:44
閱讀 2675·2019-08-30 13:12
閱讀 604·2019-08-29 16:05
