java|HashMap和ConcurrentHashMap java|基础

前言 Map 这样的 Key Value 在软件开发中是非常经典的结构，常用于在内存中存放数据。
本篇主要想讨论 ConcurrentHashMap 这样一个并发容器，在正式开始之前我觉得有必要谈谈 HashMap，没有它就不会有后面的 ConcurrentHashMap。
Hash 表在讲HashMap之前，我们先来了解下他们底层实现的一种数据结构——Hash 表。
Hash表，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。存放记录的数组叫做哈希表。
在HashMap中，就是将所给的“键”通过哈希函数得到“索引”，然后把内容存在数组中，这样就形成了“键”和内容的映射关系。

文章图片

哈希表
上图可以发现，“键”转换为“索引”的过程就是哈希函数，为了尽可能保证每一个“键”通过哈希函数的转换对应不同的“索引”，就需要对哈希函数进行选择了，使其得到的“索引”分布越均匀越好。
哈希函数的均匀性：

文章图片

哈希函数设计
通过前辈的研究加上实践表明，当把哈希函数得到hashcode值对素数取模时，这样得到的索引是最为均匀的。但是，在HashMap源码中，并不是取模素数的，而是一种等效取模2的n次方的位运算，hash&(length-1)。hash%length==hash&(length-1)的前提是length是2的n次方；之所以使用位运算替代取模，是因为位运算的效率更高，所以也就要求数组的长度必须是2的n次方（索引的分布也是很均匀的）。
哈希函数的一致性：

文章图片

哈希函数设计原则
哈希函数的一致性原则是：当两个对象的equals相等，那么他们的hashcode一定相等。
这就要求我们在重写了equals方法时，必须重写hashcode方法。如果不重写hashcode，则会使用Object的hashcode方法，该方法是以我们创建的对象的地址作为参数求hash的。所以，如果不重写hashcode，两个equals相等的对象会导致hashcode不同（因为不同的对象），这个是不允许的，因为违背了hash函数的一致性原则。
哈希冲突：
当两个不同的元素，通过哈希函数得到了同一个hashcode，则会产生哈希冲突。HashMap的处理方式是，JDK8之前，每一个位置对应一个链表，链式的存放哈希冲突的元素；JDK8开始，当哈希冲突达到一定程度（8个），每一个位置从链表转换成红黑树。因为红黑树的时间复杂度是O(log n)的，效率优于链表。

文章图片

哈希表小结：
哈希表，均摊复杂度是O(1)，因为第一步通过数组索引找到数组位置是O(1)，然后到链表中查找元素的均摊复杂度是O(size/length)，size为元素个数，length为数组长度。由于Hash表的容量是动态扩容的，也就是说随着size和length成正比的，即size/length是一个常数，于是也是O(1)的复杂度，即总的来说，均摊复杂度是O(1)。但是哈希表是没有顺序性的，即无法对元素进行排序。

HashMap 众所周知 HashMap 底层是基于 数组 + 链表 组成的，不过在 jdk1.7 和 1.8 中具体实现稍有不同。
Base 1.7
1.7 中的数据结构图：

文章图片

先来看看 1.7 中的实现。

文章图片

这是 HashMap 中比较核心的几个成员变量；看看分别是什么意思？

初始化桶大小，因为底层是数组，所以这是数组默认的大小。
桶最大值。
默认的负载因子（0.75）
table 真正存放数据的数组。
Map 存放数量的大小。
桶大小，可在初始化时显式指定。
负载因子，可在初始化时显式指定。

重点解释下负载因子：
由于给定的 HashMap 的容量大小是固定的，比如默认初始化：

1public HashMap() { 2this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); 3} 4 5public HashMap(int initialCapacity, float loadFactor) { 6if (initialCapacity < 0) 7throw new IllegalArgumentException("Illegal initial capacity: " + 8initialCapacity); 9if (initialCapacity > MAXIMUM_CAPACITY) 10initialCapacity = MAXIMUM_CAPACITY; 11if (loadFactor <= 0 || Float.isNaN(loadFactor)) 12throw new IllegalArgumentException("Illegal load factor: " + 13loadFactor); 14 15this.loadFactor = loadFactor; 16threshold = initialCapacity; 17init(); 18}

给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。
因此通常建议能提前预估 HashMap 的大小最好，尽量的减少扩容带来的性能损耗。
根据代码可以看到其实真正存放数据的是

transient Entry[] table = (Entry[]) EMPTY_TABLE;

这个数组，那么它又是如何定义的呢？

文章图片

Entry 是 HashMap 中的一个内部类，从他的成员变量很容易看出：

key 就是写入时的键。
value 自然就是值。
开始的时候就提到 HashMap 是由数组和链表组成，所以这个 next 就是用于实现链表结构。
hash 存放的是当前 key 的 hashcode。

知晓了基本结构，那来看看其中重要的写入、获取函数：
put 方法

1public V put(K key, V value) { 2if (table == EMPTY_TABLE) { 3inflateTable(threshold); 4} 5if (key == null) 6return putForNullKey(value); 7int hash = hash(key); 8int i = indexFor(hash, table.length); 9for (Entry e = table[i]; e != null; e = e.next) { 10Object k; 11if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 12V oldValue = https://www.it610.com/article/e.value; 13e.value = value; 14e.recordAccess(this); 15return oldValue; 16} 17} 18 19modCount++; 20addEntry(hash, key, value, i); 21return null; 22}

判断当前数组是否需要初始化。
如果 key 为空，则 put 一个空值进去。
根据 key 计算出 hashcode。
根据计算出的 hashcode 定位出所在桶。
如果桶是一个链表则需要遍历判断里面的 hashcode、key 是否和传入 key 相等，如果相等则进行覆盖，并返回原来的值。
如果桶是空的，说明当前位置没有数据存入；新增一个 Entry 对象写入当前位置。

1void addEntry(int hash, K key, V value, int bucketIndex) { 2if ((size >= threshold) && (null != table[bucketIndex])) { 3resize(2 * table.length); 4hash = (null != key) ? hash(key) : 0; 5bucketIndex = indexFor(hash, table.length); 6} 7 8createEntry(hash, key, value, bucketIndex); 9} 10 11void createEntry(int hash, K key, V value, int bucketIndex) { 12Entry e = table[bucketIndex]; 13table[bucketIndex] = new Entry<>(hash, key, value, e); 14size++; 15}

当调用 addEntry 写入 Entry 时需要判断是否需要扩容。
如果需要就进行两倍扩充，并将当前的 key 重新 hash 并定位。
而在 createEntry 中会将当前位置的桶传入到新建的桶中，如果当前桶有值就会在位置形成链表。
get 方法
再来看看 get 函数：

1public V get(Object key) { 2if (key == null) 3return getForNullKey(); 4Entry entry = getEntry(key); 5 6return null == entry ? null : entry.getValue(); 7} 8 9final Entry getEntry(Object key) { 10if (size == 0) { 11return null; 12} 13 14int hash = (key == null) ? 0 : hash(key); 15for (Entry e = table[indexFor(hash, table.length)]; 16e != null; 17e = e.next) { 18Object k; 19if (e.hash == hash && 20((k = e.key) == key || (key != null && key.equals(k)))) 21return e; 22} 23return null; 24}

首先也是根据 key 计算出 hashcode，然后定位到具体的桶中。
判断该位置是否为链表。
不是链表就根据 key、key 的 hashcode 是否相等来返回值。
为链表则需要遍历直到 key 及 hashcode 相等时候就返回值。
啥都没取到就直接返回 null 。

Base 1.8
不知道 1.7 的实现大家看出需要优化的点没有？
其实一个很明显的地方就是：

当 Hash 冲突严重时，在桶上形成的链表会变的越来越长，这样在查询时的效率就会越来越低；时间复杂度为 O(N)。

因此 1.8 中重点优化了这个查询效率。
1.8 HashMap 结构图：

文章图片

先来看看几个核心的成员变量：

1static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 2 3/** 4* The maximum capacity, used if a higher value is implicitly specified 5* by either of the constructors with arguments. 6* MUST be a power of two <= 1<<30. 7*/ 8static final int MAXIMUM_CAPACITY = 1 << 30; 9 10/** 11* The load factor used when none specified in constructor. 12*/ 13static final float DEFAULT_LOAD_FACTOR = 0.75f; 14 15static final int TREEIFY_THRESHOLD = 8; 16 17transient Node[] table; 18 19/** 20* Holds cached entrySet(). Note that AbstractMap fields are used 21* for keySet() and values(). 22*/ 23transient Set> entrySet; 24 25/** 26* The number of key-value mappings contained in this map. 27*/ 28transient int size;

和 1.7 大体上都差不多，还是有几个重要的区别：

TREEIFY_THRESHOLD 用于判断是否需要将链表转换为红黑树的阈值。
HashEntry 修改为 Node。

Node 的核心组成其实也是和 1.7 中的 HashEntry 一样，存放的都是 key value hashcode next 等数据。
再来看看核心方法。
put 方法

文章图片

看似要比 1.7 的复杂，我们一步步拆解：

判断当前桶是否为空，空的就需要初始化（resize 中会判断是否进行初始化）。
根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空，为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。
如果当前桶有值（ Hash 冲突），那么就要比较当前桶中的 key、key 的 hashcode 与写入的 key 是否相等，相等就赋值给 e,在第 8 步的时候会统一进行赋值及返回。
如果当前桶为红黑树，那就要按照红黑树的方式写入数据。
如果是个链表，就需要将当前的 key、value 封装成一个新节点写入到当前桶的后面（形成链表）。
接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。
如果在遍历过程中找到 key 相同时直接退出遍历。
如果 e != null 就相当于存在相同的 key,那就需要将值覆盖。
最后判断是否需要进行扩容。

get 方法

1public V get(Object key) { 2Node e; 3return (e = getNode(hash(key), key)) == null ? null : e.value; 4} 5 6final Node getNode(int hash, Object key) { 7Node[] tab; Node first, e; int n; K k; 8if ((tab = table) != null && (n = tab.length) > 0 && 9(first = tab[(n - 1) & hash]) != null) { 10if (first.hash == hash && // always check first node 11((k = first.key) == key || (key != null && key.equals(k)))) 12return first; 13if ((e = first.next) != null) { 14if (first instanceof TreeNode) 15return ((TreeNode)first).getTreeNode(hash, key); 16do { 17if (e.hash == hash && 18((k = e.key) == key || (key != null && key.equals(k)))) 19return e; 20} while ((e = e.next) != null); 21} 22} 23return null; 24}

get 方法看起来就要简单许多了。

首先将 key hash 之后取得所定位的桶。
如果桶为空则直接返回 null 。
否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key，是就直接返回 value。
如果第一个不匹配，则判断它的下一个是红黑树还是链表。
红黑树就按照树的查找方式返回值。
不然就按照链表的方式遍历匹配返回值。

从这两个核心方法（get/put）可以看出 1.8 中对大链表做了优化，修改为红黑树之后查询效率直接提高到了 O(logn)。
但是 HashMap 原有的问题也都存在，比如在并发场景下使用时容易出现死循环。

1final HashMap map = new HashMap(); 2for (int i = 0; i < 1000; i++) { 3new Thread(new Runnable() { 4@Override 5public void run() { 6map.put(UUID.randomUUID().toString(), ""); 7} 8}).start(); 9}

但是为什么呢？简单分析下。
看过上文的还记得在 HashMap 扩容的时候会调用 resize() 方法，就是这里的并发操作容易在一个桶上形成环形链表；这样当获取一个不存在的 key 时，计算出的 index 正好是环形链表的下标就会出现死循环。
如下图：

文章图片

文章图片

遍历方式
还有一个值得注意的是 HashMap 的遍历方式，通常有以下几种：

1Iterator entryIterator = map.entrySet().iterator(); 2while (entryIterator.hasNext()) { 3Map.Entry next = entryIterator.next(); 4System.out.println("key=" + next.getKey() + " value="https://www.it610.com/article/+ next.getValue()); 5} 6 7Iterator iterator = map.keySet().iterator(); 8while (iterator.hasNext()){ 9String key = iterator.next(); 10System.out.println("key=" + key + " value="https://www.it610.com/article/+ map.get(key)); 11 12}

强烈建议使用第一种 EntrySet 进行遍历。
第一种可以把 key value 同时取出，第二种还得需要通过 key 取一次 value，效率较低。

简单总结下 HashMap：无论是 1.7 还是 1.8 其实都能看出 JDK 没有对它做任何的同步操作，所以并发会出问题，甚至出现死循环导致系统不可用。

因此 JDK 推出了专项专用的 ConcurrentHashMap ，该类位于 java.util.concurrent 包下，专门用于解决并发问题。

坚持看到这里的朋友算是已经把 ConcurrentHashMap 的基础已经打牢了，下面正式开始分析。

ConcurrentHashMap ConcurrentHashMap 同样也分为 1.7 、1.8 版，两者在实现上略有不同。
Base 1.7
先来看看 1.7 的实现，下面是他的结构图：

文章图片

如图所示，是由 Segment 数组、HashEntry 组成，和 HashMap 一样，仍然是数组加链表。
它的核心成员变量：

1/** 2* Segment 数组，存放数据时首先需要定位到具体的 Segment 中。 3*/ 4final Segment[] segments; 5 6transient Set keySet; 7transient Set> entrySet;

Segment 是 ConcurrentHashMap 的一个内部类，主要的组成如下：

1static final class Segment extends ReentrantLock implements Serializable { 2 3private static final long serialVersionUID = 2249069246763182397L; 4 5// 和 HashMap 中的 HashEntry 作用一样，真正存放数据的桶 6transient volatile HashEntry[] table; 7 8transient int count; 9 10transient int modCount; 11 12transient int threshold; 13 14final float loadFactor; 15 16}

看看其中 HashEntry 的组成：

文章图片

和 HashMap 非常类似，唯一的区别就是其中的核心数据如 value ，以及链表都是 volatile 修饰的，保证了获取时的可见性。
原理上来说：ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。
下面也来看看核心的 put get 方法。
put 方法

1public V put(K key, V value) { 2Segment s; 3if (value =https://www.it610.com/article/= null) 4throw new NullPointerException(); 5int hash = hash(key); 6int j = (hash>>> segmentShift) & segmentMask; 7if ((s = (Segment)UNSAFE.getObject// nonvolatile; recheck 8(segments, (j << SSHIFT) + SBASE)) == null) //in ensureSegment 9s = ensureSegment(j); 10return s.put(key, hash, value, false); 11}

首先是通过 key 定位到 Segment，之后在对应的 Segment 中进行具体的 put。

1final V put(K key, int hash, V value, boolean onlyIfAbsent) { 2HashEntry node = tryLock() ? null : 3scanAndLockForPut(key, hash, value); 4V oldValue; 5try { 6HashEntry[] tab = table; 7int index = (tab.length - 1) & hash; 8HashEntry first = entryAt(tab, index); 9for (HashEntry e = first; ; ) { 10if (e != null) { 11K k; 12if ((k = e.key) == key || 13(e.hash == hash && key.equals(k))) { 14oldValue = https://www.it610.com/article/e.value; 15if (!onlyIfAbsent) { 16e.value = value; 17++modCount; 18} 19break; 20} 21e = e.next; 22} 23else { 24if (node != null) 25node.setNext(first); 26else 27node = new HashEntry(hash, key, value, first); 28int c = count + 1; 29if (c > threshold && tab.length < MAXIMUM_CAPACITY) 30rehash(node); 31else 32setEntryAt(tab, index, node); 33++modCount; 34count = c; 35oldValue = https://www.it610.com/article/null; 36break; 37} 38} 39} finally { 40unlock(); 41} 42return oldValue; 43}

虽然 HashEntry 中的 value 是用 volatile 关键词修饰的，但是并不能保证并发的原子性，所以 put 操作时仍然需要加锁处理。
首先第一步的时候会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁。

文章图片

尝试自旋获取锁。
如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取，保证能获取成功。

文章图片

再结合图看看 put 的流程。

将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。
遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value。
不为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。
最后会解除在 1 中所获取当前 Segment 的锁。

get 方法

1public V get(Object key) { 2Segment s; // manually integrate access methods to reduce overhead 3HashEntry[] tab; 4int h = hash(key); 5long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; 6if ((s = (Segment)UNSAFE.getObjectVolatile(segments, u)) != null && 7(tab = s.table) != null) { 8for (HashEntry e = (HashEntry) UNSAFE.getObjectVolatile 9(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE); 10e != null; e = e.next) { 11K k; 12if ((k = e.key) == key || (e.hash == h && key.equals(k))) 13return e.value; 14} 15} 16return null; 17}

get 逻辑比较简单：
只需要将 Key 通过 Hash 之后定位到具体的 Segment ，再通过一次 Hash 定位到具体的元素上。
由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值。
ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。
Base 1.8
1.7 已经解决了并发问题，并且能支持 N 个 Segment 这么多次数的并发，但依然存在 HashMap 在 1.7 版本中的问题。

那就是查询遍历链表效率太低。

因此 1.8 做了一些数据结构上的调整。
首先来看下底层的组成结构：

文章图片

看起来是不是和 1.8 HashMap 结构类似？
其中抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。

文章图片

也将 1.7 中存放数据的 HashEntry 改为 Node，但作用都是相同的。
其中的 val next 都用了 volatile 修饰，保证了可见性。
put 方法
重点来看看 put 函数：

文章图片

根据 key 计算出 hashcode 。
判断是否需要进行初始化。
f 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
如果都不满足，则利用 synchronized 锁写入数据。
如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。

get 方法

文章图片

根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
如果是红黑树那就按照树的方式获取值。
就不满足那就按照链表的方式遍历获取值。

1.8 在 1.7 的数据结构上做了大的改动，采用红黑树之后可以保证查询效率（O(logn)），甚至取消了 ReentrantLock 改为了 synchronized，这样可以看出在新版的 JDK 中对 synchronized 优化是很到位的。

HashSet 的工作原理：
HashSet 的底层还是 HashMap:

文章图片

HashSet 构造器
对于 HashSet 而言，它是基于 HashMap 实现的，HashSet 底层使用 HashMap 来保存所有元素，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来完成，我们应该为保存到 HashSet 中的对象覆盖 hashCode() 和 equals()。
add 方法：

public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

可知，HashSet 中的 value 都是 PRESENT，其是 Object 对象。当元素 e 在 map 中不存在时， map.put(e, PRESENT) 方法返回 null，即 add 返回 true；如果元素 e 在 map 中已经存在，map.put(e, PRESENT) 方法返回不为 null，即 add 返回 false。从而保证了 set 中元素的不可重复性。
总结看完了整个 HashMap 和 ConcurrentHashMap 在 1.7 和 1.8 中不同的实现方式相信大家对他们的理解应该会更加到位。
其实这块也是面试的重点内容，通常的套路是：

谈谈你理解的 HashMap，讲讲其中的 get put 过程。
1.8 做了什么优化？
是线程安全的嘛？
不安全会导致哪些问题？
如何解决？有没有线程安全的并发容器？
ConcurrentHashMap 是如何实现的？ 1.7、1.8 实现有何不同？为什么这么做？

这一串问题相信大家仔细看完都能怼回面试官。
除了面试会问到之外平时的应用其实也蛮多，像之前谈到的 Guava 中 Cache 的实现就是利用 ConcurrentHashMap 的思想。
同时也能学习 JDK 作者大牛们的优化思路以及并发解决方案。

ConcurrentHashMap与HashMap等的区别 HashMap 我们知道HashMap是线程不安全的，在多线程环境下，使用Hashmap进行put操作会引起死循环，导致CPU利用率接近100%，所以在并发情况下不能使用HashMap。
HashTable HashTable和HashMap的实现原理几乎一样，差别无非是
HashTable不允许key和value为null
HashTable是线程安全的
但是HashTable线程安全的策略实现代价却太大了，简单粗暴，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁。
多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。
ConcurrentHashMap 主要就是为了应对hashmap在并发环境下不安全而诞生的，ConcurrentHashMap的设计与实现非常精巧，大量的利用了volatile，final，CAS等lock-free技术来减少锁竞争对于性能的影响。
我们都知道Map一般都是数组+链表结构（JDK1.8该为数组+红黑树）。

文章图片

ConcurrentHashMap避免了对全局加锁改成了局部加锁操作，这样就极大地提高了并发环境下的操作速度，由于ConcurrentHashMap在JDK1.7和1.8中的实现非常不同，接下来我们谈谈JDK在1.7和1.8中的区别。
JDK1.7版本的CurrentHashMap的实现原理
在JDK1.7中ConcurrentHashMap采用了数组+Segment+分段锁的方式实现。
Segment(分段锁)-减少锁的粒度
ConcurrentHashMap中的分段锁称为Segment，它即类似于HashMap的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表,同时又是一个ReentrantLock（Segment继承了ReentrantLock）。
内部结构
ConcurrentHashMap使用分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。如下图是ConcurrentHashMap的内部结构图：

文章图片

从上面的结构我们可以了解到，ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。
第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。
该结构的优劣势
坏处是这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长。
好处是写操作的时候可以只对元素所在的Segment进行加锁即可，不会影响到其他的Segment，这样，在最理想的情况下，ConcurrentHashMap可以最高同时支持Segment数量大小的写操作（刚好这些写操作都非常平均地分布在所有的Segment上）。
所以，通过这一种结构，ConcurrentHashMap的并发能力可以大大的提高。
JDK1.8版本的CurrentHashMap的实现原理
JDK8中ConcurrentHashMap参考了JDK8 HashMap的实现，采用了数组+链表+红黑树的实现方式来设计，内部大量采用CAS操作，这里我简要介绍下CAS。
CAS是compare and swap的缩写，即我们所说的比较交换。cas是一种基于锁的操作，而且是乐观锁。在java中锁分为乐观锁和悲观锁。悲观锁是将资源锁住，等一个之前获得锁的线程释放锁之后，下一个线程才可以访问。而乐观锁采取了一种宽泛的态度，通过某种方式不加锁来处理资源，比如通过给记录加version来获取数据，性能较悲观锁有很大的提高。
CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。如果内存地址里面的值和A的值是一样的，那么就将内存里面的值更新成B。CAS是通过无限循环来获取数据的，如果在第一轮循环中，a线程获取地址里面的值被b线程修改了，那么a线程需要自旋，到下次循环才有可能机会执行。
JDK8中彻底放弃了Segment转而采用的是Node，其设计思想也不再是JDK1.7中的分段锁思想。
Node：保存key，value及key的hash值的数据结构。其中value和next都用volatile修饰，保证并发的可见性。

class Node implements Map.Entry { final int hash; final K key; volatile V val; volatile Node next; //... 省略部分代码 }

Java8 ConcurrentHashMap结构基本上和Java8的HashMap一样，不过保证线程安全性。
在JDK8中ConcurrentHashMap的结构，由于引入了红黑树，使得ConcurrentHashMap的实现非常复杂，我们都知道，红黑树是一种性能非常好的二叉查找树，其查找性能为O（logN），但是其实现过程也非常复杂，而且可读性也非常差，Doug
Lea的思维能力确实不是一般人能比的，早期完全采用链表结构时Map的查找时间复杂度为O（N），JDK8中ConcurrentHashMap在链表的长度大于某个阈值的时候会将链表转换成红黑树进一步提高其查找性能。

文章图片

总结其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树。
1.数据结构：取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
2.保证线程安全机制：JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。
3.锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。
4.链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。
5.查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。
为什么 ConcurrentHashMap 的读操作不需要加锁-volatile的使用？
【java|HashMap和ConcurrentHashMap】HashMap 夺命二十一问！鸡哥都扛不住