HashMap 介绍

Map 作为 java 中按 key-value 方式存储的集合框架，使用非常广泛。本文记录一下最常用的 HashMap 及线程安全的 ConcurrentHashMap 相关的知识点。

HashMap

底层通过散列表（数组+链表）实现，当链表长度超过8且 map 元素总数大于64时，将链表转为红黑树。hash 值为 hashCode 与其高16位进行异或运算是为了降低 hash 冲突。capacity 限制为2的次幂，方便-1后和 hash 值与运算直接定位元素下标。扩容时，拿 hash 值与旧容量与运算，结果为0则下标不变，结果为1则将当前下标加旧容量值作为新下标。

Java7 和 1.8的区别

发生hash冲突时，Java7 会在链表头部插入，Java8 会在链表尾部插入。
扩容后转移数据，Java7 转移前后链表顺序会倒置（高并发场景下会导致死循环），Java8 还是保持原来的顺序。
Java8中当链表长度大于8时会把链表转换成红黑树，寻址时间复杂度从O(N)变成O(log(N))，很大程度上提升了性能。

1.7操作流程图：
Java7
1.8操作流程图：
Java8

ConcurrentHashMap

Java7 的 ConcurrentHashMap

底层数据结构仍然是数组和链表。与HashMap不同的是，ConcurrentHashMap最外层不是一个大的数组，而是一个Segment的数组。每个Segment包含一个与HashMap数据结构差不多的链表数组。通过分段锁思想提高并发效率（有点类似LongAdder的做法）。整体数据结构如下图所示:
Java7数据结构图
Java7类图

初始化操作：

入参:

initialCapacity(初始化容量，默认16)
loadFactor(负载因子，默认0.75)
concurrencyLevel(并发等级，默认16)

具体操作:

计算segmentMask(段掩码，默认为15，二进制位1111)，首先计算segments数组大小(大于等于并发等级的最小二次幂),段掩码为segments.size()-1
计算segmentShift(段偏移量，默认为28)，32-sshift(计算segments数组大小时左移的次数)
计算每个segment对象中HashEntry<K,V>[]数组的大小cap=向上取整(initialCapacity/ssize)

总的来说就是通过concurrencyLevel决定分多少个片段，再结合initialCapacity决定每个片段下的链表个数。

put操作

首先根据(hash(key)>>>segmentShift)&segmentMask定位片段下标，然后加锁，再根据hash(key)&(cap-1)定位链表，后续操作类似hashMap。

get操作

get操作定位链表的方法和put一致，但是get方法没有加锁，原因是链表节点HashEntry中的变量通过volatile修饰，通过CAS完成更新操作，并且通过volatile修饰table来保证扩容时链表数组的内存可见性。

size操作

连续遍历2次Segment数组，将count的值，进行相加操作。如果遍历2次后的结果，都没有变化，那么就直接将count的和返回，如果此时发生了变化，那么就对整张hash表进行加锁处理。

Java8 的 ConcurrentHashMap

Java8 为进一步提高并发性，摒弃了分段锁的方案，而是直接使用一个大的数组。同时为了提高哈希碰撞下的寻址性能，Java 8在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为O(log(N))）。其数据结构如下图所示：
Java8数据结构图

put操作

如果key对应的数组元素(即链表表头或者树的根元素)为null，则通过CAS操作将其设置为当前值。否则对该元素使用sychronized关键字申请锁，然后进行操作。

get操作

由于数组被volatile关键字修饰，因此不用担心数组的可见性问题。对于数组元素(即链表表头或者树的根元素)的可见性由Unsafe的getObjectVolatile方法保证。同时Node实例的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;
}

size操作

put方法和remove方法都会通过addCount方法维护Map的size，维护方式类似LongAdder。size方法返回sumCount方法的值(baseCount累加cell.value)。