上一篇 懂LruCache嘴纺？你必須先懂LinkedHashMap，順帶給LruCache提個建議中我們分析了LinkedHashMap原理浓冒。
其實LinkedHashMap繼承于HashMap栽渴，如果想理解的徹底必須懂HashMap的底層原理。
本文主要針對HashMap的以下幾個問題展開分析稳懒，由淺入深闲擦，由使用到原理，上下關(guān)聯(lián)，融會貫通墅冷。
- 什么是HashMap纯路？
- HashMap使用方式？
- HashMap的幾個重要方法的源碼是怎么實現(xiàn)的寞忿？
- HashMap 1.7 ~ 1.8 有什么不同驰唬？
1. 到底什么是HashMap？
- HashMap是一個繼承于AbstractMap罐脊，實現(xiàn)Map和Serializable接口的 線程不安全 的 亂序 散列表定嗓，內(nèi)部根據(jù)key的 hashCode 存儲key - value鍵值對。
2. HashMap使用方式萍桌？
- HashMap的使用非常簡單，如下：
public class HashMapActivity extends AppCompatActivity {
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_hash_map);
HashMap<String, String> hashMap = new HashMap();
hashMap.put("k", "v");
hashMap.put("k2", "v2");
hashMap.put("k3", "v3");
for (Map.Entry<String, String> entries : hashMap.entrySet()) {
Log.d("TAG", "key:" + entries.getKey() + " value:" + entries.getValue());
}
}
}
Log
2019-12-12 18:35:23.378 11510-11510/com.test D/TAG: key:k2 value:v2
2019-12-12 18:35:23.378 11510-11510/com.test D/TAG: key:k3 value:v3
2019-12-12 18:35:23.378 11510-11510/com.test D/TAG: key:k value:v
- 通過以上的日志輸出可以看出HashMap數(shù)據(jù)存儲的無序性凌简。
3. HashMap的幾個重要方法怎么實現(xiàn)的上炎？
-
我們根據(jù)HashMap的使用的順序逐一分析每個方法具體在干什么事。
- 3.1. HashMap使用前都需要借助構(gòu)造方法進行實例化雏搂，那么HashMap的構(gòu)造方法具體做了什么藕施？
/**
* 創(chuàng)建一個默認的初始容量，負載因子為0.75的HashMap對象
*/
public HashMap() {
//默認為0.75凸郑，該變量主要用于擴容觸發(fā)裳食，當(dāng)HashMap存儲超過設(shè)定容容量75%時觸發(fā)擴容。
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
*創(chuàng)建一個初始容量為initialCapacity芙沥，負載因子為默認0.75的HashMap對象
* @param initialCapacity 初始化容量诲祸，
* @throws IllegalArgumentException 如果傳入的初始化容量是負數(shù)則報這個異常
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 創(chuàng)建一個初始容量為initialCapacity，負載因子為loadFactor 的HashMap對象而昨。
*
* @param initialCapacity 初始容量
* @param loadFactor 負載因子
* @throws IllegalArgumentException 如果初始容量或loadFactor有一個為負數(shù)則拋該異常救氯。
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
//如果初始容量 > 2^30則設(shè)定initialCapacity = 2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//如果loadFactor是負數(shù)或者非數(shù)字值則拋異常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
//這個邏輯是一個將initialCapacity轉(zhuǎn)換為2的n次方的一個過程，具體細節(jié)我們后續(xù)詳細分析
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 構(gòu)造一個和指定Map有相同mappings的HashMap歌憨，初始容量能充足的容下指定的Map,負載因子為0.75
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
- 以上構(gòu)造方法已經(jīng)逐行寫了注釋着憨，針對 tableSizeFor(int cap) 我們展開分析下。
/**
* 直接翻譯英文注釋的意是
* 返回給定目標(biāo)容量的兩個大小的冪
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
- 在看這個方法之前首先你得懂 移位運算 和 或運算务嫡，我先簡單普及下這倆運算
- 首先計算機只認識二進制數(shù)字甲抖，它認為所有的數(shù)據(jù)都是0101010組成的。
- 比如十進制 24 轉(zhuǎn)為2進制為11000
- 移位運算則將2進制數(shù)據(jù)移動位置并補0心铃，比如11000>>> 1后為01100准谚，01100 >>> 2后為00010
- 或運算是有一個1則為1，全是0則為0.
- ok,普及完了于个，我們研究下上邊的代碼氛魁。
- 非常簡單首先進行了cap-1，該操作是為了防止當(dāng)前入?yún)⒁咽?的冪了证鸥，結(jié)果最后返回的卻是入?yún)⒌?倍掺逼。
- 后續(xù)都是或運算和移位預(yù)算碍岔。按照我上述的邏輯會發(fā)現(xiàn)到最后會將入?yún)⒌淖罡呶缓缶鶗兂?畜侦。
- 比如入?yún)⑹?5祟牲，25-1 =24起便， 二進制為11000理澎，最后會變成11111琳骡，最后return 在將11111+1澳盐，最后返回32祈纯。
- 其實上述方法只是返回了離入?yún)⒌淖罱?的n次冪，比如入?yún)⑹?則返回4叼耙，入?yún)⑹?則返回8腕窥。
我們寫個demo驗證下
public class HashMapActivity extends AppCompatActivity {
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_hash_map);
Log.d("TAG", "tableSizeFor->:" + tableSizeFor(0));
Log.d("TAG", "tableSizeFor->:" + tableSizeFor(1));
Log.d("TAG", "tableSizeFor->:" + tableSizeFor(2));
Log.d("TAG", "tableSizeFor->:" + tableSizeFor(3));
Log.d("TAG", "tableSizeFor->:" + tableSizeFor(4));
Log.d("TAG", "tableSizeFor->:" + tableSizeFor(5));
}
final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= 1 << 30) ? 1 << 30 : n + 1;
}
}
Log
2019-12-13 18:28:22.308 5512-5512/com.test D/TAG: tableSizeFor->:1
2019-12-13 18:28:22.308 5512-5512/com.test D/TAG: tableSizeFor->:1
2019-12-13 18:28:22.308 5512-5512/com.test D/TAG: tableSizeFor->:2
2019-12-13 18:28:22.308 5512-5512/com.test D/TAG: tableSizeFor->:4
2019-12-13 18:28:22.308 5512-5512/com.test D/TAG: tableSizeFor->:4
2019-12-13 18:28:22.308 5512-5512/com.test D/TAG: tableSizeFor->:8
-
HashMap構(gòu)造方法小結(jié)，我們梳理下new HashMap()后干了啥事
- a. new HashMap()進行了局部變量賦默認值 this.loadFactor = DEFAULT_LOAD_FACTOR;
- b. new HashMap(1)調(diào)用了this.HashMap(1, DEFAULT_LOAD_FACTOR)
- c. new HashMap(1, 0.8)進行了初始容量大小判斷筛婉，負載因子合規(guī)判斷簇爆，以及調(diào)用了tableSizeFor(initialCapacity)進行了初始容量轉(zhuǎn)2^n轉(zhuǎn)化。
- 3.2. HashMap添加數(shù)據(jù)通過put方法爽撒，我們看下put方法
/**
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return 如果當(dāng)前key下之前沒有數(shù)據(jù)則返回null入蛆，否則返回之前的老數(shù)據(jù)。
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 存放數(shù)據(jù)
* @param hash 通過key計算的hashCode
* @param key 鍵
* @param value 值
* @param onlyIfAbsent 如果是true并且該key下原來有值硕勿，則不替換原來的值
* @param evict 如果是false則代表table處于創(chuàng)建模式哨毁。
* @return 如果之前有值則返回，如果之前沒值則返回null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果tab為null或者長度為0則通過resize()方法創(chuàng)建一個 Node<K,V>[]賦值給tab源武。
//resize()方法后續(xù)單獨分析
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果當(dāng)前key的位置沒有數(shù)據(jù)扼褪，則直接存入當(dāng)前數(shù)據(jù)。
if ((p = tab[i = (n - 1) & hash]) == null)
//通過newNode()方法創(chuàng)建并存入數(shù)據(jù)软能。
tab[i] = newNode(hash, key, value, null);
else {
//如果當(dāng)前key位置有數(shù)據(jù)迎捺，說明發(fā)生的hash沖突。
Node<K,V> e; K k;
//判斷當(dāng)前的key和之前老數(shù)據(jù)的key是否相同查排，如果相同則把老數(shù)據(jù)賦值給局部變量e凳枝。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判斷該位置的結(jié)構(gòu)是否為紅黑樹，如果是紅黑樹則啟用putTreeVal()方法處理數(shù)據(jù)跋核，如果有key相同的則將老數(shù)據(jù)賦值給局部變量e
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//當(dāng)前位置的結(jié)構(gòu)是鏈表岖瑰，則在循環(huán)在鏈表后添加當(dāng)前數(shù)據(jù)。
for (int binCount = 0; ; ++binCount) {
//循環(huán)到最后一個元素砂代，沒有key重復(fù)則在鏈表尾添加Node<K,V>對象蹋订，此時e為null
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//添加后判斷當(dāng)前鏈表的長度，如果長度>=8則轉(zhuǎn)換為紅黑樹刻伊。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果本次循環(huán)的key和當(dāng)前key相同則退出循環(huán)露戒，并在下邊邏輯中進行替換操作椒功。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//如果本次循環(huán)的key不相同的，且當(dāng)前不是鏈表尾智什，則繼續(xù)下次循環(huán)
p = e;
}
}
//替換值操作
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//LinkedHashMap預(yù)留的方法动漾。
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//判斷擴容
if (++size > threshold)
resize();
//LinkedHashMap預(yù)留的方法。
afterNodeInsertion(evict);
return null;
}
/**
* 向紅黑樹插入/更新數(shù)據(jù)
* 遍歷紅黑樹判斷該節(jié)點的key是否與需插入的key相同荠锭，相同則返回老數(shù)據(jù)旱眯，不同則插入并返回null
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
-
HashMap put()方法小結(jié)，我們梳理下調(diào)用put()后干了啥事证九？主要分為以下7步
- 首先將全局變量table賦值給局部tab删豺，并判斷tab是否為null，如果為null則調(diào)用resize()方法初始化愧怜，創(chuàng)建table呀页。
- 通過 tab[i = (n - 1) & hash]獲取當(dāng)前key的hashCode值位置的數(shù)據(jù)，如果為null拥坛，則說明該位置之前未存放數(shù)據(jù)赔桌，直接通過newNode()創(chuàng)建 Node<K,V>對象存儲。
- 如果key hashCode對應(yīng)的位置不為null則發(fā)生了hash碰撞渴逻，判斷帶插入key和碰撞的key是否相同，相同則直接替換對象音诫。
- 如果碰撞位置的數(shù)據(jù)結(jié)構(gòu)是否為紅黑樹惨奕，如果是則通過putTreeVal()方法處理數(shù)據(jù)，如果發(fā)現(xiàn)有key相同則返回老數(shù)據(jù)并賦值給局部變量e竭钝。
- 如果碰撞位置的數(shù)據(jù)結(jié)果為鏈表梨撞，則循環(huán)判斷是否有和當(dāng)前key相同的，如果有則返回老的數(shù)據(jù)香罐，并賦值給e卧波，如果沒有則循環(huán)到鏈表尾，插入新數(shù)據(jù)庇茫。然后判斷鏈表長度港粱，如果>=8則通過treeifyBin()轉(zhuǎn)換為紅黑樹。
- 判斷局部變量e旦签，如果!=null,則通過入?yún)nlyIfAbsent 判斷是否替換舊的值查坪，然后調(diào)用afterNodeAccess()，該方法默認實現(xiàn)為空宁炫，LinkedHashMap有用到偿曙。
- 判斷數(shù)據(jù)個數(shù)是否大于擴容閥值，如果大于則調(diào)用resize()擴容羔巢。并調(diào)用afterNodeInsertion()望忆，該方法默認實現(xiàn)為空罩阵，LinkedHashMap有用到。
- 3.3. HashMap.put()中用到resize()方法启摄，這個方法主要是干啥的稿壁？
/**
* 該函數(shù)有兩個功能
* 1. 初始化hash表
* 2. 擴容
*
* @return the table
*/
final Node<K,V>[] resize() {
// 保存之前的table；
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;// 保存之前的table的容量鞋仍。
int oldThr = threshold;// 保存之前的閥值（threshold值為oldTab.length*load_factor）
int newCap, newThr = 0;
//如果oldCap > 0說明之前的table不為空
if (oldCap > 0) {
//如果老table的長度已經(jīng)>=最大整型值則將閥值設(shè)置為Integer.MAX_VALUE常摧，后續(xù)也不在進行擴容。
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果容量翻倍后<最大整型值威创，且老容量>=16,則將新閥值也翻倍落午。（<<1可代表翻倍）
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//此時說明oldTab 為 null，oldCap 為0,如果oldThr > 0說明肚豺，HashMap被調(diào)用以下三構(gòu)造方法之一溃斋。
//HashMap(int initialCapacity, float loadFactor)
//HashMap(int initialCapacity)
//HashMap(Map<? extends K, ? extends V> m)
//oldThr 為用戶指定的 HashMap的初始容量（initialCapacity）。
else if (oldThr > 0) // initial capacity was placed in threshold
//table未初始化時oldThr為初始容量initialCapacity
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// oldCap <= 0 且 oldThr =0吸申，說明通過HashMap()創(chuàng)建的HashMap梗劫，所有值均采用默認值，oldTab（Table）表為空截碴，oldCap為0梳侨，oldThr等于0，直接設(shè)置新容量為16日丹，新閥值為16*0.75
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新閾值為0
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"})
//初始化table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果老table!=null則將舊數(shù)據(jù)移值到新table中
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果是單個節(jié)點則直接放到newTab的指定位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果是紅黑樹則進行紅黑樹的rehash操作
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//如果是鏈表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 將同一桶中的元素根據(jù)(e.hash & oldCap)是否為0分成2個不同的鏈表走哺，完成rehash
//索引不變得鏈表
if ((e.hash & oldCap) == 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);
//索引不變的鏈表尾指針!=null則將尾指針.next制空
if (loTail != null) {
loTail.next = null;
//將頭指針放在桶的第一個位置
newTab[j] = loHead;
}
//索引改變的鏈表尾指針!=null,則將尾指針.next制空
if (hiTail != null) {
hiTail.next = null;
//新的位置為原位置+oldCap
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
-
HashMap.resize()方法小結(jié)，我們梳理下調(diào)用resize()后干了啥事哲虾？主要分為以下7步
- 首先resize()有兩個功能丙躏，一個是初始化table，一個是擴容束凑。
- 如果之前table!=null 則判斷 if( table.lenth>=整型最大值 ) { 則將擴容閥值設(shè)置為整型最大值晒旅，并停止擴容。} else if ( table.lenth*2<整型最大值 ) {則擴容為原來2倍汪诉，且閥值擴大為原來2倍}
- 如果通過構(gòu)造函數(shù)創(chuàng)建了HashMap則賦值容量變量和閥值變量废恋，如果沒有設(shè)置容量和負載因子則用默認的賦值。
- 如果table未初始化則通過new Node[newCap]初始化摩瞎，如果進行了擴容則通過new Node[newCap]創(chuàng)建新的容器拴签。
- 如果老table!=null則將老數(shù)據(jù)移值到新容器中，存儲位置為原位置/原位置+原容量旗们，移值過程采用尾插法蚓哩，轉(zhuǎn)移數(shù)據(jù)時統(tǒng)一計算存儲位置。
-
JDK1.7 ~ JDK1.8在resize()的區(qū)別有哪些上渴？
- 擴容時機：1.7是先判斷>閥值擴容后再插入數(shù)據(jù)岸梨，1.8是先插入數(shù)據(jù)然后判斷>閥值擴容喜颁。
- 存儲位置計算：1.7 重新hashCode，擾動處理然后取模運算曹阔，并且每一個數(shù)據(jù)單獨計算半开，1.8 原位置/原位置+舊容量，在轉(zhuǎn)移數(shù)據(jù)時統(tǒng)一計算赃份。
- 擴容后轉(zhuǎn)移數(shù)據(jù)：1.7使用頭插法寂拆，原位置數(shù)據(jù)往后移動，會出現(xiàn)逆序/環(huán)形鏈表死循環(huán)問題抓韩，1.8使用尾插法纠永，防止出現(xiàn)死循環(huán)，逆序谒拴，環(huán)形鏈表等問題尝江。
- 3.4. HashMap.get()方法主要做了什么？這個方法主要是干啥的英上？
//返回key對應(yīng)的值炭序，如果返回為null，可能是值為空也可能是key不存在苍日，如需判斷是哪種情況可用containsKey()判斷
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果第一個值就是則返回鏈表頭
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
//如果是紅黑樹則通過getTreeNode獲取
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//循環(huán)從鏈表里查找
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
至此HashMap1.8的核心方法已經(jīng)分析結(jié)束了惭聂，接下來我們針對1.7和1.8的差異進行針對性對比。
4. HashMap 1.7 / 1.8差異分析
| 差異種類 | HashMap 1.7 | HashMap 1.8 |
|---|---|---|
| 數(shù)據(jù)結(jié)構(gòu) | 數(shù)組+鏈表 | 數(shù)組+鏈表+紅黑樹相恃，當(dāng)鏈表lenth>8則轉(zhuǎn)換為紅黑樹彼妻，在resize()后，所有數(shù)據(jù)位置會重新計算豆茫，如果紅黑樹的元素個數(shù)<=6則轉(zhuǎn)回鏈表 |
| 初始化方式 | inflateTable() | resize() |
| hash計算方式 | hashCode() , 擾動處理（4次位運算+5次異或運算） | hashCode() , 擾動處理（1次位運算+1次異或運算） |
| 數(shù)據(jù)存放方式 | 無沖突時存放數(shù)組，有沖突時存放單鏈表 | 無沖突時存放數(shù)組屋摇，有沖突存放鏈表（長度<8）或紅黑樹(長度>=8) |
| 數(shù)據(jù)插入方式 | 頭插法（將原有數(shù)據(jù)后移一位） | 尾插法（直接插入鏈表或紅黑樹尾部） |
| 擴容后存儲位置的計算方式 | 全部重新計算（hashCode()>擾動處理>&(lenth-1)） | 原位置/原位置+老table.lenth |
| 擴容后轉(zhuǎn)移老數(shù)據(jù)的方式 | 頭插法（原數(shù)據(jù)后移一位揩魂，會出現(xiàn)逆序，環(huán)形鏈表炮温，死循環(huán)等問題） | 尾插法（不會出現(xiàn)逆序火脉，環(huán)形列表，死循環(huán)等問題） |
| 擴容時機 | 先判斷>閥值擴容后再插入 | 先插入數(shù)據(jù)然后判斷>閥值擴容 |
| 舊數(shù)據(jù)轉(zhuǎn)移時的位置計算時機 | 單獨計算 | 轉(zhuǎn)移時統(tǒng)一計算 |
補充一點小知識
-
哈希表如何解決Hash沖突柒啤？
哈希表如何解決Hash沖突.jpg -
為什么HashMap具備下述特點：鍵-值（key-value）都允許為空倦挂、線程不安全、不保證有序担巩、存儲位置隨時間變化方援？
1.jpg -
為什么 HashMap 中 String、Integer 這樣的包裝類適合作為 key 鍵
1.jpg -
HashMap 中的 key若 Object類型涛癌， 則需實現(xiàn)哪些方法犯戏？
1.jpg
