dslztx
0%

并发Map

发表于 更新于 专题于 ， ， Disqus：

本文介绍并发Map，有几点说明：

  • 其在Java容器中的划分位置见[1]
  • 根接口为Map，“键”和“键值”是否允许NULL值由具体实现子类决定
  • 根接口为Map，它不像Collection接口继承Iterable接口，故本身没有iterator()方法获取迭代器，但是通过Set<K> keySet()，Collection<V> values()和Set<Map.Entry<K, V>> entrySet()方法获取到的3个视图的类型分别为Set，Collection和Set，它们属于Collection接口体系，有iterator()方法获取迭代器（迭代器类型跟具体实现相关），这些间接的迭代器在这里不是主要矛盾，因此本文不作介绍
  • 接下来介绍其常见的三个子类：
    • Hashtable
    • SynchronizedMap
    • ConcurrentHashMap

接下来对具体实现子类的介绍，主要基于以下几个维度：

  • “键”和“键值”是否允许NULL值
  • 实现映射表的核心机制，比如“节点数组+哈希”，“树”
  • 实现操作的线程安全策略及该种线程安全策略下的并发性能

一、Hashtable

核心原理：

  • “键”和“键值”都不允许NULL值
  • 实现映射表的核心机制：基于“节点数组+哈希”
  • 使用synchronized锁实现操作的线程安全，故属于同步容器。锁粒度为“整体”，所有并发操作（比如“put”，“remove”，“get”，“size”等）都要竞争同一把锁，并发性能较差

接下来主要介绍“哈希和碰撞”和“大小”两个问题。需要说明的两点是：1）接下来的时间复杂度分析不考虑获取synchronized锁，如果考虑的话便会不可分析；2）“时间复杂度分析”跟“并发性能”属于两个维度。

1.1、哈希和碰撞

1、哈希算法

  1. 第一次哈希：键的hashCode()方法值
  2. 第二次哈希：其源代码为hash & 0x7FFFFFFF（hash为第一次哈希的结果值），其含义是：去掉最高位1，避免第三次哈希出现“负数取余操作”情形
  3. 第三次哈希：本次哈希是为了散列到槽，其计算公式为p % n[假定节点数组大小为n，经过前两次哈希的结果值为p]

2、碰撞解决策略
碰撞可通过“链地址法”解决，对应的链可称之为“碰撞冲突链”，假定链表的长度为K，此时增删改查的时间复杂度为O(K)。

1.2、大小

Hashtable涉及到两类大小：映射记录大小和节点数组大小。

1.2.1、映射记录大小

指Hashtable中映射记录数量，比如“节点数组大小为8，在且只在第3个节点（槽）有一个长度为4的链表（碰撞冲突链），则映射记录大小为4”：

  • 对应于实例成员变量private transient int count
  • 对应于实例成员方法public synchronized int size()的返回值（不考虑映射记录大小大于Integer.MAX_VALUE的情形），该方法直接返回成员变量count的值，因此时间复杂度是O(1)

1.2.2、节点数组大小

指Hashtable中节点数组大小，即成员变量 private transient Entry<?,?>[] table的大小。

接下来介绍“初始化节点数组大小”和“扩容节点数组大小”，在介绍之前首先作以下几点说明：

  • 为简化描述和便于理解，不考虑极值大小的情况，比如节点数组大小>=MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8)
  • 成员变量loadFactor的语义是：负载因子，当映射记录大小 >= 节点数组大小*loadFactor时扩容节点数组
  • 成员变量threshold的语义是：threshold=节点数组大小*loadFactor，即当映射记录大小 >= threshold时扩容节点数组
1.2.2.1、初始化

即时初始化。

1、构造方法
构造方法初始化节点数组，设置成员变量loadFactor和threshold的值，具体描述如下表。

构造方法\设置 节点数组初始化大小 loadFactor threshold
Hashtable(int initialCapacity, float loadFactor) 等于传入的initialCapacity 等于传入的loadFactor 等于initialCapacity * loadFactor
Hashtable(int initialCapacity) 等于传入的initialCapacity 等于默认的0.75f 等于initialCapacity * loadFactor
Hashtable() 等于默认的11 等于默认的0.75f 等于initialCapacity * loadFactor
Hashtable(Map<? extends K, ? extends V> t) 等于max(2*t.size(), 11) 等于默认的0.75f 等于initialCapacity * loadFactor

有一点说明：后续可知，扩容操作十分耗费性能（申请新节点数组内存资源，对原映射记录进行rehash操作），因此在创建Hashtable实例时最好能够根据预估的“映射记录大小”预计算“节点数组的初始化大小”。由于当映射记录大小 >= 节点数组大小*loadFactor时进行扩容，故为尽量避免扩容，须使得满足节点数组大小 > 映射记录大小/loadFactor不等式，上述第4个构造方法中的max(2*t.size(),11)就是在loadFactor取常见默认值0.75f情况下符合该不等式的一个等式，我们自己在创建Hashtable实例时也应该使用该等式预计算传入的节点数组初始化大小。

1.2.2.2、扩容

节点数组只有“扩容”，没有“收缩”，扩容条件为：映射记录大小 >= threshold。

扩容过程描述如下：

  • 假定节点数组原大小为N，则扩容后大小为M=N*2+1。成员变量threshold的值为M * loadFactor（语义不变）
  • 对原映射记录进行rehash操作

二、SynchronizedMap

java.util.Collections类中的内部类。

1、核心原理

  • 由所传入的Map实例，决定“键”和“键值”是否允许NULL值
  • 由所传入的Map实例，确定实现映射表的核心机制
  • 使用synchronized锁实现操作的线程安全，故属于同步容器。锁粒度为“整体”，所有并发操作（比如“put”，“remove”，“get”，“size”等）都要竞争同一把锁，并发性能较差

2、构造参数

  • Map<K,V> m：SynchronizedMap实例所基于的底层Map实例，注意其跟“初始化元素来源集合”不一样，后者在复制后就不再有关联
  • Object mutex：传入的锁对象

三、ConcurrentHashMap

详见《HashMap和ConcurrentHashMap》博文中对ConcurrentHashMap的介绍。


参考文献

[1]《Java容器》

您的支持将鼓励我继续分享！