只有JAVA8的环境，就看8的吧
欢迎评论，如果写的不好，我优化
首先来个试验：
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
少了好几个值，确实不安全
我们来看看内部实现，点开HashMap类：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
JAVA8开始，HashMap内部使用的是一个Node对象，所以你塞进去的每个K、V键值对都会生成一个Node对象，并且Node对象有next可以指向下一个对象，串联起来，这样就避免了使用List去管理同一个hash桶中的多个对象；
我们来看看put方法,往下点两层到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;
}
哦呦，眼花缭乱
来，耐着性子一点点看
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
table为null或者长度为0，就调resize初始化一下，待会我们再来看resize；
并发下，可能初始化多遍；
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
用&符号取模后发现这个hash槽位是空的，那直接把这个node放到这个槽位即可；
并发下，两个线程的值可能相互覆盖，最终只保留到了一个值；
这里顺便提一下取模操作，n是hash捅目前的长度，二进制下一定是100000，减1后就是11111,和当前key值的hash值做&就是hash对n取余；用这种方式的目的就是效率高；
来看看这个槽位不是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;
}
}
使用了一个Node<K,V> e，p就是当前槽位的Node
第一个if：如果传进来的key值和当前槽位的key值相等，e指向当前槽位的Node
第二个else if：如果是个TreeNode，这个是基于红黑树的Node，这个时候就不是串联了，需要调用putTreeVal来把当前的key和value挂上去，红黑树node我们就不深入了，有兴趣自己去看；一般使用好像并不会插入TreeNode；TreeNode是给LinkedHashMap使用的；
第三个else：过来的key值和当前槽位key值不一样，只是恰巧八字比较合，hash冲突了，大家在一个槽位，那样就一个个node.next遍历，挂到最后面去；
最后：计算些其他有用的变量，比如size要和threshold比较，超过就要扩容（threshold=数组长度*loadFactor控制最大元素数量，loadFactor默认0.75）
上述各个变量都没有锁，判空、赋值所有的运算都不安全，多线程操作各个环节都可能出问题
然后我们来看看扩容：
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;
}
很长~~~~~~~~~~~~~~~~~
返回的就是一个Node<K,V>[]数组
扩容提是通过newCap = oldCap << 1和newThr = oldThr << 1; // double threshold来实现容量计算的，扩大两倍；其中cap控制数组长度，threshold控制最大的Node数量
然后新建一个数组Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
接下来就要一个个从老的数组里读取元素，然后重新hash，重新塞一遍，非常耗性能；所以，如果一开始就能预估出有多少数据，在初始化的时候就指定数量public HashMap(int initialCapacity)；
通过(e.hash & oldCap) == 0来判断元素应该属于高区还是低区
比如oldCap==100==4, newCap=100<<1=1000==8原来塞的时候是e.hash是1001，1001 & 1==1塞在第一个槽位，那么1001&100==0就塞回原位，与1001&(1000-1)=1塞在1是一样的；而另外一个e.hash=10101&100=101,就要塞(1+100)到高位去了，和10101&(1000-1)=101算出来是一样的；看，数学多奇妙；这里其实就是到高位后111中把第一个1取出来，分一下高低位就可以，但是大大优化了效率；
这里有个可能发生的死循环（resize后进行get操作），如果两个线程同时扩容，又同时创建了两个新数组，那么在某个槽位，移动同一批Node的时候，比如有个三四个Node分别是a、b、c，上面这个循环是通过e=e.next+loTail.next = e来循环读的，本来线程1的loTail已经移动到b了，后面继续挂个c就完美收官了，这个时候线程2把e突然替换成了a，然后就loTail.next=a,这样a.next=b,b.next=a；下次你get的时候，就在b和a之间绕不出来了；game over；
网友评论