摘要：中的使用及在中的冲突方案引言简称是在作为的替代选择新引入的，是包的重要成员。为了解决在频繁冲突时性能降低的问题，中使用平衡树来替代链表存储冲突的元素。目前，只有和会在频繁冲突的情况下使用平衡树。
java中ConcurrentHashMap的使用及在Java 8中的冲突方案 1、引言
ConcurrentHashMap(简称CHM)是在Java 1.5作为Hashtable的替代选择新引入的，是concurrent包的重要成员。在Java 1.5之前，如果想要实现一个可以在多线程和并发的程序中安全使用的Map,只能在HashTable和synchronized Map中选择，因为HashMap并不是线程安全的。但再引入了CHM之后，我们有了更好的选择。CHM不但是线程安全的，而且比HashTable和synchronizedMap的性能要好。相对于HashTable和synchronizedMap锁住了整个Map，CHM只锁住部分Map。CHM允许并发的读操作，同时通过同步锁在写操作时保持数据完整性。在这篇博客中我将介绍以下几点：
CHM在Java中如何实现的
什么情况下应该使用CHM
在Java中使用CHM的例子
CHM的一些重要特性
2、Java中ConcurrentHashMap的实现CHM引入了分割，并提供了HashTable支持的所有的功能。在CHM中，支持多线程对Map做读操作，并且不需要任何的blocking。这得益于CHM将Map分割成了不同的部分，在执行更新操作时只锁住一部分。根据默认的并发级别(concurrency level)，Map被分割成16个部分，并且由不同的锁控制。这意味着，同时最多可以有16个写线程操作Map。试想一下，由只能一个线程进入变成同时可由16个写线程同时进入(读线程几乎不受限制)，性能的提升是显而易见的。但由于一些更新操作，如put(),remove(),putAll(),clear()只锁住操作的部分，所以在检索操作不能保证返回的是最新的结果。
另一个重要点是在迭代遍历CHM时，keySet返回的iterator是弱一致和fail-safe的，可能不会返回某些最近的改变，并且在遍历过程中，如果已经遍历的数组上的内容变化了，不会抛出ConcurrentModificationExceptoin的异常。
CHM默认的并发级别是16，但可以在创建CHM时通过构造函数改变。毫无疑问，并发级别代表着并发执行更新操作的数目，所以如果只有很少的线程会更新Map，那么建议设置一个低的并发级别。另外，CHM还使用了ReentrantLock来对segments加锁。
3、Java中ConcurrentHashMap putifAbsent方法的例子很多时候我们希望在元素不存在时插入元素，我们一般会像下面那样写代码
synchronized(map){
if (map.get(key) == null){
return map.put(key, value);
} else{
return map.get(key);
}
}
上面这段代码在HashMap和HashTable中是好用的，但在CHM中是有出错的风险的。这是因为CHM在put操作时并没有对整个Map加锁，所以一个线程正在put(k,v)的时候，另一个线程调用get(k)会得到null，这就会造成一个线程put的值会被另一个线程put的值所覆盖。当然，你可以将代码封装到synchronized代码块中，这样虽然线程安全了，但会使你的代码变成了单线程。CHM提供的putIfAbsent(key,value)方法原子性的实现了同样的功能，同时避免了上面的线程竞争的风险。
4、什么时候使用ConcurrentHashMapCHM适用于读者数量超过写者时，当写者数量大于等于读者时，CHM的性能是低于Hashtable和synchronized Map的。这是因为当锁住了整个Map时，读操作要等待对同一部分执行写操作的线程结束。CHM适用于做cache,在程序启动时初始化，之后可以被多个请求线程访问。正如Javadoc说明的那样，CHM是HashTable一个很好的替代，但要记住，CHM的比HashTable的同步性稍弱。
5、使用小结现在我们知道了什么是ConcurrentHashMap和什么时候该用ConcurrentHashMap，下面我们来复习一下CHM的一些关键点。
CHM允许并发的读和线程安全的更新操作
在执行写操作时，CHM只锁住部分的Map
并发的更新是通过内部根据并发级别将Map分割成小部分实现的
高的并发级别会造成时间和空间的浪费，低的并发级别在写线程多时会引起线程间的竞争
CHM的所有操作都是线程安全
CHM返回的迭代器是弱一致性，fail-safe并且不会抛出ConcurrentModificationException异常
CHM不允许null的键值
可以使用CHM代替HashTable，但要记住CHM不会锁住整个Map
以上就是Java中CHM的实现和使用场景，下面做进一步深入探究。
6、冲突解决方案在Java 8 之前，HashMap和其他基于map的类都是通过链地址法解决冲突，它们使用单向链表来存储相同索引值的元素。在最坏的情况下，这种方式会将HashMap的get方法的性能从O(1)降低到O(n)。为了解决在频繁冲突时hashmap性能降低的问题，Java 8中使用平衡树来替代链表存储冲突的元素。这意味着我们可以将最坏情况下的性能从O(n)提高到O(logn)。
在Java 8中使用常量TREEIFY_THRESHOLD来控制是否切换到平衡树来存储。目前，这个常量值是8，这意味着当有超过8个元素的索引一样时，HashMap会使用树来存储它们。
这一改变是为了继续优化常用类。大家可能还记得在Java 7中为了优化常用类对ArrayList和HashMap采用了延迟加载的机制，在有元素加入之前不会分配内存，这会减少空的链表和HashMap占用的内存。
这一动态的特性使得HashMap一开始使用链表，并在冲突的元素数量超过指定值时用平衡二叉树替换链表。不过这一特性在所有基于hash table的类中并没有，例如Hashtable和WeakHashMap。
目前，只有ConcurrentHashMap,LinkedHashMap和HashMap会在频繁冲突的情况下使用平衡树。
7、什么时候会产生冲突HashMap中调用hashCode()方法来计算hashCode。
由于在Java中两个不同的对象可能有一样的hashCode,所以不同的键可能有一样hashCode，从而导致冲突的产生。
HashMap在处理冲突时使用链表存储相同索引的元素。
从Java 8开始，HashMap，ConcurrentHashMap和LinkedHashMap在处理频繁冲突时将使用平衡树来代替链表，当同一hash桶中的元素数量超过特定的值便会由链表切换到平衡树，这会将get()方法的性能从O(n)提高到O(logn)。
当从链表切换到平衡树时，HashMap迭代的顺序将会改变。不过这并不会造成什么问题，因为HashMap并没有对迭代的顺序提供任何保证。
从Java 1中就存在的Hashtable类为了保证迭代顺序不变，即便在频繁冲突的情况下也不会使用平衡树。这一决定是为了不破坏某些较老的需要依赖于Hashtable迭代顺序的Java应用。
除了Hashtable之外，WeakHashMap和IdentityHashMap也不会在频繁冲突的情况下使用平衡树。
使用HashMap之所以会产生冲突是因为使用了键对象的hashCode()方法，而equals()和hashCode()方法不保证不同对象的hashCode是不同的。需要记住的是，相同对象的hashCode一定是相同的，但相同的hashCode不一定是相同的对象。
在HashTable和HashMap中，冲突的产生是由于不同对象的hashCode()方法返回了一样的值。
以上就是Java中HashMap如何处理冲突。这种方法被称为链地址法，因为使用链表存储同一桶内的元素。通常情况HashMap，HashSet，LinkedHashSet，LinkedHashMap，ConcurrentHashMap，HashTable，IdentityHashMap和WeakHashMap均采用这种方法处理冲突。
从JDK 8开始，HashMap，LinkedHashMap和ConcurrentHashMap为了提升性能，在频繁冲突的时候使用平衡树来替代链表。因为HashSet内部使用了HashMap，LinkedHashSet内部使用了LinkedHashMap，所以他们的性能也会得到提升。
http://javarevisited.blogspot.com/2013/02/concurrenthashmap-in-java-example-tutorial-working.html
http://javarevisited.blogspot.jp/2016/01/how-does-java-hashmap-or-linkedhahsmap-handles.html
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/65109.html
摘要：若遇到哈希冲突，则将冲突的值加到链表中即可。之后相比于之前的版本，之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值默认为时，将链表转化为红黑树，以减少搜索时间。有序，唯一红黑树自平衡的排序二叉树。 本文是最最最常见Java面试题总结系列第三周的文章。主要内容： Arraylist 与 LinkedList 异同 ArrayList 与 Vector 区别 HashMap的底层...
摘要：与中的类似，也是一个数组加链表，不过这个线程安全。线程安全，但是它的线程安全是依赖将所有修改的代码块都用修饰。这是中实现线程安全的思路，由个组成，每个就相当于一个数组链表。线程安全，但性能差，不推荐使用。 问题描述 翻翻别人的面试经历 这里在知乎上看到的，分享出了自己面试阿里Java岗的面试题。 showImg(https://segmentfault.com/img/bVbfSZ5?...
摘要：一同步容器常用的一些容器例如都不是线程安全的，最简单的将这些容器变为线程安全的方式，是给这些容器所有的方法都加上关键字。为了降低哈希冲突的成本，在链表长度超过时，将链表转换为红黑树。 一、同步容器 常用的一些容器例如 ArrayList、HashMap、都不是线程安全的，最简单的将这些容器变为线程安全的方式，是给这些容器所有的方法都加上 synchronized 关键字。 Java 的...
摘要：需要注意的是所链接的是一颗红黑树，红黑树的结点用表示，所以中实际上一共有五种不同类型的结点。时不再延续，转而直接对每个桶加锁，并用红黑树链接冲突结点。 showImg(https://segmentfault.com/img/bVbfTCY?w=1920&h=1080); 本文首发于一世流云专栏：https://segmentfault.com/blog... 一、Concurren...
阅读 2790·2021-11-25 09:43
阅读 1315·2021-11-24 11:15
阅读 2179·2021-11-22 15:25
阅读 3331·2021-11-11 16:55
阅读 3018·2021-11-04 16:10
阅读 2624·2021-09-14 18:02
阅读 1495·2021-09-10 10:50
阅读 889·2019-08-29 15:39
