1. 數(shù)據(jù)結(jié)構(gòu)
在Java中巩搏，是通過數(shù)組和鏈表這倆種數(shù)據(jù)結(jié)構(gòu)來進行數(shù)據(jù)存儲的。
- 數(shù)組：
- 數(shù)組的存儲空間的連續(xù)的说敏，所以占內(nèi)存嚴(yán)重
- 二分查找復(fù)雜度小
- 尋址容易诗赌，插入刪除難
- 鏈表：
- 區(qū)間離散，占用內(nèi)存比較寬松
- 空間復(fù)雜度很小被饿，時間復(fù)雜度很大
- 尋址難四康，插入刪除容易
哈希表(Hash Table)就是這兩者的結(jié)合，插入刪除簡單锹漱，尋址容易箭养，占用內(nèi)存相對寬松。
- 拉鏈法(鏈地址法)：鏈表的數(shù)組
拉鏈法
最常用的哈希表排列法哥牍，一目了然的數(shù)組+鏈表組合毕泌。
存儲規(guī)則：整個數(shù)組長度為16，每個元素存儲的是一個鏈表的頭結(jié)點嗅辣。比如：1%16 = 1撼泛，337%16 = 1，353%16 = 1 澡谭。余數(shù)皆為1愿题，所以這三個元素被存儲在數(shù)組下標(biāo)為1的位置。
解決哈希沖突：同數(shù)組下標(biāo)下蛙奖，通過鏈?zhǔn)浇Y(jié)構(gòu)避免索引值沖突潘酗。
而HashMap就是典型的拉鏈法哈希表結(jié)構(gòu)。
他實際上是一個線性數(shù)組雁仲。他的靜態(tài)內(nèi)部類繼承了一個Entry接口仔夺。這里注意，在jdk1.8中攒砖，在鏈表中加入了紅黑樹（平衡二分查找樹）缸兔。所以1.8版本的HashMap是由數(shù)組+（鏈表+紅黑樹）實現(xiàn)的。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
......
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//hash code value for this map entry
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;
}
}
......
}
乍一眼就能看出是一個bean類吹艇，關(guān)鍵的參數(shù)有三個：key惰蜜，value，next受神，接下來我們看下HashMap的方法與Entry的關(guān)聯(lián)
- get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;//key是否存在抛猖，存在返回key的value值，不存在返回null
//hash(key)獲得key的hash值
}
getNode方法
/**
* 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; //Entry數(shù)組
Node<K,V> first, e;
int n; //數(shù)組長度
K k;
// 1. 定位鍵值對所在桶的位置
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//2.判斷鍵值的hashcode相等，對象相等
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
// 3..如果 first 是 TreeNode 類型财著，則調(diào)用黑紅樹查找方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
-
我們看一下判斷條件养交。前兩個是tab非空判斷，沒什么好說的瓢宦，看下第三個條件。
(first = tab[(n - 1) & hash]) != null其中tab[(n - 1) & hash]這個可能有點難理解灰羽。這里是為了運算出桶在桶數(shù)組中的位置驮履。HashMap 中桶數(shù)組的大小 length 總是2的冪，此時廉嚼，(n - 1) & hash 等價于對 length 取余玫镐。
隨便假設(shè)一對值，比如hash = 98怠噪，n = 21恐似，98 & (21-1) = 0，是不是和下方圖示運算結(jié)果一樣傍念？位運算效率是高于運算符的矫夷，這算是java優(yōu)化中的小細節(jié)。
位運算取余數(shù)
- 這里需注意憋槐，hashcode相同不代表是同一個對象双藕，只有equals才能判斷兩個是否是同一對象（鍵值）
- 黑紅樹是jdk1.8在HashMap的性能優(yōu)化中新添加的特性。它主要有五大性質(zhì)：
- 節(jié)點是紅色或黑色阳仔。
- 根是黑色忧陪。
- 所有葉子都是黑色（葉子是NIL節(jié)點）。
- 每個紅色節(jié)點必須有兩個黑色的子節(jié)點近范。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點嘶摊。）
- 從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點（簡稱黑高）。
紅黑樹
- put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);//1. onlyIfAbsent參數(shù)
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 初始化桶數(shù)組 table
if ((tab = table) == null || (n = tab.length) == 0)
//擴容方法
n = (tab = resize()).length;
// 當(dāng)前key不存在评矩，新建鍵值對加入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果鍵的值以及節(jié)點 hash 等于鏈表中的第一個鍵值對節(jié)點時叶堆，則將 e 指向該鍵值對
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果節(jié)點下引用數(shù)據(jù)結(jié)構(gòu)為紅黑樹，調(diào)用紅黑樹插入法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 鏈表結(jié)構(gòu)稚照，遍歷
for (int binCount = 0; ; ++binCount) {
//不存在當(dāng)前需要插入的節(jié)點
if ((e = p.next) == null) {
//新建一個節(jié)點插入
p.next = newNode(hash, key, value, null);
//鏈表長度超過或等于樹化闕值（8）蹂空，對鏈表進行樹化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//需要插入的節(jié)點已經(jīng)存在了
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)//1.onlyIfAbsent 判斷
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
- onlyIfAbsent這個參數(shù)，牽扯到另外一個put方法：putIfAbsent方法
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
他和put方法唯一的區(qū)別就是onlyIfAbsent的值為true
特點：putIfAbsent在放入數(shù)據(jù)時果录，如果存在重復(fù)的key上枕，那么putIfAbsent不會放入值。
如果傳入key對應(yīng)的value已經(jīng)存在弱恒，就返回存在的value辨萍，不進行替換。如果不存在，就添加key和value锈玉，返回null
- resize方法
resize(),咱們稱之為擴容方法爪飘，只有在兩種情況下會被調(diào)用：
- HashMap實行了懶加載: 新建HashMap時不會對table進行賦值, 而是到第一次插入時, 進行resize時構(gòu)建table;
- 當(dāng)HashMap的
size值大于threshold時, 會進行resize(); 看一下threshold在源碼中的注解:// (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; /** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
1 << 4是位運算，結(jié)果threshold默認值為16拉背。
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<K,V>[] resize() {
Node<K,V>[] oldTab = table;//將當(dāng)前table暫存到oldtab來操作
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {//如果老容量大于最大容量
threshold = Integer.MAX_VALUE;//閾值設(shè)置為Integer的最大值师崎，好像是2147483647，遠大于默認的最大容量
return oldTab;//直接返回當(dāng)前table椅棺，不用擴容
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 雙倍擴大老內(nèi)存和老閾值并賦給新的table
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { //這種情況是初始化HashMap時啥參數(shù)都沒加
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {//當(dāng)只滿足老閾值大于0的條件時犁罩，新閾值等于新容量*默認擴容因子
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;//把新的閾值賦給當(dāng)前table
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//創(chuàng)建容量為newCap的新table
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {//對老table進行遍歷
Node<K,V> e;
if ((e = oldTab[j]) != null) {//遍歷到的賦給e進行暫存，同時將老table對應(yīng)項賦值為null
oldTab[j] = null;
if (e.next == null)//將不為空的元素復(fù)制到新table中
newTab[e.hash & (newCap - 1)] = e;//等于是創(chuàng)建一個新的空table然后重新進行元素的put两疚，這里的table長度是原table的兩倍
else if (e instanceof TreeNode)//暫時沒了解紅黑樹
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;//用于保存put后不移位的鏈表
Node<K,V> hiHead = null, hiTail = null;//用于保存put后移位的鏈表
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {//如果與的結(jié)果為0床估，表示不移位，將桶中的頭結(jié)點添加到lohead和lotail中诱渤，往后如果桶中還有不移位的結(jié)點丐巫，就向tail繼續(xù)添加
if (loTail == null)//在后面遍歷lohead和lotail保存到table中時，lohead用于保存頭結(jié)點的位置勺美，lotail用于判斷是否到了末尾
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {//這是添加移位的結(jié)點递胧，與不移位的類似
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {//把不移位的結(jié)點添加到對應(yīng)的鏈表數(shù)組中去
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {//把移位的結(jié)點添加到對應(yīng)的鏈表數(shù)組中去
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
4.線程安全
HashMap是線程不安全的，但是HashTable由于每次put操作就進行鎖死效率十分低下赡茸。那有沒有既效率又線程安全的HashMap呢谓着？
答案就是：ConcurrentHashMap
- 底層采用分段的數(shù)組+鏈表實現(xiàn)，線程安全
- 通過把整個Map分為N個Segment坛掠，可以提供相同的線程安全赊锚，但是效率提升N倍，默認提升16倍屉栓。(讀操作不加鎖舷蒲，由于HashEntry的value變量是 volatile的，也能保證讀取到最新的值友多。)
- Hashtable的synchronized是針對整張Hash表的牲平，即每次鎖住整張表讓線程獨占，ConcurrentHashMap允許多個修改操作并發(fā)進行域滥，其關(guān)鍵在于使用了鎖分離技術(shù)
- 有些方法需要跨段纵柿，比如size()和containsValue()，它們可能需要鎖定整個表而而不僅僅是某個段启绰，這需要按順序鎖定所有段昂儒，操作完畢后，又按順序釋放所有段的鎖
- 擴容：段內(nèi)擴容（段內(nèi)元素超過該段對應(yīng)Entry數(shù)組長度的75%觸發(fā)擴容委可，不會對整個Map進行擴容）渊跋，插入前檢測需不需要擴容，有效避免無效擴容
