在分析HashMap的源碼之前還是先去看一下hash函數(shù)部分的知識给郊，之前的數(shù)據(jù)結(jié)構(gòu)課程中也講過，現(xiàn)在也記不太清楚了捧灰。
哈希 哈希函數(shù) 哈希表
什么是散列表?
在數(shù)組中查找數(shù)據(jù)的速度可以達(dá)到O(1),是因為數(shù)組中的數(shù)據(jù)有它對應(yīng)的下標(biāo)淆九。但是查找鏈表中的數(shù)據(jù)時間復(fù)雜度就相對很高，因為查找鏈表中的數(shù)據(jù)需要從頭遍歷毛俏。所以就希望有一種通過關(guān)鍵字不需要比較就可以獲得需要記錄的存儲位置炭庙。這就是一種新的存儲技術(shù)——散列技術(shù)。
散列技術(shù)是在存儲位置和它的關(guān)鍵子之間建立一個確定的對應(yīng)關(guān)系f,使得每個關(guān)鍵字對應(yīng)一個存儲位置f(key)拧抖。
對應(yīng)關(guān)系f稱為哈希函數(shù)或者散列函數(shù)煤搜。按照這個思想采用散列技術(shù)將數(shù)據(jù)存儲在一塊連續(xù)的存儲空間中免绿，這塊連續(xù)存儲空間稱為散列表或哈希表唧席。
哈希函數(shù)
在設(shè)計哈希函數(shù)的時候需要解決的一個問題就是解決哈希沖突，也就是有兩個關(guān)鍵字key1和key2嘲驾，但是卻有f(key1)!=f(key2),這就是沖突淌哟。
散列函數(shù)的構(gòu)造方法
哈希函數(shù)中key值的選取有這么幾種方式：
- 直接定址法
- 數(shù)字分析法
- 平方取中法
- 折疊法
- 除留余數(shù)法
此方法常用，f(key) = key mod p(p<=m)辽故。若散列表表長為m,通常p為小于或等于表長的最小質(zhì)數(shù)或不包含小于20質(zhì)因子的合數(shù)徒仓。
- 隨機(jī)數(shù)法
處理散列沖突的方法
- 開放地址法
開放地址法就是一旦發(fā)生了沖突，就去尋找下一個空的散列地址誊垢，只要散列表足夠大掉弛，空的散列地址總能找的到。
f1(key) = (f(key)+di) mod m (di=1,2,3,4,....,m-1)
- 再散列函數(shù)法
- 鏈地址法
鏈地址法是最常用的處理哈希沖突的方法喂走。比如當(dāng)前有12個數(shù)殃饿，先開辟長度為12的數(shù)組，通過H(key) = key mod 12來計算將當(dāng)前數(shù)據(jù)作為結(jié)點(diǎn)插入到數(shù)組下標(biāo)對應(yīng)的結(jié)點(diǎn)后面芋肠。
HashMap源碼分析
Map有常用的四種集合：
- HashMap:使用哈希表實現(xiàn)乎芳，在keys或values之中都是無序的
- TreeMap:基于紅黑樹實現(xiàn)，按key排序
- LinkedHashMap:有序的
- HashTable:與HashMap實現(xiàn)方式一樣，但HashTable屬于同步(synchronized)的
在看HashMap源碼之前帶著這幾個問題去看：
- 什么時候會使用HashMap?它有什么特點(diǎn)奈惑？
- HashMap的工作原理吭净？
- get和put的原理？equals()和hashCode()都有什么作用肴甸？
- hash的實現(xiàn)寂殉？為什么要這樣實現(xiàn)？
- 負(fù)載因子是干嘛的原在？如果HashMap的大小超過了負(fù)載因子定義的容量不撑，怎么辦？
HashMap的定義
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable
HashMap繼承于AbstractMap<K,V>抽象類晤斩，實現(xiàn)了Map<K,V>,Cloneable,Serialable接口焕檬。
HashMap屬性
//實現(xiàn)了序列化，有自己對應(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中存儲的元素的數(shù)量大于(容量*負(fù)載因子)也就是默認(rèn)大于16*0.75=12時澳泵，HashMap會進(jìn)行擴(kuò)容的操作
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//鏈表轉(zhuǎn)為紅黑樹的閾值
static final int TREEIFY_THRESHOLD = 8;
//紅黑樹轉(zhuǎn)為鏈表的閾值
static final int UNTREEIFY_THRESHOLD = 6;
//存儲方式有鏈表轉(zhuǎn)為紅黑樹的容量的最小閾值
static final int MIN_TREEIFY_CAPACITY = 64;
//是HashMap底層存儲的數(shù)據(jù)結(jié)構(gòu)实愚，是一個Node數(shù)組。Node類為元素維護(hù)了一個單向鏈表兔辅。
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;
這里有個問題，到底什么是加載因子呢维苔？還是先繼續(xù)往下看源碼
Map.Entry
這個類應(yīng)該都比較熟悉了碰辅，在對Map進(jìn)行遍歷的時候都會用到這個，不如去看看Map的源碼吧介时。没宾。。
把Map中的結(jié)構(gòu)抽出來看：
//計算整個map中的數(shù)據(jù)的長度
int size();
//判斷map是否為空
boolean isEmpty();
//判斷map中是否含有某個key
boolean containsKey(Object key);
//判斷map中是否含有某個值
boolean containsValue(Object value);
//用putAll方法把一個Map放入一個新的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對應(yīng)的哈希碼值
int hashCode();
````
}
Node<K,V>
HashMap中有這樣一個靜態(tài)Node類,實現(xiàn)了Map.Entry這個接口沸柔。
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>是一個基本結(jié)點(diǎn)，用于大多數(shù)鍵值對(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是紅黑樹中的結(jié)點(diǎn)結(jié)構(gòu)迁酸，還是先繼續(xù)往下吧。俭正。奸鬓。
HashMap的構(gòu)造函數(shù)
//無參構(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
在計算threshold出現(xiàn)了一個tableSizeFor方法，這個方法到底是干嘛的呢段审？點(diǎn)進(jìn)去一看原來又是高效的位運(yùn)算全蝶。源碼中基本上都是位運(yùn)算闹蒜，這么做一定有它的原因。我試了一下當(dāng)cap=15的時候抑淫，n的結(jié)果還為15绷落，返回16；當(dāng)cap=20的時候始苇，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的次方冪。
也就對應(yīng)了之前定義的常量DEFAULT_INITIAL_CAPACITY的值為16荣月，注釋中說容量必須是2的次冪管呵。根據(jù)它的作用來說如果我輸入的值在[33,64]之間，那么最后n的結(jié)果都為63哺窄，且threshold為64捐下。我去試了下，真的是這樣萌业。位運(yùn)算真的是一個很神奇的東西坷襟，如果我想運(yùn)算的值都可以自己用位運(yùn)算和邏輯運(yùn)算寫出來的話，在計算方面效率確實是可以提高不少生年。
為什么cap要保持為2的冪次方婴程？
cap要保持為2的冪次方主要原因是HashMap中數(shù)據(jù)存儲有關(guān)。在JDK1.8中抱婉，HashMap中key的Hash值由Hash(key)方法計算得來档叔。
HashMap中存儲數(shù)據(jù)table的index是由key的Hash值決定的。在HashMap存儲數(shù)據(jù)的時候授段，我們希望數(shù)據(jù)能夠均勻分布蹲蒲，以避免哈希沖突番甩，所以一般就會采用取余(%)的操作來實現(xiàn)侵贵。
有一個重要的知識：取余操作中如果除數(shù)是2的冪次方則等價于和其除數(shù)減一的與操作
index = e.hash & (newCap - 1)
等價于：
index = e.hash % newCap
putMapEntries
在將Map作為參數(shù)傳入HashMap的構(gòu)造函數(shù)中的時候調(diào)用了這個方法
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ìn)來的map的容量+1.0f
float ft = ((float)s / loadFactor) + 1.0F;
//和最大容量作比較
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//將當(dāng)前map的容量和擴(kuò)容閾值作比較，如果超過了閾值就需要執(zhí)行擴(kuò)容方法
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();//計算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這個方法重新計算了Node<K,V>[] table的容量和擴(kuò)容閾值
final Node<K,V>[] resize() {
//oldTab是當(dāng)前的table數(shù)組
Node<K,V>[] oldTab = table;
//得到oldTab的長度
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) {
//考慮容量值不能超過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) {//計算新的擴(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ù)組中缘薛，這里面需要考慮的問題是因為擴(kuò)容指針數(shù)組的長度變?yōu)樵瓉淼?倍窍育，結(jié)點(diǎn)對應(yīng)的位置可能會發(fā)生改變，也就是我們需要處理可能會發(fā)生的哈希沖突的問題宴胧。
@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ù)組中只有一個結(jié)點(diǎn)
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//判斷出當(dāng)前節(jié)點(diǎn)是TreeNode類型漱抓，也就是紅黑樹類型的結(jié)點(diǎn)需要做自己的變化
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//這里就是做了對可能產(chǎn)生的哈希沖突的處理，主要計算過程在下面解釋-->解釋一
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;
}
解釋一
可以看到在這部分多出來了兩個新的鏈表lo和hi恕齐。lo存放那些和之前hash表中位置沒有改變的結(jié)點(diǎn)乞娄，hi就用來存放產(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表中的位置，前面提到過仪或。公式1的效果就是為了判斷擴(kuò)容后結(jié)點(diǎn)存在的位置是否發(fā)生了改變确镊，結(jié)果為true,就說明沒有發(fā)生改變。也就是公式2和公式3計算出來的效果是一樣的范删。舉個栗子:
舊的數(shù)組的容量為16蕾域，則新的數(shù)組的容量為32。計算值的話就是：
e.hash & 0x0F(0000 1111 為15)——舊
e.hash & 0x1F(0001 1111 為31)——新
e.hash & 0x10(0001 0000)——e.hash & oldCap
新數(shù)組和舊數(shù)組的長度之間會向高位移一個1,也就是說看結(jié)點(diǎn)的hash值在對應(yīng)的高位是1還是0到旦，是0就插入lo隊列是0就插入hi隊列旨巷。
看到了一篇博客上寫的，分析的很清楚添忘，圖文并茂采呐。。搁骑。感覺自己說的不是很清楚懈万。。靶病。java集合——HashMap
putVal
在putMapEntries方法中擴(kuò)容完會遍歷Map集合会通，獲得key和value后調(diào)用putVal方法，將key和value作為參數(shù)傳入娄周。下面來看看這個方法是干嘛的涕侈。
見下面
put函數(shù)的實現(xiàn)
平常我們會通過調(diào)用map.put方法來向集合中放入一個鍵值對。
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或者長度為0煤辨，就進(jìn)行初始化裳涛，調(diào)用resize方法
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果當(dāng)前Node對應(yīng)的位置還沒有其它結(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是同一個對象就覆蓋之前的值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//當(dāng)前節(jié)點(diǎn)是紅黑樹結(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)前修改或者插入的值寫入
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//增加修改次數(shù)
//超過了擴(kuò)容閾值，調(diào)用resize方法
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
putVal函數(shù)的大致思路為：
- 對key的hashCode()做hash众辨，然后再計算index;
- 如果沒有碰撞直接放到bucket里端三；
- 如果碰撞了，以鏈表的形式存在buckets后鹃彻；
- 如果碰撞導(dǎo)致鏈表過長(>=TREEIFY_THRESHOLD),就把鏈表轉(zhuǎn)成紅黑樹郊闯；
- 如果結(jié)點(diǎn)已經(jīng)存在就替換old value(保證key的唯一性)
- 如果bucket滿了，就調(diào)用resize蛛株。
get函數(shù)的實現(xiàn)
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
實際調(diào)用的是getNode方法团赁，看過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ù)組不為空且長度大于0且當(dāng)前單元中有Node結(jié)點(diǎn)
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果是第一個結(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)是紅黑樹結(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里的第一個節(jié)點(diǎn)，直接命中谨履；
- 若第一個未命中欢摄，就去遍歷查找。一種是在樹的結(jié)構(gòu)中查找笋粟，一種就是在單鏈表中查找怀挠。
到這里HashMap中的基本重要方法就分析完了析蝴，主要有兩個屬性需要特別關(guān)注:
- threshold 擴(kuò)容閾值
- loadFactor 負(fù)載因子
幾個方法：
- tableSizeFor():計算擴(kuò)容閾值
- resize():擴(kuò)容Node<K,V> tab數(shù)組
- putVal():往map中添加值
- getVal():獲取map中的值
- hash():計算hashCode()的hash值
這里再對一些地方進(jìn)行解釋：
在java中，散列表用鏈表數(shù)組實現(xiàn)绿淋。每個鏈表被稱為桶(bucket)嫌变，要想查找表中對象的位置，就要先計算它的散列碼躬它，然后與桶的總數(shù)取余腾啥，所得的結(jié)果就是保存這個元素的桶的索引
兩個重要參數(shù)
容量(Capacity)和負(fù)載因子(LoadFactor)。
- Capacity:就是bucket的大小
- LoadFactor:就是bucket填滿程度的最大比列
如果對迭代性能要求很高的話冯吓，不要把Capacity設(shè)置過大倘待，也不要把LoadFactor設(shè)置過小。當(dāng)bucket中的entries的數(shù)目大于capacity*loadfactor時就需要調(diào)整bucket大小為當(dāng)前的2倍组贺。
hash函數(shù)的實現(xiàn)
HashMap中的hash()
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這里對key為null還做了處理凸舵，key為null,hash后等于0，說明HashMap是支持key為null的失尖。
可以看到這里是對key的hashCode值的前16位和后16位進(jìn)行異或運(yùn)算啊奄，有一幅圖：
image
這里進(jìn)行取前16位和后16位分別進(jìn)行異或是為了減少在數(shù)組中插入值時產(chǎn)生頻繁的碰撞∠瞥保可以這樣去想如果當(dāng)前的數(shù)組長度比較小菇夸，比如說是10，那么在進(jìn)行(n-1)&hash時仪吧，使用的其實只是hashcode()值的后一位庄新，那么這樣就會很容易產(chǎn)生碰撞。因此通過高16位和低16位異或的操作薯鼠，既減少了系統(tǒng)的開銷择诈，也不會造成因為高位沒有參與下標(biāo)的計算(table長度比較小時)，引起的碰撞出皇。
如果還是產(chǎn)生了碰撞羞芍，HashMap設(shè)計者使用了紅黑樹O(logn)去做。
問題總結(jié)
HashMap應(yīng)該是面試中的高頻考點(diǎn)了郊艘，這里總結(jié)一下應(yīng)該怎么回答問題荷科。
- 講一講HashMap?
HashMap底層的數(shù)據(jù)結(jié)構(gòu)是用數(shù)組+鏈表+紅黑樹實現(xiàn)的，當(dāng)鏈表中節(jié)點(diǎn)的個數(shù)大于8的時候鏈表會進(jìn)行樹化暇仲，當(dāng)節(jié)點(diǎn)的個數(shù)小于等于6的時候會恢復(fù)成鏈表的結(jié)構(gòu)步做。HashMap默認(rèn)初始容量為16，容量的大小一般為2的次方冪奈附，HashMap的大小會根據(jù)要存入數(shù)據(jù)的多少進(jìn)行擴(kuò)容，有三個重要的值煮剧，Capacity容量就是HashMap當(dāng)前所能放入的所有鍵值對斥滤，loadFactor擴(kuò)容因子一般為0.75代表填滿當(dāng)前map容量的最大比例将鸵，threshold擴(kuò)容閾值，它的大小為(容量*擴(kuò)容因子),當(dāng)要加入值的個數(shù)加上之前加入過的值的總和大于擴(kuò)容閾值需要對HashMap進(jìn)行擴(kuò)容佑颇，會調(diào)用resize函數(shù)顶掉，map的容量會變?yōu)橹暗?倍，擴(kuò)容閾值也會變?yōu)橹暗膬杀短粜亍＿€有常用的加入元素和取出元素的get和put方法痒筒，get方法會先去判斷當(dāng)前key的hashCode的hash值，如果存在且是第一個節(jié)點(diǎn)就取出茬贵，如果不是就去遍歷當(dāng)前的鏈表簿透，如果當(dāng)前要查詢的節(jié)點(diǎn)是紅黑樹節(jié)點(diǎn)就去在樹中尋找，否則就去遍歷鏈表解藻。put方法在放入一個entry的時候會先計算hash值并計算index值老充，也就是當(dāng)前要放入的節(jié)點(diǎn)的位置，如果當(dāng)前位置為空就創(chuàng)建結(jié)點(diǎn)插入螟左，如果之前有節(jié)點(diǎn)放入就去遍歷檢查有沒有重復(fù)的節(jié)點(diǎn)啡浊，有就替換現(xiàn)有的節(jié)點(diǎn)，保證key的唯一性胶背。
- 為什么使用HashMap?
HashMap是一個散列桶(數(shù)組和鏈表)巷嚣，它存儲的內(nèi)容是鍵值對(key-value)映射
HashMap采用了數(shù)組和鏈表的數(shù)據(jù)結(jié)構(gòu)，能在查詢和修改方面繼承了數(shù)組的線性查找和鏈表的易于刪除拋棄的節(jié)點(diǎn)
HashMap是非synchronize的钳吟，所以HashMap很快
HashMap可以接受null鍵和值涂籽，但是HashTable不能。(HashMap在key為null時在hash方法中做了處理)
- HashMap線程安全么砸抛？還知道其他Map類的集合么评雌？和HashMap有什么區(qū)別？
不是線程安全的直焙，在對HashMap的操作中并沒有上鎖景东。在多線程訪問使用put方法插入元素，發(fā)生哈希碰撞可能會造成數(shù)據(jù)的丟失奔誓。還有resize方法也是不安全的斤吐，多線程下都會創(chuàng)建一個新的table數(shù)組，但最終只有一個對象替換之前的舊的table數(shù)組厨喂。
了解到的其他Map類:
HashTable:也是數(shù)組+鏈表的存儲方式和措，內(nèi)部共享數(shù)據(jù)的方法添加了synchronized，保證了線程安全蜕煌。
LinkedHashMap:(HashMap+LinkedList)存入的數(shù)據(jù)是有序的派阱。實現(xiàn)了Lru緩存。
ConcurrentHashMap:引入了CAS,根據(jù)同步級別對map的一部分上鎖斜纪。引入了分割贫母，不論變的多么大僅僅需要鎖定map的某個部分文兑，其他的線程不需要等到迭代完成才能訪問map
- HashMap的擴(kuò)容機(jī)制是如何實現(xiàn)的？
HashMap的擴(kuò)容機(jī)制要提到三個變量腺劣，threshold擴(kuò)容閾值绿贞、loadFactor擴(kuò)容因子一般都為0.75、capacity容量橘原，這三個變量之間的關(guān)系是擴(kuò)容閾值=擴(kuò)容因子*總?cè)萘考簿褪钦f在往當(dāng)前map中添加元素的時候會去檢查添加的新值加上之前已經(jīng)有個元素的個數(shù)時候會超過當(dāng)前map的擴(kuò)容閾值，如果超過了就需要擴(kuò)容趾断。如果當(dāng)前容量非常大甚至超過了最大容量2^30拒名，那么就把當(dāng)前容量設(shè)置為Integer.MAX_VALUE,否則就將當(dāng)前的map容量和擴(kuò)容閾值都設(shè)置為之前的2倍。
- HashMap中的hash方法是怎么實現(xiàn)的歼冰？
hash方法其實是根據(jù)key的hashCode值靡狞，取這個值的前16位和后16位進(jìn)行異或操作，在通過(n-1)&hash得到當(dāng)前節(jié)點(diǎn)所要放入的數(shù)組的下標(biāo)隔嫡。
