网站建设国家和行业标准,做阿里巴巴还是做网站好,好用的wordpress编辑器,wordpress 百科主题文章目录 1.Java 7 版本的 ConcurrentHashMap2.Java 8 版本的 ConcurrentHashMap3.分析 Java 8 版本的 ConcurrentHashMap 的重要源码3.1.Node 节点3.2.put 方法源码分析3.3.get 方法源码分析 4.对比 Java7 和 Java8 的异同和优缺点4.1.并发度4.2.保证并发安全的原理4.3.遇到 H… 文章目录 1.Java 7 版本的 ConcurrentHashMap2.Java 8 版本的 ConcurrentHashMap3.分析 Java 8 版本的 ConcurrentHashMap 的重要源码3.1.Node 节点3.2.put 方法源码分析3.3.get 方法源码分析 4.对比 Java7 和 Java8 的异同和优缺点4.1.并发度4.2.保证并发安全的原理4.3.遇到 Hash 碰撞4.4.查询时间复杂度 1.Java 7 版本的 ConcurrentHashMap
我们首先来看一下 Java 7 版本中的 ConcurrentHashMap 的结构示意图
从图中我们可以看出在 ConcurrentHashMap 内部进行了 Segment 分段 Segment 继承了ReentrantLock可以理解为一把锁各个 Segment 之间都是相互独立上锁的互不影响。相比于之前的Hashtable每次操作都需要把整个对象锁住而言大大提高了并发效率。因为它的锁与锁之间是独立的而不是整个对象只有一把锁。 每个 Segment 的底层数据结构与 HashMap 类似仍然是数组和链表组成的拉链法结构。默认有 0~15共 16 个 Segment所以最多可以同时支持 16 个线程并发操作操作分别分布在不同的 Segment 上。 16 这个默认值可以在初始化的时候设置为其他值但是一旦确认初始化以后是不可以扩容 的。
2.Java 8 版本的 ConcurrentHashMap
在 Java 8 中的示意图 图中的节点有三种类型。
第一种是最简单的空着的位置代表当前还没有元素来填充。第二种就是和 HashMap 非常类似的拉链法结构在每一个槽中会首先填入第一个节点但是后续 如果计算出相同的 Hash 值就用链表的形式往后进行延伸。第三种结构就是红黑树结构这是 Java 7 的 ConcurrentHashMap 中所没有的结构。
当第二种情况的链表长度大于某一个阈值默认为 8且同时满足一定的容量要求的时候ConcurrentHashMap 便会把这个链表从链表的形式转化为红黑树的形式目的是进一步提高它的查找性能。 红黑树是每个节点都带有颜色属性的二叉查找树颜色为红色或黑色是一种平衡二叉查找树查找效率高会自动平衡防止极端不平衡从而影响查找效率的情况发生。由于自平衡的特点即左右子树高度几乎一致所以其查找性能近似于二分查找时间复杂度是O(log(n))级别反观链表它的时间复杂度就不一样了如果发生了最坏的情况可能需要遍历整个链表才能找到目标元素时间复杂度为 O(n)远远大于红黑树的 O(log(n))尤其是在节点越来越多的情况下O(log(n))体现出的优势会更加明显。 红黑树的一些其他特点
每个节点要么是红色要么是黑色但根节点永远是黑色的。红色节点不能连续也就是说红色节点的子和父都不能是红色的。从任一节点到其每个叶子节点的路径都包含相同数量的黑色节点。
正是由于这些规则和要求的限制红黑树保证了较高的查找效率好处就是避免在极端的情况下冲突链表变得很长在查询的时 候效率会非常慢。而红黑树具有自平衡的特点所以即便是极端情况下也可以保证查询效率在O(log(n))。
3.分析 Java 8 版本的 ConcurrentHashMap 的重要源码
由于 Java 7 版本已经过时了所以我们把重点放在 Java 8 版本的源码分析上。
3.1.Node 节点
我们看看最基础的内部存储结构 Node这就是一个一个的节点如这段代码所示
static class NodeK,V implements Map.EntryK,V {final int hash;final K key;volatile V val;volatile NodeK,V next;}可以看出每个 Node里面是key-value的形式并且把 value 用 volatile 修饰以便保证可见性同时内部还有一个指向下一个节点的 next 指针方便产生链表结构。 下面我们看两个最重要、最核心的方法。
3.2.put 方法源码分析
put 方法的核心是 putVal 方法为了方便阅读我把重要步骤的解读用注释的形式补充在下面的源码中。
final V putVal(K key, V value, boolean onlyIfAbsent) {// 检查是否有空键或值if (key null || value null) throw new NullPointerException();// 计算哈希并进行扩散以避免聚集int hash spread(key.hashCode());int binCount 0;// 无限循环以处理哈希冲突和表初始化for (NodeK, V[] tab table;;) {NodeK, V f;int n, i, fh;// 检查表是否为空如果是则初始化表if (tab null || (n tab.length) 0)tab initTable();else if ((f tabAt(tab, i (n - 1) hash)) null) {// 如果桶为空请尝试原子性地添加新节点if (casTabAt(tab, i, null, new NodeK, V(hash, key, value, null)))break; // 添加到空桶时不需要锁定} else if ((fh f.hash) MOVED)// 如果桶正在转移中请协助进行转移tab helpTransfer(tab, f);else {V oldVal null;// 在桶上同步以处理并发修改synchronized (f) {if (tabAt(tab, i) f) {if (fh 0) {// 处理桶中的链表binCount 1;for (NodeK, V e f;; binCount) {K ek;if (e.hash hash ((ek e.key) key || (ek ! null key.equals(ek)))) {oldVal e.val;if (!onlyIfAbsent)e.val value;break;}NodeK, V pred e;if ((e e.next) null) {// 在链表中添加新节点pred.next new NodeK, V(hash, key, value, null);break;}}} else if (f instanceof TreeBin) {// 处理桶中的树节点NodeK, V p;binCount 2;if ((p ((TreeBinK, V) f).putTreeVal(hash, key, value)) ! null) {oldVal p.val;if (!onlyIfAbsent)p.val value;}}}}// 检查是否进行了任何修改并采取适当的操作if (binCount ! 0) {if (binCount TREEIFY_THRESHOLD)// 如果链表长度超过阈值则将链表转换为树treeifyBin(tab, i);if (oldVal ! null)// 如果存在旧值则返回旧值return oldVal;break;}}}// 更新地图中元素的计数addCount(1L, binCount);return null;
}
以下是代码的主要功能和步骤解释
参数检查 首先代码检查传入的键和值是否为null如果是则抛出NullPointerException。计算哈希 使用键的哈希码并通过spread方法对哈希码进行扩散以减少哈希冲突的可能性。循环处理 进入一个无限循环用于处理可能的哈希冲突和表的初始化。初始化表 如果哈希表为null或长度为0则通过调用initTable方法初始化哈希表。处理空桶 如果计算得到的桶是空的则尝试使用CASCompare and Swap原子操作添加新的Node节点到该桶中如果成功则退出循环。处理转移中的桶 如果当前桶的状态是MOVED正在进行桶的迁移操作则调用helpTransfer方法协助进行桶的迁移。处理非空桶 如果桶非空说明存在哈希冲突根据桶的类型链表或树采取不同的处理方式。
如果桶中是链表fh 0则使用同步块在链表中查找键值对。如果找到了相同的键更新其值否则将新的Node节点添加到链表中。如果桶中是树f instanceof TreeBin则调用putTreeVal方法在树中插入键值对。
更新计数 最后根据实际添加的节点数更新哈希表中元素的计数。返回值 如果在添加操作中替换了已存在的值返回被替换的旧值否则返回null。
3.3.get 方法源码分析
get 方法比较简单我们同样用源码注释的方式来分析一下
public V get(Object key) {// 定义局部变量NodeK, V[] tab;NodeK, V e, p;int n, eh;K ek;// 计算扩散后的哈希值int h spread(key.hashCode());// 检查哈希表是否已初始化if ((tab table) ! null (n tab.length) 0 (e tabAt(tab, (n - 1) h)) ! null) {// 遍历链表或树查找对应的键值对if ((eh e.hash) h) {// 判断第一个节点是否匹配if ((ek e.key) key || (ek ! null key.equals(ek)))return e.val; // 返回找到的值} else if (eh 0)return (p e.find(h, key)) ! null ? p.val : null; // 处理树结构// 在链表中遍历查找while ((e e.next) ! null) {if (e.hash h ((ek e.key) key || (ek ! null key.equals(ek))))return e.val; // 返回找到的值}}// 未找到匹配的键返回nullreturn null;
}
计算哈希 计算传入键的哈希值并通过spread方法进行扩散。检查表和桶 检查哈希表是否已经初始化以及哈希桶中是否存在节点。处理第一个节点 检查第一个节点是否匹配如果匹配则返回对应的值。处理树结构 如果哈希桶中是树结构则调用find方法查找匹配的键值对。遍历链表 在链表中遍历查找匹配的键值对如果找到则返回对应的值。未找到匹配 如果遍历完仍未找到匹配的键则返回null。
4.对比 Java7 和 Java8 的异同和优缺点
数据结构 Java 7 采用 Segment 分段锁来实现而 Java 8 中的 ConcurrentHashMap 使用数组 链表 红黑树。
4.1.并发度
Java 7 中每个 Segment 独立加锁最大并发个数就是 Segment 的个数默认是 16。 Java 8 中锁粒度更细理想情况下 table 数组元素的个数也就是数组长度就是其支持并 发的最大个数并发度比之前有提高。
4.2.保证并发安全的原理
Java 7 采用 Segment 分段锁来保证安全而 Segment 是继承自 ReentrantLock。 Java 8 中放弃了 Segment 的设计采用 NodeCASsynchronized 保证线程安全。
4.3.遇到 Hash 碰撞
Java 7 在 Hash 冲突时会使用拉链法也就是链表的形式。 Java 8 先使用拉链法在链表长度超过一定阈值时将链表转换为红黑树来提高查找效率。
4.4.查询时间复杂度
Java 7 遍历链表的时间复杂度是O(n)n 为链表长度。 Java 8 如果变成遍历红黑树那么时间复杂度降低为 O(log(n))n 为树的节点个数。
