ConcurrentHashmap 小结

并发包concurrent包下的ConcurrentHashmap

1.8以前是通过内部分段的方式实现内部分段,最多分16段,允许16个线程同时操作,通过细粒度锁定的方式提高性能

1.8通过数组,链表,红黑树实现

内部实现基本和hashMap一样,只是在每个元素,即每条链表头部加锁,让一个线程进行操作.大量使用了voliate关键字和CAS算法

Node：保存key，value及key的hash值的数据结构。其中value和next都用volatile修饰，保证并发的可见性。

 static class Node<K,V> implements Map.Entry<K,V> {
       final int hash;
       final K key;
       volatile V val;//volatile类型的
       volatile Node<K,V> next;//volatile类型的


       Node(int hash, K key, V val, Node<K,V> next) {
           this.hash = hash;
           this.key = key;
           this.val = val;
           this.next = next;
       }
       //省略部分代码
      } 

put流程
1、第一步根据给定的key的hash值找到其在table中的位置index。

2、找到位置index后，存储进行就好了。

只是这里的存储有三种情况罢了，第一种：table[index]中没有任何其他元素，即此元素没有发生碰撞，这种情况直接存储就好了哈。第二种，table[i]存储的是一个链表，如果链表不存在key则直接加入到链表尾部即可（这里与hashMap相反,hashMap将元素存放在链表头部），如果存在key则更新其对应的value。第三种，table[i]存储的是一个树，则按照树添加节点的方法添加就好。添加完成后,如果节点数>＝8，那么转换链表结构为红黑树结构.

get流程
1、根据key调用spread计算hash值；并根据计算出来的hash值计算出该key在table出现的位置i.

2、检查table是否为空；如果为空，返回null，否则进行3

3、检查table[i]处桶位不为空；如果为空，则返回null，否则进行4

4、先检查table[i]的头结点的key是否满足条件，是则返回头结点的value；否则分别根据树、链表查询。