HashMap 介绍

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)。