concurrenthashmap

1.concurrenthashmap1.8的实现

image.png

总结：
JDK1.8底层是散列表(数组+链表)+红黑树
ConCurrentHashMap支持高并发的访问和更新，它是线程安全的
检索操作不用加锁，get方法是非阻塞的
size()和containsValue()可能需要锁定整个表
key和value都不允许为null
2 1.7的实现
上面指明的是JDK1.8底层是：散列表+红黑树，也就意味着，JDK1.7的底层跟JDK1.8是不同的~

image.png
Hashtable是在每个方法上都加上了Synchronized完成同步，效率低下。
ConcurrentHashMap通过在部分加锁和利用CAS算法来实现同步。

CAS（比较与交换，Compare and swap） 是一种有名的无锁算法

CAS有3个操作数

内存值V
旧的预期值A
要修改的新值B
当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做

当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值(A和内存值V相同时，将内存值V修改为B)，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试(否则什么都不做)
看了上面的描述应该就很容易理解了，先比较是否相等，如果相等则替换(CAS算法)
ConcurrentHashMap(JDK1.8)为什么要使用synchronized而不是可重入锁？
为什么是synchronized，而不是可重入锁

1. 减少内存开销
   假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承AQS来获得同步支持。但并不是每个节点都需要获得同步支持的，只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。
2. 获得JVM的支持
   可重入锁毕竟是API这个级别的，后续的性能优化空间很小。
   synchronized则是JVM直接支持的，JVM能够在运行时作出相应的优化措施：锁粗化、锁消除、锁自旋等等。这就使得synchronized能够随着JDK版本的升级而不改动代码的前提下获得性能上的提升。