只有JAVA8的環(huán)境，就看8的吧
歡迎評(píng)論颜凯，如果寫(xiě)的不好舀奶，我優(yōu)化
首先來(lái)個(gè)試驗(yàn)：
try {
List<Integer> list1 = new ArrayList();
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < 1000; i++) {
list1.add(i);
}
list1.parallelStream().forEach(
i -> {
try {
map.put(i,i);
}catch (Exception e){
System.out.println(e);
}
}
);
System.out.println("size of map:" + map.size());
} catch (Exception e) {
System.out.println(e);
}
size of map:932
少了好幾個(gè)值暑竟，確實(shí)不安全
我們來(lái)看看內(nèi)部實(shí)現(xiàn)，點(diǎn)開(kāi)HashMap類(lèi)：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
JAVA8開(kāi)始育勺，HashMap內(nèi)部使用的是一個(gè)Node對(duì)象但荤，所以你塞進(jìn)去的每個(gè)K、V鍵值對(duì)都會(huì)生成一個(gè)Node對(duì)象涧至，并且Node對(duì)象有next可以指向下一個(gè)對(duì)象腹躁，串聯(lián)起來(lái)，這樣就避免了使用List去管理同一個(gè)hash桶中的多個(gè)對(duì)象南蓬；
我們來(lái)看看put方法,往下點(diǎn)兩層到putVal：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
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;
}
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)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
哦呦纺非，眼花繚亂
來(lái)，耐著性子一點(diǎn)點(diǎn)看
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
table為null或者長(zhǎng)度為0赘方，就調(diào)resize初始化一下烧颖，待會(huì)我們?cè)賮?lái)看resize；
并發(fā)下窄陡，可能初始化多遍炕淮；
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
用&符號(hào)取模后發(fā)現(xiàn)這個(gè)hash槽位是空的，那直接把這個(gè)node放到這個(gè)槽位即可跳夭；
并發(fā)下涂圆，兩個(gè)線程的值可能相互覆蓋，最終只保留到了一個(gè)值币叹；
這里順便提一下取模操作润歉，n是hash捅目前的長(zhǎng)度，二進(jìn)制下一定是100000套硼，減1后就是11111,和當(dāng)前key值的hash值做&就是hash對(duì)n取余卡辰；用這種方式的目的就是效率高胞皱；
來(lái)看看這個(gè)槽位不是null的時(shí)候咋搞：
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
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;
}
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)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
使用了一個(gè)Node<K,V> e邪意，p就是當(dāng)前槽位的Node
第一個(gè)if：如果傳進(jìn)來(lái)的key值和當(dāng)前槽位的key值相等，e指向當(dāng)前槽位的Node
第二個(gè)else if：如果是個(gè)TreeNode反砌，這個(gè)是基于紅黑樹(shù)的Node雾鬼，這個(gè)時(shí)候就不是串聯(lián)了，需要調(diào)用putTreeVal來(lái)把當(dāng)前的key和value掛上去宴树，紅黑樹(shù)node我們就不深入了策菜，有興趣自己去看；一般使用好像并不會(huì)插入TreeNode；TreeNode是給LinkedHashMap使用的又憨；
第三個(gè)else：過(guò)來(lái)的key值和當(dāng)前槽位key值不一樣翠霍，只是恰巧八字比較合，hash沖突了蠢莺，大家在一個(gè)槽位寒匙，那樣就一個(gè)個(gè)node.next遍歷，掛到最后面去躏将；
最后：計(jì)算些其他有用的變量锄弱，比如size要和threshold比較，超過(guò)就要擴(kuò)容（threshold=數(shù)組長(zhǎng)度*loadFactor控制最大元素?cái)?shù)量祸憋，loadFactor默認(rèn)0.75）
上述各個(gè)變量都沒(méi)有鎖会宪，判空、賦值所有的運(yùn)算都不安全蚯窥，多線程操作各個(gè)環(huán)節(jié)都可能出問(wèn)題
然后我們來(lái)看看擴(kuò)容：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
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;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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"})
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;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((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;
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);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
很長(zhǎng)~~~~~~~~~~~~~~~~~
返回的就是一個(gè)Node<K,V>[]數(shù)組
擴(kuò)容提是通過(guò)newCap = oldCap << 1和newThr = oldThr << 1; // double threshold來(lái)實(shí)現(xiàn)容量計(jì)算的掸鹅，擴(kuò)大兩倍；其中cap控制數(shù)組長(zhǎng)度沟沙，threshold控制最大的Node數(shù)量
然后新建一個(gè)數(shù)組Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
接下來(lái)就要一個(gè)個(gè)從老的數(shù)組里讀取元素河劝，然后重新hash，重新塞一遍矛紫，非常耗性能赎瞎；所以，如果一開(kāi)始就能預(yù)估出有多少數(shù)據(jù)颊咬，在初始化的時(shí)候就指定數(shù)量public HashMap(int initialCapacity)务甥；
通過(guò)(e.hash & oldCap) == 0來(lái)判斷元素應(yīng)該屬于高區(qū)還是低區(qū)
比如oldCap==100==4, newCap=100<<1=1000==8原來(lái)塞的時(shí)候是e.hash是1001，1001 & 1==1塞在第一個(gè)槽位喳篇，那么1001&100==0就塞回原位敞临，與1001&(1000-1)=1塞在1是一樣的；而另外一個(gè)e.hash=10101&100=101,就要塞(1+100)到高位去了麸澜，和10101&(1000-1)=101算出來(lái)是一樣的挺尿；看，數(shù)學(xué)多奇妙炊邦；這里其實(shí)就是到高位后111中把第一個(gè)1取出來(lái)编矾，分一下高低位就可以，但是大大優(yōu)化了效率馁害；
這里有個(gè)可能發(fā)生的死循環(huán)（resize后進(jìn)行g(shù)et操作）窄俏，如果兩個(gè)線程同時(shí)擴(kuò)容，又同時(shí)創(chuàng)建了兩個(gè)新數(shù)組碘菜，那么在某個(gè)槽位凹蜈，移動(dòng)同一批Node的時(shí)候限寞，比如有個(gè)三四個(gè)Node分別是a、b仰坦、c履植，上面這個(gè)循環(huán)是通過(guò)e=e.next+loTail.next = e來(lái)循環(huán)讀的，本來(lái)線程1的loTail已經(jīng)移動(dòng)到b了悄晃，后面繼續(xù)掛個(gè)c就完美收官了静尼，這個(gè)時(shí)候線程2把e突然替換成了a，然后就loTail.next=a,這樣a.next=b,b.next=a传泊；下次你get的時(shí)候鼠渺，就在b和a之間繞不出來(lái)了；game over眷细；
