JAVA7

Java7的ConcurrentHashMap里有多把锁，每一把锁用于其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率呢。这就是“锁分离”技术。

ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁（继承了ReentrantLock），在ConcurrentHashMap里扮演锁的角色，HashEntry则用于存储键值对数据。

ConcurrentHashMap底层逻辑结构

一个ConcurrentHashMap里包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构，Segment数组中每个Segment里包含一个HashEntry数组，一个HashEntry数组中的每个hashEntry对象是一个链表的头结点，每个链表结构中包含的元素才是Map集合中的key-value键值对。如下图：

由上图可见，ConcurrentHashMap的数据结构；一个Segment对应（锁住）一个HashEntry数组。

每个Segment守护着一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。

确定插入的元素在哪一个Segment的位置，当然也是Hash,这个算法也是左移、右移等，然后再插入到具体的HashEntry数组中。

Java7中ConcurrentHashMap使用的就是锁分段技术，ConcurrentHashMap由多个Segment组成(Segment下包含很多Node，也就是我们的键值对了)，每个Segment都有把锁来实现线程安全，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

因此，关于ConcurrentHashMap就转化为了对Segment的研究。这是因为，ConcurrentHashMap的get、put操作是直接委托给Segment的get、put方法。

JAVA8

 个人理解：Java8中的锁的粒度比Java7中更细了，Java8锁住的一个某一个数组元素table[i](头节点)，而Java7中segment锁住的是一个HashEntry数组，相当于锁住了多个数组元素；所以我感觉Java8中ConcurrentHashMap多线程环境下 put效率更高。

HashMap集合底层的数组Node[] table的某一个元素table[i]（即某一个链表的头结点），表示Map集合一些泛型对象构成的链表或者红黑树。

static class Node implements Map.Entry {final int hash;    //用来定位数组索引位置final K key;V value;Node next;   //链表的下一个nodeNode(int hash, K key, V value, Node next) { ... }public final K getKey(){ ... }public final V getValue() { ... }public final String toString() { ... }public final int hashCode() { ... }public final V setValue(V newValue) { ... }public final boolean equals(Object o) { ... }
}

（重点）

 为什么链表长度大于8就要转红黑树？

红黑树的插入、删除和遍历的最坏时间复杂度都是log(n)，因此，意外的情况或者恶意使用下导致hashCode()方法的返回值很差时，只要Key具有可比性，性能的下降将会是"优雅"的。
但由于TreeNodes的空间占用是常规Nodes的两倍，所以只有桶中包含足够多的元素以供使用时，我们才应该使用树。那么为什么这个数字会是8呢？

官方文档的一段描述：

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are:0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million

理想情况下，在随机哈希代码下，桶中的节点频率遵循泊松分布，文中给出了桶长度k的频率表。
由频率表可以看出，桶的长度超过8的概率非常非常小（一亿分之六）。所以作者应该是根据概率统计而选择了8作为阀值，由此可见，这个选择是非常严谨和科学的。

所以链表转红黑树概率很低；但是一旦超过8链表的查询、插入、删除效率综合来看比不上红黑树的效率(本文末有对红黑树简单介绍)。

Java8 HashMap的hash算法，如果key为null，hash值为0；如果不为null，直接将key的hashcode值h与h无符号右移16位后的数进行按位异或^位运算 

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

JDK1.8的ConcurrentHashMap中Segment虽保留，但已经简化属性，仅仅是为了兼容旧版本。

/*** Stripped-down version of helper class used in previous version,* declared for the sake of serialization compatibility*/static class Segment extends ReentrantLock implements Serializable {private static final long serialVersionUID = 2249069246763182397L;final float loadFactor;Segment(float lf) { this.loadFactor = lf; }}

JAVA8中ConcurrentHashMap的底层与Java8的HashMap有相通之处，底层依然由“数组”+链表+红黑树来实现的，底层结构存放的是TreeBin对象，而不是TreeNode对象；TreeBin包装的很多TreeNode节点，它代替了TreeNode的根节点，也就是说在实际的ConcurrentHashMap“数组”中，存放的是TreeBin对象，而不是TreeNode对象，这是与HashMap的区别，另外它还带有了读写锁。

ConcurrentHashMap实现中借用了较多的CAS(Compare And Swap)算法(sun.misc.Unsafe对象中有很多native本地方法，如unsafe.compareAndSwapInt(this, valueOffset, expect, update))。

意思是如果valueOffset位置包含的值与expect值相同，则更新valueOffset位置的值为update，并返回true，否则不更新，返回false。

我理解为如果将要更新的变量的值如果和这个线程从Map中取出值相同，那么就更新，否则就不更新(和CAS的思想一样)。

ConcurrentHashMap既然借助了CAS来实现非阻塞的无锁实现线程安全，那么是不是就没有用锁了呢？？答案：还是使用了synchronized关键字进行同步了的，在哪里使用了呢？在操作hash值相同的链表或红黑树的头结点还是会synchronized上锁，这样才能保证线程安全。

（重点）

因为如果不锁住该位置的头结点，当一个线程在对该Hash数组的该位置的链表或者红黑树进行写操作时，如果其他线程操作（修改，添加元素，删除等）引起了Map的resize(扩容或缩减)，该链表或红黑树的hash值可能会发生变化，而正在进行写操作（如put）的线程会因为hash值改变而找不到该位置对于的元素，还有例如插入到当前尾结点后面，如果当前尾结点正好被删除了就会有问题；

锁住了头结点，其他线程就无法操作（修改，添加元素，删除等）该链表或者红黑树，当持有锁的线程操作完毕，释放头结点锁，其他线程才有机会获得该位置的锁，然后进行操作。

ConcurrentHashMap整个类的源码，和HashMap的实现基本一模一样，当有修改操作时借助了synchronized来对table[i](头结点)进行锁定保证了线程安全以及使用了CAS来保证原子性操作，其它的基本一致，例如：ConcurrentHashMap的get(int key)方法的实现思路为：根据key的hash值找到其在table所对应的位置i,然后在table[i]位置所存储的链表(或者是树)进行查找是否有键为key的节点，如果有，则返回节点对应的value，否则返回null。思路是不是很熟悉，是不是和HashMap中该方法的思路一样。所以，如果你也在看ConcurrentHashMap的源码，不要害怕，思路还是原来的思路，只是多了些许东西罢了。

为什么要指定HashMap的容量？

首先创建HashMap指定容量比如1024后，并不是HashMap的size不是1024，而是0，插入多少元素，size就是多少；

然后如果不指定HashMap的容量，要插入768个元素，第一次容量为16，需要持续扩容多次到1024，才能保存1024*0.75=768个元素；

而HashMap扩容是非常非常消耗性能的，每次先创建2倍当前容量的新数组，然后再将老数组中的所有元素再次通过hash&(length-1)的方式散列到HashMap中。

ConcurrentHashMap类中相关属性的介绍

sizeCtl最重要的属性之一，看源码之前，这个属性表示什么意思，一定要记住。

private transient volatile int sizeCtl;//控制标识符

sizeCtl是控制标识符，不同的值表示不同的意义。

• 负数代表正在进行初始化或扩容操作 ,其中-1代表正在初始化 ；-N（N>1） 表示有N-1个线程正在进行扩容操作
• 0表示未被初始化；
• 正数表示下一次进行扩容的大小，sizeCtl的值 = 当前ConcurrentHashMap容量*0.75，这与loadfactor是对应的。实际容量>=sizeCtl，则扩容。

1、 transient volatile Node[] table;

是一个Node数组，第一次插入数据的时候初始化，大小是2的幂次方。这就是我们所说的底层结构：”数组+链表（或树）”。

注意这里的Node数组加了volatile（volatile关键字的作用）进行修饰，table数组在内存中对所有线程都及时可见，如果一个线程修改了table数组的值，其他线程中如果自己的线程栈中有table的副本，就会把table缓存行设置为失效，强制从内存中读取table数组的值。

所以一个线程调用ConcurrentHashMap的get方法也能获得最新的Map集合元素的值（迭代器可能是旧值）。

2、private static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量

3、private static final intDEFAULT_CAPACITY = 16;

4、static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // MAX_VALUE=2^31-1=2147483647

5、private static finalint DEFAULT_CONCURRENCY_LEVEL = 16;

6、private static final float LOAD_FACTOR = 0.75f;

7、static final int TREEIFY_THRESHOLD = 8; // 链表转树的阈值，如果table[i]下面的链表长度大于8时就转化为数

8、static final int UNTREEIFY_THRESHOLD = 6; //树转链表的阈值，小于等于6是转为链表，仅在扩容tranfer时才可能树转链表

9、static final int MIN_TREEIFY_CAPACITY = 64;

10、private static final int MIN_TRANSFER_STRIDE = 16;

11、private static int RESIZE_STAMP_BITS = 16;

12、private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; // help resize的最大线程数

13、private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

14、static final int MOVED = -1; // hash for forwarding nodes（节点在Map中的hash值）、标示位

15、static final int TREEBIN = -2; // hash for roots of trees（树根节点的hash值）

16、static final int RESERVED = -3; // hash for transient reservations（保留节点的hash值，为了扩容的时候吧）

在ConcurrentHashMap中有一个构造方法中有一个参数：concurrencyLevel，表示能够同时更新ConccurentHashMap且不产生锁竞争的最大线程数。默认值为16，(即允许16个线程并发可能不会产生竞争)。为了保证并发的性能，我们要很好的估计出concurrencyLevel值，不然要么竞争相当厉害，从而导致线程试图写入当前锁定的段时阻塞。

ConcurrentHashMap的get()方法没有对任何对象加锁，所以可能会读到旧的数据（比如通过迭代器遍历的时候，其他线程修改了数组元素），和HashMap的get方法的原理是一模一样的。 

ConcurrentHashMap链表转树时，并不会直接转，正如注释（Nodes for use in TreeBins）所说，只是把这些节点包装成TreeNode放到TreeBin中，再由TreeBin来转化红黑树。

ConcurrentHashMap不允许null key或value，HashMap可以。

(重点)

putVal方法

putVal(K key, V value, boolean onlyIfAbsent, boolean evict)方法干的工作如下：
1、检查key/value是否为null，如果为null，则抛异常，否则进行2
2、进入for死循环，进行3
3、检查table是否初始化了，如果没有，则调用initTable()进行初始化然后进行 2，否则进行4
4、根据key的hash值计算出其应该在table中储存的位置i（根据key的hashcode计算出Hash值，在将Hash值与length-1进行按位与，length是2的整数次幂，减1后的二进制与Hash值进行按位与相当于取余运算,但取余的位运算次数肯定不止1次，而这里一次位运算就得出结果，效率更高），取出table[i]的节点用f表示。
根据f的不同有如下三种情况：

　　1）如果table[i]==null(即该位置的节点为空，没有发生碰撞)，则利用CAS操作直接存储在该位置，如果CAS操作成功则退出死循环。
　　2）如果table[i]!=null(即该位置已经有其它节点，发生碰撞)，碰撞处理也有两种情况
　　　　2.1）检查table[i]的节点的hash是否等于MOVED(-1)，如果等于，则检测到正在扩容，则帮助其扩容
　　　　2.2）说明table[i]的节点的hash值不等于MOVED，synchronized锁住头结点table[i]，进行插入操作；

　　　　　　  如果table[i]为链表节点，则将此节点插入链表末尾中即可;

　　　　　　  如果table[i]为树节点，则将此节点插入树中即可;

　　　　　　  插入成功后，进行 5

5、如果table[i]的节点是链表节点，则检查table的第i个位置的链表的元素个数是否大于了8，大于8就需要转化为树，如果需要则调用treeifyBin函数进行转化。
　　链表转树：将数组tab的第index位置的链表转化为红黑树。
6、插入成功后，如果key已经存在，返回oldValue；key开始不存在，返回null。

上面第4点中的2)中的2.1)帮助扩容：如果当前正在扩容，则尝试协助其扩容，死循环再次发挥了重试的作用，有趣的是ConcurrentHashMap是可以多线程同时扩容的。

这里说协助的原因在于，对于数组扩容，一般分为两步：1.新建一个更大的数组；2.将原数组数据（重新散列Hash值）copy到新数组中。

对于第一步，ConcurrentHashMap通过CAS来控制一个int变量保证新建数组这一步建一个更大的数组只会执行一次；

对于第二步，ConcurrentHashMap采用CAS + synchronized + 移动后标记 的方式来达到多线程扩容的目的。

感兴趣可以查看transfer函数。 

目前的猜想多线程扩容可能是：多线程操作不同的table位置的链表或红黑树，将元素h&(length-1)散列到新的table数组中。

ConcurrentHashMap是如何实现高效的并发操作，这得益于ConcurrentHashMap中的如下三个函数(sun.misc.Unsafe U)：

/*3个用的比较多的CAS操作*/@SuppressWarnings("unchecked") // ASHIFT等均为private static final  static final  Node tabAt(Node[] tab, int i) { // 获取索引i处Node  return (Node)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);  }  // 利用CAS算法设置i位置上的Node节点（将c和table[i]比较，相同则插入v）。  static final  boolean casTabAt(Node[] tab, int i,  Node c, Node v) {  return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);  }  // 在链表转树时用到了这个方法；设置节点位置的值，仅在上锁区被调用  static final  void setTabAt(Node[] tab, int i, Node v) {  U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);  }

private final void treeifyBin(Node[] tab, int index) {……  
}treeifyBin方法的思想：检查下table的长度（Map的容量，不是乘以加载因子的那个，也不是目前集合中元素的个数）是否大于等于MIN_TREEIFY_CAPACITY（64），如果不大于，
则调用tryPresize方法将table两倍扩容就可以了，就不降链表转化为树了；如果大于，则就将table[i]的链表转化为树。

public long mappingCount() {long n = sumCount();return (n < 0L) ? 0L : n; // ignore transient negative values
}这是Java8中查询元素个数的方法mappingCount,返回值是long；这个应该用来代替size()方法被使用。这是因为ConcurrentHashMap可能比包含更多的映射结果，即超过int类型的
最大值（size()方法的返回值是int）；这个方法返回值是一个估计值，由于存在并发的插入和删除，因此返回值可能与实际值会有出入。

final long sumCount() {CounterCell[] as = counterCells; CounterCell a;long sum = baseCount;if (as != null) {for (int i = 0; i < as.length; ++i) {if ((a = as[i]) != null)sum += a.value;}}return sum;}
元素个数

ConcurrentHashMap 中的迭代器

在遍历过程中，如果已经遍历的数组上的内容变化了，迭代器不会抛出 ConcurrentModificationException 异常。

如果未遍历的数组上的内容发生了变化，则有可能反映到迭代过程中。

这就是 ConcurrentHashMap 迭代器弱一致的表现。

在这种迭代方式中，当 iterator 被创建后，集合再发生改变就不再是抛出 ConcurrentModificationException，取而代之的是在改变时 new 新的数据 从而不影响原有的数据，iterator 完成后再将头指针替换为新的数据，这样 iterator 线程可以使用原来老的数据，而写线程也可以并发的完成改变，更重要的，这保证了多个线程并发执行的连续性和扩展性，是性能提升的关键。 总结，ConcurrentHashMap 的弱一致性主要是为了提升效率，是一致性 与效率之间的一种权衡。

红黑树简单介绍

算法导论中lgn默认都是以2为底的，即为log2n。

红黑树使二叉搜索树更加平衡：红黑树是一种二叉搜索树，但在每个节点上增加一个存储位表示节点的颜色，可是 red 或 black，红黑树的查找、插入、删除的时间复杂度最坏为 O(lgn)；

因为由 n 个节点随机生成的二叉搜索树的高度为 lgn，所以二叉搜索树的一般操作的执行时间为 O(lgn)。

红黑树是牺牲了严格的高度平衡的优越条件为代价，红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。

此外，由于它的设计，任何不平衡都会在三次旋转之内解决。

红黑树的查询性能略微逊色于AVL(平衡二叉查找树)树，因为他比avl树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的avl树最多多一次比较；

但是，红黑树在插入和删除上完胜avl树，avl树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于avl树为了维持平衡的开销要小得多

红黑树的特性大致有三个（换句话说，插入、删除节点后整个红黑树也必须满足下面的三个性质，如果不满足则必须进行旋转）：
1.根节点与叶节点都是黑色节点，其中叶节点为Null节点
2.每个红色节点的两个子节点都是黑色节点，换句话说就是不能有连续两个红色节点，但是黑色节点可以连续
3.从根节点到所有叶子节点上的黑色节点数量是相同的

上述的性质约束了红黑树的关键：从根到叶子的最长可能路径不多于最短可能路径的两倍长。

得到这个结论的理由是：
红黑树中最短的可能路径是全部为黑色节点的路径；
红黑树中最长的可能路径是红黑相间的路径。

链表转红黑树、红黑树的插入与删除等没有详细说明。

ConcurrentHashMap中红黑树相关：https://blog.csdn.net/chenssy/article/details/73749297

红黑树30张图详解！！！

来源：https://blog.csdn.net/u010412719/article/details/52145145

来源：http://www.importnew.com/20386.html

浅析几种线程安全模型-importNew

 https://blog.csdn.net/daiyuhe/article/details/89424736