JAVA HashMap与ConcurrentHashMap

java

HashMap

Fast-Fail(遍历时写入操作异常)

在使用迭代器的过程中如果HashMap被修改,那么ConcurrentModificationException将被抛出,也即Fast-fail策略。

当HashMap的iterator()方法被调用时,会构造并返回一个新的EntryIterator对象,并将EntryIterator的expectedModCount设置为HashMap的modCount(该变量记录了HashMap被修改的次数)。

HashIterator() {

expectedModCount = modCount;

if (size > 0) { // advance to first entry

Entry[] t = table;

while (index < t.length && (next = t[index++]) == null)

;

}

}

在通过该Iterator的next方法访问下一个Entry时,它会先检查自己的expectedModCount与HashMap的modCount是否相等,如果不相等,说明HashMap被修改,直接抛出ConcurrentModificationException。该Iterator的remove方法也会做类似的检查。该异常的抛出意在提醒用户及早意识到线程安全问题。

tableSizeFor方法

tableSizeFor的功能是返回大于输入参数且最近的2的整数次幂的数。比如10,则返回16。

   static final int tableSizeFor(int cap) {

int n = cap - 1;

n |= n >>> 1;

n |= n >>> 2;

n |= n >>> 4;

n |= n >>> 8;

n |= n >>> 16;

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

}

    static final int MAXIMUM_CAPACITY = 1 << 30;

再次分析问什么减一

  int n = cap - 1;

让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000,十进制数值为8。如果不对它减1而直接操作,将得到答案10000,即16。显然不是结果。减1后二进制为111,再进行操作则会得到原来的数值1000,即8。

HashMap里的MAXIMUM_CAPACITY是230。我结合tableSizeFor()的实现,猜测设置原因如下:

int的正数最大可达231-1,而没办法取到231。所以容量也无法达到231。又需要让容量满足2的幂次。所以设置为230

hash方法

    static final int hash(Object key) {

int h;

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

从上面的代码可以看到key的hash值的计算方法。key的hash值高16位不变,低16位与高16位异或作为key的最终hash值。(h >>> 16,表示无符号右移16位,高位补0,任何数跟0异或都是其本身,因此key的hash值高16位不变。)

为什么要这么干呢?

这个与HashMap中table下标的计算有关。

n = table.length;

index = (n-1) & hash;

因为,table的长度都是2的幂,因此index仅与hash值的低n位有关(此n非table.leng,而是2的幂指数),hash值的高位都被与操作置为0了。

假设table.length=24=16。

由上图可以看到,只有hash值的低4位参与了运算。

这样做很容易产生碰撞。设计者权衡了speed, utility, and quality,将高16位与低16位异或来减少这种影响。设计者考虑到现在的hashCode分布的已经很不错了,而且当发生较大碰撞时也用树形存储降低了冲突。仅仅异或一下,既减少了系统的开销,也不会造成的因为高位没有参与下标的计算(table长度比较小时),从而引起的碰撞。

ConcurrentHashMap

JDK7中处理

Segment继承自ReentrantLock,所以我们可以很方便的对每一个Segment上锁。

读操作(get)

对于读操作,获取Key所在的Segment时,需要保证可见性(请参考如何保证多线程条件下的可见性)。具体实现上可以使用volatile关键字,也可使用锁。但使用锁开销太大,而使用volatile时每次写操作都会让所有CPU内缓存无效,也有一定开销。ConcurrentHashMap使用如下方法保证可见性,取得最新的Segment。

Segment<K,V> s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)

获取Segment中的HashEntry时也使用了类似方法

HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile

(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE)

写操作(put,remove)

写操作,并不要求同时获取所有Segment的锁,因为那样相当于锁住了整个Map。它会先获取该Key-Value对所在的Segment的锁,获取成功后就可以像操作一个普通的HashMap一样操作该Segment,并保证该Segment的安全性。

同时由于其它Segment的锁并未被获取,因此理论上可支持concurrencyLevel(等于Segment的个数)个线程安全的并发读写。

获取锁时,并不直接使用lock来获取,因为该方法获取锁失败时会挂起(参考可重入锁)。事实上,它使用了自旋锁,如果tryLock获取锁失败,说明锁被其它线程占用,此时通过循环再次以tryLock的方式申请锁。如果在循环过程中该Key所对应的链表头被修改,则重置retry次数。如果retry次数超过一定值,则使用lock方法申请锁。

这里使用自旋锁是因为自旋锁的效率比较高,但是它消耗CPU资源比较多,因此在自旋次数超过阈值时切换为互斥锁。

JDK8处理

可见性,查看node源码:

static class Node<K,V> implements Map.Entry<K,V> {

final int hash;

final K key;

volatile V val;

volatile Node<K,V> next;

}

读操作,由于数组被volatile关键字修饰,因此不用担心数组的可见性问题。同时每个元素是一个Node实例(Java 7中每个元素是一个HashEntry),它的Key值和hash值都由final修饰,不可变更,无须关心它们被修改后的可见性问题。而其Value及对下一个元素的引用由volatile修饰,可见性也有保障。

对于Key对应的数组元素的可见性,由Unsafe的getObjectVolatile方法保证。

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {

return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);

}

总结

HashMap在JDK8与JDK7中的区别

  • 插入数据时,hash冲突,jdk7总是把数据插入到链表的头部,jdk8要先判断node是红黑树,还是链表,如果是链表,长度超过8也要转换成红黑树,链表的话,插入到链表尾部,如果是remove数据,红黑树长度小于6也会转换成链表。
  • 扩容resize时,jdk7的扩容,按旧链表正序遍历,在新链表的头部依次插入,在多线程的情况下,有一定概率会出现链表环,出现死锁。jdk8扩容,按旧链表正序遍历,在新链表尾部依次插入,不会出现jdk7中的链表环,但在多线程的情况下有一定概率出现脏数据,数据丢失问题。

ConcurrentHashMap在JDK7与JDK8中的区别

  • ConcurrentHashMap在jdk8中初始化采用了延迟初始化策略,他会在第一次执行put的时候初始化table。

  • JDK7采用segment的分段锁机制实现线程安全,其中segment继承自ReentrantLock。JDK8采用CAS(读)+Synchronized(写)保证线程安全。

  • 锁的粒度:原来是对需要进行数据操作的Segment加锁,JDK8调整为对每个数组元素加锁(Node)。

  • 链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时,会将链表转化为红黑树进行存储。

  • 查询时间复杂度:从原来的遍历链表O(n),变成遍历红黑树O(logN)。

  • JDK8推荐使用mappingCount方法而不是size方法获取当前map表的大小,因为这个方法的返回值是long类型,size方法是返回值类型是int

ConcurrentHashMap与HashMap相比,有以下不同点

  • ConcurrentHashMap线程安全,而HashMap非线程安全
  • HashMap允许Key和Value为null,而ConcurrentHashMap不允许
  • HashMap迭代器是强一致性,ConcurrentHashMap迭代器是弱一致性,HashMap不允许通过Iterator遍历的同时通过HashMap修改,而ConcurrentHashMap允许该行为,并且该更新对后续的遍历可见。

参考:

Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析

Java进阶(六)从ConcurrentHashMap的演进看Java多线程核心技术

Java8的HashMap详解(存储结构,功能实现,扩容优化,线程安全,遍历方法)

Java8 HashMap源码阅读

Java进阶(六)从ConcurrentHashMap的演进看Java多线程核心技术

Java集合类框架学习 5.3—— ConcurrentHashMap(JDK1.8)

以上是 JAVA HashMap与ConcurrentHashMap 的全部内容, 来源链接: utcz.com/z/393790.html

回到顶部