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操作流程图:
1.8操作流程图:
ConcurrentHashMap
Java7 的 ConcurrentHashMap
底层数据结构仍然是数组和链表。与HashMap不同的是,ConcurrentHashMap最外层不是一个大的数组,而是一个Segment的数组。每个Segment包含一个与HashMap数据结构差不多的链表数组。通过分段锁思想提高并发效率(有点类似LongAdder的做法)。整体数据结构如下图所示:
初始化操作:
入参:
- 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)))。其数据结构如下图所示:
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)。