Java8的HashMap与ConcurrentHashMap

前言

• Java8在之前的类库基础上对HashMap和ConcurrentHashMap进行了一次升级。
• Java7之前的HashMap和ConcurrentHashMap可参考：
  juejin.cn/post/692865…
• Java8的HashMap使用了红黑树存储Entry，这种近似平衡的二叉搜索树可以参考：
  juejin.cn/post/695868…
• 大体的设计思想其实和Java7之前差不太多，在这里我只记录和Java7之前的有哪些区别

一、HashMap优化

1.1 hash算法

HashMap的设计思想就是，先求key的hashcode，再用key的hashcode求数组的下标，如果存在两个数组下标相同的元素，这种现象就叫做hash碰撞，Java7用链表存储这些元素。
为了减少hash碰撞，Java8优化了计算每个元素的数组下标的算法

java7的下标算法

    /**
     * 根据key计算hashcode，计算完之后进行散列处理
     * 避免与数组长度进行或运算时，总是得到相同的值
     */
    final int hash(Object k) {
        int h = hashSeed;
//        if (0 != h && k instanceof String) {
//            return sun.misc.Hashing.stringHash32((String) k);
//        }
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
复制代码

java8的下标算法

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
复制代码

1.2 HashMap里的红黑树(Red-Black tree)

当数组里存的链表长度超过8的时候，为了更快的查找效率，会将此链表的转存为红黑树。
使数组里同hash值的元素集合，查找效率为O(logN)。

1.2.1 链表如何用红黑树替换？

根据前言，我们直到红黑树本质上是一种二叉搜索树，所以为了满足二叉搜索树的特性——每个节点的左孩子都比它小，每个右孩子都比它大，我们用key的hash值作为二叉搜索的标识，构建红黑树。
hash值大的放在右子树，hash值小的放在左子树。
这种构建方法在Java8中也同样适用于 LinkedHashMap 和 ConcurrentHashMap 。

1.3 实际的效果

1.3.1 get()方法 (hashcode散列均匀的效果)

1.3.2 get()方法 (hashcode都相同)

1.3.3 put()方法 (hashcode散列均匀的效果)

1.3.4 put()方法 (hashcode都相同)

数据来源: www.nagarro.com/en/blog/pos…

二、ConcurrentHashMap的优化

Java7之前的ConcurrentHashMap是基于Segment的分段锁，理论上最大并发度与Segment个数相等。Java8为了进一步提高并发性，使用CAS机制进行多线程数据同步处理。

2.1 同步方式

2.1.1 put操作

• 对于put操作，如果Key对应的数组元素为null，则通过CAS操作将其设置为当前值。
• 如果Key对应的数组元素（也即链表表头或者树的根元素）不为null，则对该元素使用 synchronized关键字申请锁，然后进行操作。
• 如果该put操作使得当前链表长度超过一定阈值，则将该链表转换为树，从而提高寻址效率。

2.1.2 get操作

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

static class Node<K,V> implements Map.Entry<K,V> {
  final int hash;
  final K key;
  volatile V val;
  volatile Node<K,V> next;
}
复制代码

对于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);
}
复制代码

2.2 size操作

put方法和remove方法都会通过addCount方法维护Map的size。size方法通过sumCount获取由addCount方法维护的Map的size。