put、get 等等核心方法在多线程情况下,都会出现修改的覆盖,数据不一致等等问题。比如多个线程 put 先后的问题,会导致结果覆盖,如果一个 put 一个get,也可能会因为调度问题获取到错误的结果;
多线程操作有读有写的时候,可能会出现一个典型异常:ConcurrentModificationException
另外扩容的时候,hashmap1.7 的实现还有可能出现死循环的问题。
关于线程安全的哈希映射的选择有三种:
Hashtable;
SynchronizedMap对HashMap包装;
ConcurrentHashMap
其中,Hashtable 的效率比较低,因为他的每一个方法都是用了锁,synchronized 修饰的;
用 SynchronizedMap 对 HashMap 包装的实质也是额外加入一个对象叫做 mutex,是一个 Object,然后给对应的方法上都加上 synchronized(mutex),当然比 Hashtable 是要好一些的,因为锁对象粒度要小一些。Hashtable 采用的 synchronized 锁上方法锁定的是整个 this。
ConcurrentHashMap则是最好的选择,这里我们来看看他的源码原理。
一、ConcurrentHashMap 数据结构其实可以想见,一个功能完全一致的容器,和原来的 HashMap 相比,肯定结构不会差到哪里去,实际上也是这样。jdk8之后 HashMap 引入红黑树的优化,ConcurrentHashMap 也有,所以我们还是分 7 和 8 来说:
1.1 jdk 7 的 ConcurrentHashMap由 Segment 片段,HashEntry组成,和HashMap一样,仍然是枚举链表。
很简单,就是 Segment 数组又分成了 HashEntry 类型的数组。
那 Segment 类型是什么呢?这个内部类维护的就是HashEntry 类型的数组。
HashEntry 是什么呢?就是链表。
所以其实首先在容器存储的核心结构上,把当时对应的 HashMap 分成了更细的粒度。
与此同时,Segment 数组是继承了 ReentrantLock 的,再往下层 HashEntry 类型的数组 table 和 HashEntry 这个链表节点都是用 volatile 修饰的。
1.2 jdk 8 的 ConcurrentHashMap显然是因为 jdk 8 的 HashMap 更新了结构,所以对应的 ConcurrentHashMap 也在这方面跟着改变了。
jdk 8 的实现已经摒弃了 Segment 的概念,而是直接用Node数组+链表+红黑树,和 HashMap 一模一样的数据结构来实现,虽然源码里还能看到Segment的数据结构,但是已经简化了属性,只是为了兼容旧版本。
对应的,不再是 Entry 而是 Node 节点,就是因为要转树,对应的方法操作,最重要的就是没有显式的再使用 ReentrantLock,用到了 synchronized 和 CAS 操作,Node 节点也是 volatile 修饰的。
二、ConcurrentHashMap 的内部方法 2.1 jdk7 的 put ,get ,扩容方法这里没有源码的截图,但是过程是清晰的。
put 方法(加锁):
将当前 Segment 中的表通过 key 的哈希码定位到HashEntry。这一步会尝试获取锁,如果获取失败肯定存在其他线程存在竞争,则利用 scanAndLockForPut() 方法去获取锁。
遍历该 HashEntry,如果不为空则判断预定的 key 和当前遍历的 key 是否替代,替代则覆盖旧的值。
不为空则需要新建一个 HashEntry 并加入到 Segment 中,同时会先判断是否需要扩容。
最后会解除在 1 中所获取当前Segment的锁。
可以看到,整体就是获取锁的中间进行 put 操作,put 操作的流程也和 HashMap 的 put 是类似的。
get 方法(不加锁):
ConcurrentHashMap 的 get 操作跟 HashMap 类似,只是ConcurrentHashMap 第一次需要经过一次 hash 定位到 Segment 的位置,然后再 hash 定位到指定的 HashEntry,遍历该 HashEntry 下的链表进行对比,成功就返回,不成功就返回 null。
并且 get 的过程调用的是 Unsafe 包的 getObjectVolatile 方法,因为具体的对象是 volatile 修饰的,不用加锁,读取也可以直接读到最新的值。
rehash 方法(加锁):
ConcurrentHashMap 的扩容方法和 HashMap 也是类似的,因为外部已经对 Segment 加锁,内部的操作就是重新计算 hash 值,然后重新移动元素。
这里可以看出来,因为有 Segment 的一个粒度缩小的优化,加上一个读写分离的普遍思想,jdk 7 实现的方法比较容易理解。
下来的 jdk 8 做出的优化非常多,因此几个方法分开来讲
2.2 jdk 8 的初始化构造方法和 HashMap 一样,是不会初始化的,而是在第一次调用 put 方法之后才会进行初始化。构造方法调用的时候只是进行了一些参数的确定。