HashMap与ConcurrentHashMap原理剖析

HashMap与ConcurrentHashMap原理剖析

        HashMap是基于哈希表的Map接口的实现。此实现提供所有可选的映射操作，并允许使用null值和null键。（除了不同步和允许使用null之外，HashMap类与Hashtable大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。另外，HashMap是非线程安全的，也就是说在多线程的环境下，可能会存在问题，不像Hashtable是线程安全的。

        ConcurrentHashMap结构与HashMap大致相同，为了实现线程安全，其比起HashMap的实现显得更加庞大。ConcurrentHashMap的数据结构和同步机制给自身提供了良好的多线程安全以及惊人的异步读取能力。

        相信有经验的开发者都会注意到，在项目中总是会把两者混合使用；那么到底什么是线程安全呢？这可能是很多初学者带有的疑问，难道ConcurrentHashMap能保证多个线程的更新都保留吗？所谓的线程安全并不是那么厉害的东西，其实就是利用同步机制（锁）来保证其不会有多个Put操作同时作用。其实在这一点上Hashtable已经做到了，而ConcurrentHashMap可以比Hashtable限制更少从而更加高效。接下来从他们各自的原理来剖析。

HashMap原理

        HashMap顾名思义，是由hash值来做映射的映射表<Key,Value>。

        其内部使用数组和链表的组合实现，根据Key计算出hash值来快速定位元素在数组中的下标，①数组通过地址偏移量可以直接定位到对应的元素。

        然而hash值很大，数组显然不可能太长，所有设数组的长度为length，则下标index=hash%length。

        那么问题来了，不同的hash值可能由于取余操作得到相同的index下标怎么办？这时候就轮到链表出场了，数组的每一个元素对应的不是一个真正的Value值，而是一个链表，链表中有hash、value、key成员变量。

        当Put时得到同一个index值，就在链表的表头加上Put的新节点；当Get时得到相同的index，就遍历对应链表上每一个节点的Key值，找到相同的Key即可，虽然遍历效率稍低，但是相对全部用链表要快很多。

        HaspMap结构如 图 1 所示，该HashMap中有数组a，包含a0-a15个元素，每个元素对应一个链表（部分未画出,实际上也是链表）。

图1

ConcurrentHashMap原理（只针对JDK1.8之前的版本，JDK1.8有所改变，将在后续讲解）

        ConcurrentHashMap也是由<Key,Value>表示的映射关系，其与HashMap的区别笔者总结为三点：多一个层数组；多一次取余操作；多了排它锁。

        多一层数组：

                先让我们看一下其数据结构，如 图2；其中每一个table相当于一个HashMap，将多个table组合成数组segments就是ConcurrentHashMap的结构了。

图2

        多一次取余：

                多了一层数组后，怎么通过hash值来定位到不同的链表呢？很简单，既然一次取余能定位一层数组，那么两次数组取两次余就好了。设segments长度为lengthA,table长度为lengthB；则segments的下标indexA=hash%lengthA，table的下标indexB=hash%lengthB；链表就在segments[indexA][indexB]位置上。

        排它锁：

                最后为了保证线程安全，在put操作时，先获取对应segment（segment指数组segments的一个元素）的排它锁，再对该处的table进行put操作便不存在线程安全问题；只有当多个线程企图对同一个segment进行put操作时才会存在资源竞争，因此效率也非常高，最高可支持segments.length个线程并发操作。由于get操作不需要获取锁，所以所有get都可以并发执行。

        我们不需要担心在get的时候，其他线程的put操作会改变链表结构；因为当get操作筛选到链表中的时候，put操作只是在链表头新加节点，对其他节点的结构不会有任何影响。

        注：这里只说明了put操作，remove操作和put操作大致相同。

        说明：①：数组在初始化时便分配了指定的连续内存空间，查找元素时只需要计算其相对于数组头的偏移地址即可。