在分析HashMap的源碼之前還是先去看一下hash函數(shù)部分的知識(shí)，之前的數(shù)據(jù)結(jié)構(gòu)課程中也講過(guò)，現(xiàn)在也記不太清楚了。
哈希 哈希函數(shù) 哈希表
什么是散列表?
在數(shù)組中查找數(shù)據(jù)的速度可以達(dá)到O(1),是因?yàn)閿?shù)組中的數(shù)據(jù)有它對(duì)應(yīng)的下標(biāo)。但是查找鏈表中的數(shù)據(jù)時(shí)間復(fù)雜度就相對(duì)很高，因?yàn)椴檎益湵碇械臄?shù)據(jù)需要從頭遍歷。所以就希望有一種通過(guò)關(guān)鍵字不需要比較就可以獲得需要記錄的存儲(chǔ)位置。這就是一種新的存儲(chǔ)技術(shù)——散列技術(shù)。
散列技術(shù)是在存儲(chǔ)位置和它的關(guān)鍵子之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f,使得每個(gè)關(guān)鍵字對(duì)應(yīng)一個(gè)存儲(chǔ)位置f(key)。
對(duì)應(yīng)關(guān)系f稱(chēng)為哈希函數(shù)或者散列函數(shù)。按照這個(gè)思想采用散列技術(shù)將數(shù)據(jù)存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中，這塊連續(xù)存儲(chǔ)空間稱(chēng)為散列表或哈希表。
哈希函數(shù)
在設(shè)計(jì)哈希函數(shù)的時(shí)候需要解決的一個(gè)問(wèn)題就是解決哈希沖突，也就是有兩個(gè)關(guān)鍵字key1和key2，但是卻有f(key1)!=f(key2),這就是沖突。
散列函數(shù)的構(gòu)造方法
哈希函數(shù)中key值的選取有這么幾種方式：
- 直接定址法
- 數(shù)字分析法
- 平方取中法
- 折疊法
- 除留余數(shù)法
此方法常用，f(key) = key mod p(p<=m)。若散列表表長(zhǎng)為m,通常p為小于或等于表長(zhǎng)的最小質(zhì)數(shù)或不包含小于20質(zhì)因子的合數(shù)。
- 隨機(jī)數(shù)法
處理散列沖突的方法
- 開(kāi)放地址法
開(kāi)放地址法就是一旦發(fā)生了沖突，就去尋找下一個(gè)空的散列地址，只要散列表足夠大，空的散列地址總能找的到。
f1(key) = (f(key)+di) mod m (di=1,2,3,4,....,m-1)
- 再散列函數(shù)法
- 鏈地址法
鏈地址法是最常用的處理哈希沖突的方法。比如當(dāng)前有12個(gè)數(shù)，先開(kāi)辟長(zhǎng)度為12的數(shù)組，通過(guò)H(key) = key mod 12來(lái)計(jì)算將當(dāng)前數(shù)據(jù)作為結(jié)點(diǎn)插入到數(shù)組下標(biāo)對(duì)應(yīng)的結(jié)點(diǎn)后面。
HashMap源碼分析
Map有常用的四種集合：
- HashMap:使用哈希表實(shí)現(xiàn)，在keys或values之中都是無(wú)序的
- TreeMap:基于紅黑樹(shù)實(shí)現(xiàn)，按key排序
- LinkedHashMap:有序的
- HashTable:與HashMap實(shí)現(xiàn)方式一樣，但HashTable屬于同步(synchronized)的
在看HashMap源碼之前帶著這幾個(gè)問(wèn)題去看：
- 什么時(shí)候會(huì)使用HashMap?它有什么特點(diǎn)？
- HashMap的工作原理？
- get和put的原理？equals()和hashCode()都有什么作用？
- hash的實(shí)現(xiàn)？為什么要這樣實(shí)現(xiàn)？
- 負(fù)載因子是干嘛的？如果HashMap的大小超過(guò)了負(fù)載因子定義的容量，怎么辦？
HashMap的定義
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable
HashMap繼承于AbstractMap<K,V>抽象類(lèi)，實(shí)現(xiàn)了Map<K,V>,Cloneable,Serialable接口。
HashMap屬性
//實(shí)現(xiàn)了序列化，有自己對(duì)應(yīng)的serialVersionUID
private static final long serialVersionUID = 362498820763181265L;
//默認(rèn)初始容量16(2^4)——必須是2的冪
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認(rèn)負(fù)載因子0.75 當(dāng)HashMap中存儲(chǔ)的元素的數(shù)量大于(容量*負(fù)載因子)也就是默認(rèn)大于16*0.75=12時(shí)，HashMap會(huì)進(jìn)行擴(kuò)容的操作
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//鏈表轉(zhuǎn)為紅黑樹(shù)的閾值
static final int TREEIFY_THRESHOLD = 8;
//紅黑樹(shù)轉(zhuǎn)為鏈表的閾值
static final int UNTREEIFY_THRESHOLD = 6;
//存儲(chǔ)方式有鏈表轉(zhuǎn)為紅黑樹(shù)的容量的最小閾值
static final int MIN_TREEIFY_CAPACITY = 64;
//是HashMap底層存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，是一個(gè)Node數(shù)組。Node類(lèi)為元素維護(hù)了一個(gè)單向鏈表。
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
//擴(kuò)容閾值，用于判斷是否需要調(diào)整HashMap的容量(threshold = 容量*加載因子)
int threshold;
//HashMap的加載因子
final float loadFactor;
這里有個(gè)問(wèn)題，到底什么是加載因子呢？還是先繼續(xù)往下看源碼
Map.Entry
這個(gè)類(lèi)應(yīng)該都比較熟悉了，在對(duì)Map進(jìn)行遍歷的時(shí)候都會(huì)用到這個(gè)，不如去看看Map的源碼吧。。。
把Map中的結(jié)構(gòu)抽出來(lái)看：
//計(jì)算整個(gè)map中的數(shù)據(jù)的長(zhǎng)度
int size();
//判斷map是否為空
boolean isEmpty();
//判斷map中是否含有某個(gè)key
boolean containsKey(Object key);
//判斷map中是否含有某個(gè)值
boolean containsValue(Object value);
//用putAll方法把一個(gè)Map放入一個(gè)新的map中
void putAll(Map<? extends K, ? extends V> m);
//移除map中的所有元素
void clear();
//Entry接口
interface Entry<K, V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
//返回當(dāng)前Entry對(duì)應(yīng)的哈希碼值
int hashCode();
````
}
Node<K,V>
HashMap中有這樣一個(gè)靜態(tài)Node類(lèi),實(shí)現(xiàn)了Map.Entry這個(gè)接口。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> 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;
}
}
從注釋里看的話，Node<K,V>是一個(gè)基本結(jié)點(diǎn)，用于大多數(shù)鍵值對(duì)(entries)。LinkedHashMap的Entry繼承于HashMap.Node<K,V>；HashMap中的TreeNode繼承于LinkedHashMap.Entry<K,V>。
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {}
不知道為什么TreeNode要繼承于LinkedHashMap.Entry，TreeNode是紅黑樹(shù)中的結(jié)點(diǎn)結(jié)構(gòu)，還是先繼續(xù)往下吧。。。
HashMap的構(gòu)造函數(shù)
//無(wú)參構(gòu)造函數(shù)
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);
//是否大于2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +loadFactor);
//負(fù)載因子的初始值都為0.75
this.loadFactor = loadFactor;
//擴(kuò)容閾值 調(diào)用tableSizeFor方法
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
tabelSizeFor
在計(jì)算threshold出現(xiàn)了一個(gè)tableSizeFor方法，這個(gè)方法到底是干嘛的呢？點(diǎn)進(jìn)去一看原來(lái)又是高效的位運(yùn)算。源碼中基本上都是位運(yùn)算，這么做一定有它的原因。我試了一下當(dāng)cap=15的時(shí)候，n的結(jié)果還為15，返回16；當(dāng)cap=20的時(shí)候，n的結(jié)果為31，返回32。還是不知道為什么要這樣做，去查了下資料。
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;
}
作用：
tableSizeFor方法保證函數(shù)返回值是大于等于給定參數(shù)initialCapacity最小的2的次方冪。
也就對(duì)應(yīng)了之前定義的常量DEFAULT_INITIAL_CAPACITY的值為16，注釋中說(shuō)容量必須是2的次冪。根據(jù)它的作用來(lái)說(shuō)如果我輸入的值在[33,64]之間，那么最后n的結(jié)果都為63，且threshold為64。我去試了下，真的是這樣。位運(yùn)算真的是一個(gè)很神奇的東西，如果我想運(yùn)算的值都可以自己用位運(yùn)算和邏輯運(yùn)算寫(xiě)出來(lái)的話，在計(jì)算方面效率確實(shí)是可以提高不少。
為什么cap要保持為2的冪次方？
cap要保持為2的冪次方主要原因是HashMap中數(shù)據(jù)存儲(chǔ)有關(guān)。在JDK1.8中，HashMap中key的Hash值由Hash(key)方法計(jì)算得來(lái)。
HashMap中存儲(chǔ)數(shù)據(jù)table的index是由key的Hash值決定的。在HashMap存儲(chǔ)數(shù)據(jù)的時(shí)候，我們希望數(shù)據(jù)能夠均勻分布，以避免哈希沖突，所以一般就會(huì)采用取余(%)的操作來(lái)實(shí)現(xiàn)。
有一個(gè)重要的知識(shí)：取余操作中如果除數(shù)是2的冪次方則等價(jià)于和其除數(shù)減一的與操作
index = e.hash & (newCap - 1)
等價(jià)于：
index = e.hash % newCap
putMapEntries
在將Map作為參數(shù)傳入HashMap的構(gòu)造函數(shù)中的時(shí)候調(diào)用了這個(gè)方法
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
//Node<K,V>[] table為null
if (table == null) { // pre-size
//計(jì)算:傳進(jìn)來(lái)的map的容量+1.0f
float ft = ((float)s / loadFactor) + 1.0F;
//和最大容量作比較
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//將當(dāng)前map的容量和擴(kuò)容閾值作比較，如果超過(guò)了閾值就需要執(zhí)行擴(kuò)容方法
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();//計(jì)算threshold
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
resize
resize這個(gè)方法重新計(jì)算了Node<K,V>[] table的容量和擴(kuò)容閾值
final Node<K,V>[] resize() {
//oldTab是當(dāng)前的table數(shù)組
Node<K,V>[] oldTab = table;
//得到oldTab的長(zhǎng)度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//oldThr是當(dāng)前數(shù)組的擴(kuò)容閾值
int oldThr = threshold;
int newCap, newThr = 0;//初始化新的數(shù)組容量和擴(kuò)容閾值
//舊的數(shù)組容量大于0
if (oldCap > 0) {
//考慮容量值不能超過(guò)2^30
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//擴(kuò)容后的新數(shù)組的容量為舊數(shù)組容量的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 擴(kuò)容閾值也為之前的兩倍
}
//舊數(shù)組的容量<=0 & 舊數(shù)組的擴(kuò)容閾值大于0
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;//新數(shù)組容量為舊數(shù)組的擴(kuò)容閾值
else {
//newCap=16,newThr=12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {//計(jì)算新的擴(kuò)容閾值=容量*負(fù)載因子
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//這里主要就是將舊數(shù)組中的結(jié)點(diǎn)放到新數(shù)組中，這里面需要考慮的問(wèn)題是因?yàn)閿U(kuò)容指針數(shù)組的長(zhǎng)度變?yōu)樵瓉?lái)的2倍，結(jié)點(diǎn)對(duì)應(yīng)的位置可能會(huì)發(fā)生改變，也就是我們需要處理可能會(huì)發(fā)生的哈希沖突的問(wèn)題。
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//數(shù)組中只有一個(gè)結(jié)點(diǎn)
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//判斷出當(dāng)前節(jié)點(diǎn)是TreeNode類(lèi)型，也就是紅黑樹(shù)類(lèi)型的結(jié)點(diǎn)需要做自己的變化
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//這里就是做了對(duì)可能產(chǎn)生的哈希沖突的處理，主要計(jì)算過(guò)程在下面解釋-->解釋一
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;
//原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//原索引+oldCap
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;
}
解釋一
可以看到在這部分多出來(lái)了兩個(gè)新的鏈表lo和hi。lo存放那些和之前hash表中位置沒(méi)有改變的結(jié)點(diǎn)，hi就用來(lái)存放產(chǎn)生了hash沖突的結(jié)點(diǎn)。
主要的判斷方法就和下面的公式有關(guān)：
- (e.hash & oldCap) == 0
- e.hash & (newCap - 1)
- e.hash & (oldCap - 1)
公式2和3都是求當(dāng)前節(jié)點(diǎn)要在hash表中的位置，前面提到過(guò)。公式1的效果就是為了判斷擴(kuò)容后結(jié)點(diǎn)存在的位置是否發(fā)生了改變，結(jié)果為true,就說(shuō)明沒(méi)有發(fā)生改變。也就是公式2和公式3計(jì)算出來(lái)的效果是一樣的。舉個(gè)栗子:
舊的數(shù)組的容量為16，則新的數(shù)組的容量為32。計(jì)算值的話就是：
e.hash & 0x0F(0000 1111 為15)——舊
e.hash & 0x1F(0001 1111 為31)——新
e.hash & 0x10(0001 0000)——e.hash & oldCap
新數(shù)組和舊數(shù)組的長(zhǎng)度之間會(huì)向高位移一個(gè)1,也就是說(shuō)看結(jié)點(diǎn)的hash值在對(duì)應(yīng)的高位是1還是0，是0就插入lo隊(duì)列是0就插入hi隊(duì)列。
看到了一篇博客上寫(xiě)的，分析的很清楚，圖文并茂。。。感覺(jué)自己說(shuō)的不是很清楚。。。java集合——HashMap
putVal
在putMapEntries方法中擴(kuò)容完會(huì)遍歷Map集合，獲得key和value后調(diào)用putVal方法，將key和value作為參數(shù)傳入。下面來(lái)看看這個(gè)方法是干嘛的。
見(jiàn)下面
put函數(shù)的實(shí)現(xiàn)
平常我們會(huì)通過(guò)調(diào)用map.put方法來(lái)向集合中放入一個(gè)鍵值對(duì)。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果當(dāng)前tab數(shù)組為null或者長(zhǎng)度為0，就進(jìn)行初始化，調(diào)用resize方法
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果當(dāng)前Node對(duì)應(yīng)的位置還沒(méi)有其它結(jié)點(diǎn)插入就創(chuàng)建新的結(jié)點(diǎn)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//hash值相同且key是同一個(gè)對(duì)象就覆蓋之前的值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//當(dāng)前節(jié)點(diǎn)是紅黑樹(shù)結(jié)點(diǎn)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//遍歷尋找當(dāng)前節(jié)點(diǎn)應(yīng)該鏈接的位置
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果key值相同就替換
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//將當(dāng)前修改或者插入的值寫(xiě)入
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//增加修改次數(shù)
//超過(guò)了擴(kuò)容閾值，調(diào)用resize方法
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
putVal函數(shù)的大致思路為：
- 對(duì)key的hashCode()做hash，然后再計(jì)算index;
- 如果沒(méi)有碰撞直接放到bucket里；
- 如果碰撞了，以鏈表的形式存在buckets后；
- 如果碰撞導(dǎo)致鏈表過(guò)長(zhǎng)(>=TREEIFY_THRESHOLD),就把鏈表轉(zhuǎn)成紅黑樹(shù)；
- 如果結(jié)點(diǎn)已經(jīng)存在就替換old value(保證key的唯一性)
- 如果bucket滿了，就調(diào)用resize。
get函數(shù)的實(shí)現(xiàn)
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
實(shí)際調(diào)用的是getNode方法，看過(guò)putVal方法后看get方法就容易許多了
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//檢查tab數(shù)組不為空且長(zhǎng)度大于0且當(dāng)前單元中有Node結(jié)點(diǎn)
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果是第一個(gè)結(jié)點(diǎn)就返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//當(dāng)前節(jié)點(diǎn)是紅黑樹(shù)結(jié)點(diǎn)
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//在當(dāng)前鏈表中循環(huán)遍歷查找要找的結(jié)點(diǎn)
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
getVal的具體流程如下：
- bucket里的第一個(gè)節(jié)點(diǎn)，直接命中；
- 若第一個(gè)未命中，就去遍歷查找。一種是在樹(shù)的結(jié)構(gòu)中查找，一種就是在單鏈表中查找。
到這里HashMap中的基本重要方法就分析完了，主要有兩個(gè)屬性需要特別關(guān)注:
- threshold 擴(kuò)容閾值
- loadFactor 負(fù)載因子
幾個(gè)方法：
- tableSizeFor():計(jì)算擴(kuò)容閾值
- resize():擴(kuò)容Node<K,V> tab數(shù)組
- putVal():往map中添加值
- getVal():獲取map中的值
- hash():計(jì)算hashCode()的hash值
這里再對(duì)一些地方進(jìn)行解釋?zhuān)?/p>
在java中，散列表用鏈表數(shù)組實(shí)現(xiàn)。每個(gè)鏈表被稱(chēng)為桶(bucket)，要想查找表中對(duì)象的位置，就要先計(jì)算它的散列碼，然后與桶的總數(shù)取余，所得的結(jié)果就是保存這個(gè)元素的桶的索引
兩個(gè)重要參數(shù)
容量(Capacity)和負(fù)載因子(LoadFactor)。
- Capacity:就是bucket的大小
- LoadFactor:就是bucket填滿程度的最大比列
如果對(duì)迭代性能要求很高的話，不要把Capacity設(shè)置過(guò)大，也不要把LoadFactor設(shè)置過(guò)小。當(dāng)bucket中的entries的數(shù)目大于capacity*loadfactor時(shí)就需要調(diào)整bucket大小為當(dāng)前的2倍。
hash函數(shù)的實(shí)現(xiàn)
HashMap中的hash()
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這里對(duì)key為null還做了處理，key為null,hash后等于0，說(shuō)明HashMap是支持key為null的。
可以看到這里是對(duì)key的hashCode值的前16位和后16位進(jìn)行異或運(yùn)算，有一幅圖：
image
這里進(jìn)行取前16位和后16位分別進(jìn)行異或是為了減少在數(shù)組中插入值時(shí)產(chǎn)生頻繁的碰撞。可以這樣去想如果當(dāng)前的數(shù)組長(zhǎng)度比較小，比如說(shuō)是10，那么在進(jìn)行(n-1)&hash時(shí)，使用的其實(shí)只是hashcode()值的后一位，那么這樣就會(huì)很容易產(chǎn)生碰撞。因此通過(guò)高16位和低16位異或的操作，既減少了系統(tǒng)的開(kāi)銷(xiāo)，也不會(huì)造成因?yàn)楦呶粵](méi)有參與下標(biāo)的計(jì)算(table長(zhǎng)度比較小時(shí))，引起的碰撞。
如果還是產(chǎn)生了碰撞，HashMap設(shè)計(jì)者使用了紅黑樹(shù)O(logn)去做。
問(wèn)題總結(jié)
HashMap應(yīng)該是面試中的高頻考點(diǎn)了，這里總結(jié)一下應(yīng)該怎么回答問(wèn)題。
- 講一講HashMap?
HashMap底層的數(shù)據(jù)結(jié)構(gòu)是用數(shù)組+鏈表+紅黑樹(shù)實(shí)現(xiàn)的，當(dāng)鏈表中節(jié)點(diǎn)的個(gè)數(shù)大于8的時(shí)候鏈表會(huì)進(jìn)行樹(shù)化，當(dāng)節(jié)點(diǎn)的個(gè)數(shù)小于等于6的時(shí)候會(huì)恢復(fù)成鏈表的結(jié)構(gòu)。HashMap默認(rèn)初始容量為16，容量的大小一般為2的次方冪，HashMap的大小會(huì)根據(jù)要存入數(shù)據(jù)的多少進(jìn)行擴(kuò)容，有三個(gè)重要的值，Capacity容量就是HashMap當(dāng)前所能放入的所有鍵值對(duì)，loadFactor擴(kuò)容因子一般為0.75代表填滿當(dāng)前map容量的最大比例，threshold擴(kuò)容閾值，它的大小為(容量*擴(kuò)容因子),當(dāng)要加入值的個(gè)數(shù)加上之前加入過(guò)的值的總和大于擴(kuò)容閾值需要對(duì)HashMap進(jìn)行擴(kuò)容，會(huì)調(diào)用resize函數(shù)，map的容量會(huì)變?yōu)橹暗?倍，擴(kuò)容閾值也會(huì)變?yōu)橹暗膬杀?。還有常用的加入元素和取出元素的get和put方法，get方法會(huì)先去判斷當(dāng)前key的hashCode的hash值，如果存在且是第一個(gè)節(jié)點(diǎn)就取出，如果不是就去遍歷當(dāng)前的鏈表，如果當(dāng)前要查詢的節(jié)點(diǎn)是紅黑樹(shù)節(jié)點(diǎn)就去在樹(shù)中尋找，否則就去遍歷鏈表。put方法在放入一個(gè)entry的時(shí)候會(huì)先計(jì)算hash值并計(jì)算index值，也就是當(dāng)前要放入的節(jié)點(diǎn)的位置，如果當(dāng)前位置為空就創(chuàng)建結(jié)點(diǎn)插入，如果之前有節(jié)點(diǎn)放入就去遍歷檢查有沒(méi)有重復(fù)的節(jié)點(diǎn)，有就替換現(xiàn)有的節(jié)點(diǎn)，保證key的唯一性。
- 為什么使用HashMap?
HashMap是一個(gè)散列桶(數(shù)組和鏈表)，它存儲(chǔ)的內(nèi)容是鍵值對(duì)(key-value)映射
HashMap采用了數(shù)組和鏈表的數(shù)據(jù)結(jié)構(gòu)，能在查詢和修改方面繼承了數(shù)組的線性查找和鏈表的易于刪除拋棄的節(jié)點(diǎn)
HashMap是非synchronize的，所以HashMap很快
HashMap可以接受null鍵和值，但是HashTable不能。(HashMap在key為null時(shí)在hash方法中做了處理)
- HashMap線程安全么？還知道其他Map類(lèi)的集合么？和HashMap有什么區(qū)別？
不是線程安全的，在對(duì)HashMap的操作中并沒(méi)有上鎖。在多線程訪問(wèn)使用put方法插入元素，發(fā)生哈希碰撞可能會(huì)造成數(shù)據(jù)的丟失。還有resize方法也是不安全的，多線程下都會(huì)創(chuàng)建一個(gè)新的table數(shù)組，但最終只有一個(gè)對(duì)象替換之前的舊的table數(shù)組。
了解到的其他Map類(lèi):
HashTable:也是數(shù)組+鏈表的存儲(chǔ)方式，內(nèi)部共享數(shù)據(jù)的方法添加了synchronized，保證了線程安全。
LinkedHashMap:(HashMap+LinkedList)存入的數(shù)據(jù)是有序的。實(shí)現(xiàn)了Lru緩存。
ConcurrentHashMap:引入了CAS,根據(jù)同步級(jí)別對(duì)map的一部分上鎖。引入了分割，不論變的多么大僅僅需要鎖定map的某個(gè)部分，其他的線程不需要等到迭代完成才能訪問(wèn)map
- HashMap的擴(kuò)容機(jī)制是如何實(shí)現(xiàn)的？
HashMap的擴(kuò)容機(jī)制要提到三個(gè)變量，threshold擴(kuò)容閾值、loadFactor擴(kuò)容因子一般都為0.75、capacity容量，這三個(gè)變量之間的關(guān)系是擴(kuò)容閾值=擴(kuò)容因子*總?cè)萘?，也就是說(shuō)在往當(dāng)前map中添加元素的時(shí)候會(huì)去檢查添加的新值加上之前已經(jīng)有個(gè)元素的個(gè)數(shù)時(shí)候會(huì)超過(guò)當(dāng)前map的擴(kuò)容閾值，如果超過(guò)了就需要擴(kuò)容。如果當(dāng)前容量非常大甚至超過(guò)了最大容量2^30，那么就把當(dāng)前容量設(shè)置為Integer.MAX_VALUE,否則就將當(dāng)前的map容量和擴(kuò)容閾值都設(shè)置為之前的2倍。
- HashMap中的hash方法是怎么實(shí)現(xiàn)的？
hash方法其實(shí)是根據(jù)key的hashCode值，取這個(gè)值的前16位和后16位進(jìn)行異或操作，在通過(guò)(n-1)&hash得到當(dāng)前節(jié)點(diǎn)所要放入的數(shù)組的下標(biāo)。
