阿里電話面試問(wèn)到了關(guān)于HashMap底層的實(shí)現(xiàn)，雖然之前看過(guò)底層源碼，但是還是回答的不夠清晰。所以趕緊去查一下，這里做個(gè)筆記記錄一下， 捋順?biāo)悸贰?/p>
java數(shù)據(jù)結(jié)構(gòu)中有數(shù)組和鏈表這兩種結(jié)構(gòu)
數(shù)組:存儲(chǔ)在內(nèi)存中是連續(xù)的，因?yàn)槭沁B續(xù)內(nèi)存空間，所以很容易通過(guò)下標(biāo)索引查詢到，但是插入和刪除困難。
鏈表:鏈表的元素在內(nèi)存中的存儲(chǔ)位置是不確定的，分散存儲(chǔ)，沒(méi)有索引下標(biāo)，所以查詢尋址難，而插入和刪除容易（只需要移動(dòng)指針）
綜合這兩者的優(yōu)點(diǎn)，摒棄缺點(diǎn)，做成了哈希表。
圖1
圖2
哈希表又稱為數(shù)組鏈表，底層還是數(shù)組但數(shù)組中每一項(xiàng)是一個(gè)鏈表。
下面我們對(duì)HashMap的源碼進(jìn)行分析
一、首先看一下put方法（通過(guò)put方法基本能看出hashmap結(jié)構(gòu)）
public V put(K key, V value) {
//如果table數(shù)組為空數(shù)組{}，進(jìn)行數(shù)組填充（為table分配實(shí)際內(nèi)存空間），入?yún)閠hreshold，此時(shí)threshold為initialCapacity 默認(rèn)是1<<4(16)
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);//創(chuàng)建null的key
int hash = hash(key);//計(jì)算key的hash值
int i = indexFor(hash, table.length);//通過(guò)key的hash值計(jì)算在數(shù)組table中的位置
//下邊循環(huán)判斷該數(shù)組 i 位置的鏈表中是否已經(jīng)存在該key，如果存在則直接將舊值覆蓋
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//判斷該條鏈上是否有hash值相同且key相同的
//若存在相同，則直接覆蓋value，返回舊value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//修改次數(shù)增加1
modCount++;
//在數(shù)組的 i 處增加節(jié)點(diǎn)entry（這里是在鏈表頭部插入，作為鏈表頭）
addEntry(hash, key, value, i);
return null;
}
通過(guò)put代碼，我們可以清晰看出保存過(guò)程
1，通過(guò)判斷table為空的，則初始化數(shù)組
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
//這行是計(jì)算閥值，當(dāng)達(dá)到該閥值，則默認(rèn)擴(kuò)容capacity * loadFactor為16 * 0.75=12
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
通過(guò)roundUpToPowerOf2(toSize)可以計(jì)算出 大于或等于toSize的最接近toSize的2的n次冪，比如toSize=13,則capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
該方法Integer.highestOneBit是用來(lái)獲取最左邊的bit（其他bit位為0）所代表的數(shù)值.
2，第一步判斷key為null，則putForNullKey(value);
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
從代碼可以看出，如果key為null的值，默認(rèn)就存儲(chǔ)到table[0]數(shù)組第一位。然后遍歷table[0]的鏈表的每個(gè)節(jié)點(diǎn)Entry，如果發(fā)現(xiàn)其中存在節(jié)點(diǎn)Entry的key為null，就替換新的value，然后返回舊的value，如果沒(méi)發(fā)現(xiàn)key等于null的節(jié)點(diǎn)Entry，就增加新的節(jié)點(diǎn)
3，計(jì)算key的hash，得到k的hash值
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
該函數(shù)用了很多異或，移動(dòng)運(yùn)算，對(duì)key的hashcode進(jìn)行進(jìn)一步運(yùn)算，來(lái)保證最終獲取的存儲(chǔ)位置盡量分布均勻
4，通過(guò)hash值計(jì)算index（數(shù)組table所處的位置）
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
h & (length-1);就相當(dāng)于h %length。也就是用hash值對(duì)table數(shù)組的長(zhǎng)度取模，這里采用了位運(yùn)算，提高性能
最終就可以拿到存儲(chǔ)的下標(biāo)
5，然后通過(guò)下標(biāo)i，table[i]拿到table 的i位置的鏈表頭節(jié)點(diǎn)。循環(huán)鏈表，如果發(fā)現(xiàn)hash，key都相同的節(jié)點(diǎn)時(shí)，就替換為新的value，然后返回舊的value，只有hash相同時(shí)，循環(huán)內(nèi)并沒(méi)有做任何處理
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;
}
}
6，通過(guò)addEntry方法來(lái)新插入一個(gè)節(jié)點(diǎn)。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);//當(dāng)size超過(guò)臨界閾值threshold，并且即將發(fā)生哈希沖突時(shí)進(jìn)行擴(kuò)容2倍
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
通過(guò)以上代碼能夠得知，當(dāng)size大于閾值的時(shí)候，需要進(jìn)行數(shù)組擴(kuò)容，擴(kuò)容時(shí)，需要新建一個(gè)長(zhǎng)度為之前數(shù)組2倍的新的數(shù)組，然后將當(dāng)前的Entry數(shù)組中的元素全部傳輸過(guò)去，擴(kuò)容后的新數(shù)組長(zhǎng)度為之前的2倍，所以擴(kuò)容相對(duì)來(lái)說(shuō)是個(gè)耗資源的操作。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//initHashSeedAsNeeded方法是判斷是否需要重新計(jì)算hash值
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
