并发编程源码解析（四）ConcurrentHashMap源码解析之一基础概念介绍以及散列算法讲解

一、ConcurrentHashMap基本介绍

1.1 ConcurrentHashMap是什么？

        ConcurrentHashMap是Java中的一个线程安全的哈希表实现，位于java.util.concurrent包下。它实现了ConcurrentMap接口，是Map的线程安全实现之一。与HashMap相比，ConcurrentHashMap允许多个线程同时读取和写入，而不需要显式的同步措施。

1.2 ConcurrentHashMap的结构

ConcurrentHashMap 采用的是 数组 + 链表 + 红黑树 的数据接口。以下的网图。 

具体的流程就是计算出HashCode值之后会与 size - 1 的进行或运算，得到的数据丢入对应的桶中，当桶重复的数据数据进入桶的时候就会形成链表，当链表的长度超过8是就会变成红黑树。

1.3  ConcurrentHashMap如何保证线程安全？

使用： CAS + Synchronized

在锁进入桶的时候是采用CAS进行修改的，当挂入链表或者红黑树的时候就会使用Synchronized，因为这样只锁住了一个节点不会影响其他节点的读写，所以ConcurentHashMap速度很快。

1.4 ConcurrentHashMap 为什么扩展系数是0.75，而为什么链表长度为8才转红黑树的呢？

扩展系数是0.75的主要原因是因为，如果是扩展系数是0.5虽然可以减少hash碰撞但是空间利用太低了；如果是1,虽然可以最大程度的使用空间，但是容易出现Hash碰撞这样容易出现红黑树，红黑树的出现会影响写的速度；所以最终采用剧中的0.75。

红黑树的长度为8，是因为从泊松分布来看长度为8的hash碰撞概率极低，所以使用8也是为了降低红黑树的概率。

 二、ConcurrentHashMap的散列算法源码分析

     static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS;
    }

解释一下以上算法的意思：他是将获取到hashCode的高16位和低16进行一个异或的处理， 然后与 HASH_BITS 进行与运算；HASH_BITS 的 二进制位 0111 1111 1111 1111 1111 1111 1111 1111。

1. 为什么要把高16位和低16位进行运算呢？ 因为是为了让整个hashCode都可以参与运算，目的是为了减少hash碰撞；前面提到了 ConcurrentHashMap 的如桶规则是和size - 1做与运算，这样的话高位几乎永远都计算不到；所以把高低位做一个异或可以让这个hashCode都能参与到运算当中。
2. 为什么是使用异或呢？ 这样高低相同时才会得到一样的结果，不会像是 或 或者 且算法很容易导致一致（如高位都是0就很容易出现问题）。
3. HASH_BITS是什么呢？ 他其实是一块蒙板他的目的是为了遮住最高位的，遮住最高位的原因为了让code保持在正数，原因是因为hashCode为负数在ConcurrentHashMap中表达特别含义。（-1 表示参数以迁移， -2 表示挂载红黑树， -3索引位置已经被占，但是值还未被存入）。

三、作者的话

ConcurrentHashMap 算是我最经常使用的一个并发工具了十分好用！但是因此它里面的内容也是比较多的，我可以讲的清除却很难用文字将他表达好只能分着慢慢写出来了。