细说 Java 集合之 Map

前言：本文基于JDK8

一、HashMap

1.1、hash方法

hash方法是map中的基石，后续很多操作都依赖hash方法；

下面是 jdk 7 中 hash方法，注意hashSeed 这个扰动因子，该值随机，所以同一个 key 每次调用hash方法后得到的hash值都不一样。

• 该值存在就是为了增加随机性，避免链表过长，性能急剧下降；
• jdk 8 中 hash方法移除了扰动因子，因为底层数据结构链表过长的情况下会进行转换为红黑树来提升性能；

// jdk 7
final int hash(Object k) {int h = hashSeed; // 扰动因子if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h ^= k.hashCode();// 扰动因子 参与 hash 计算// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);
}

1.2、put方法

1.3、putVal方法

其中( n - 1 ) & hash是对 hash % n（n 是 2 的幂次方）的性能优化。

HashMap数组长度都是2的幂次方，就是为了方便上述操作，提高处理效率。

注意上图中操作：数组位置 i 空闲时，直接存入节点，多线程情况下会导致元素丢失，所以putVal方法线程不安全。

上图提到了采用拉链法解决hash冲突，下面来看下具体内容：

链表尾插法

JDK 7 时，采用的是头插法，即下一个冲突的键值对会放在上一个键值对的前面。扩容的时候就有可能导致出现环形链表，造成死循环。

注意链表转化为红黑树阈值TREEIFY_THRESHOLD 为 8；

TREEIFY_THRESHOLD - 1的值为 7

• 为何减1：
  插入新节点时，binCount表示插入前的链表长度。
  例如：
  插入第8个节点时，插入前链表长度为7（binCount=7），满足条件7 >= 7，触发树化。
  插入完成后，链表实际长度为8，此时已超过阈值，需转换为红黑树。

jdk 7 拉链法只有链表，并无红黑树处理逻辑。

1.4、方法treeifyBin

数组长度小于64时采用扩容数组来减少hash冲突；否则转换为红黑树；

1.5、扩容resize

重点关注迁移数组链表（红黑树同理，不再赘述）中元素：
之所以可以达到迁移前后数组位置的上述变化，奥秘就在于：

• 数组长度为2的 n 次幂；
• key 的 hash 值固定；
  

1.6、get方法

1.7、getNode方法

1.8、节点

1.8.1、Node

1.8.2、TreeNode

LinkedHashMap.Entry在HashMap.Node基础上扩展了before和after指针，形成双向链表以维护插入/访问顺序。而TreeNode继承它后，天然具备了维护双向链表的能力。这种设计允许在树化（链表转红黑树）和反树化（红黑树转链表）时，快速重构链表结构，避免重新遍历节点。

1.9、小节

• JDK1.8 HashMap 结构为：数组+链表/红黑树；
• 数组长度为2的 n 次幂，方便用位运算快速计算数组下标；
• 链表转换为红黑树前提2个：
  • 链表长度达到8个；
  • 数组长度达到64；
• 数组扩容后，链表元素（红黑树一样）分为2个链表：
  • 一个链表位置在新老数组中下标一样；
  • 另外一个位置为旧数组位置+ 旧数组长度；
  • 计算时通过hash值 与旧数组长度进行位与（&）操作来区分；
  • 这种优化依赖hash值稳定不变和数组长度为2的n次幂；

二、LinkedHashMap

LinkedHashMap 继承了HashMap，增加了元素的顺序控制；

• 插入顺序；
• 访问顺序；
  • 头部最老；
  • 尾部最年轻；

2.1、HashMap 对LinkedHashMap支持：

HashMap 中添加了一系列钩子方法，来支持LinkedHashMap。

2.2、get方法

2.3、afterNodeAccess方法

• 开启访问顺序控制时，将访问节点移动到链表尾部；
• 迭代访问LinkedHashMap时，后输出的元素最近被访问过；

2.4、removeEldestEntry方法

• 是否移除最老元素；
• 当访问顺序标识开启，同时覆写此方法，如下图注释，即可实现简易版LRU(Least Recently Used，最近最少使用)

• 通过 LinkedHashMap实现LRU

// 自定义 LinkedHashMap，限制最大容量并开启淘汰逻辑
public class LRUCache<K,V> extends LinkedHashMap<K,V> {private final int maxCapacity;public LRUCache(int maxCapacity) {super(maxCapacity, 0.75f, true); // accessOrder=true 维护访问顺序this.maxCapacity = maxCapacity;}@Overrideprotected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return size() > maxCapacity; // 超过容量时移除最久未访问的节点}
}

2.5、afterNodeInsertion方法

LRU中移除最老元素就是此方法做的。

该钩子方法在HashMap中putVal方法结束前会调用；

其中的removeNode方法是HashMap中的方法，该方法结束前会调用钩子方法afterNodeRemoval，详见2.6小节。

2.6、afterNodeRemoval方法

双向链表删除节点

三、ConcurrentHashMap

相对于 HashMap，ConcurrentHashMap 就是线程安全的 map，其中利用了锁分段的思想大大提高了并发的效率。

ConcurrentHashMap中与HashMap中一致的内容不再赘述。

1.8 版本舍弃了 1.7中的 segment，使用了 synchronized 和 CAS 无锁操作来保证 ConcurrentHashMap 的线程安全。

• 为什么不用 ReentrantLock 而是 synchronzied 呢？

实际上，synchronzied 做了很多的优化（包括偏向锁、轻量级锁、重量级锁），synchronized 相较于 ReentrantLock 的性能其实差不多。

3.1、hash方法

ConcurrentHashMap 中hash方法名变为spread，与HashMap相比，增加了将hash值变为正数（严谨点，非负数）的操作。

hash值为非负数是为了配合3.2小节中的辅助节点。

• key 不允许为 null，所以这里没有必要判空；

3.2、节点

ConcurrentHashMap 中5种节点分为两类：

• 数据节点（hash值为非负数，通过方法spread计算）：
  • Node：链表节点；
  • TreeNode：红黑树节点；
• 辅助节点（不存放数据，hash值固定，且均为负数）：
  • TreeBin：用于指向红黑树根节点，hash值为-2；
  • ForwardingNode：数组扩容时使用，hash值为-1；
  • ReservationNode：占位节点，hash值为-3，方法computeIfAbsent 和 compute中使用该节点。

3.2.1、Node

3.2.2、TreeNode

3.2.3、TreeBin

该节点hash值固定为TREEBIN = -2

3.2.4、ForwardingNode

• 注意，构造方法中MOVED是该节点的hash值，固定为 -1
• 成员变量nextTable就是扩容过程中，用于指向新的数组位置。

3.2.5、ReservationNode

注意，构造方法中RESERVED是该节点的hash值，固定为 -3

该节点使用详见3.6小节

3.3、put方法

为啥不允许key 、value 为null ?

多线程环境下的歧义性问题：

• HashMap中允许，当get(key) 返回null 时，单线程情况下：
  • 通过containskey(key) 可以确认key是否存在，即 key 不存在，所以value返回null； 或key存在，value就是null；
• ConcurrentHashMap中不允许，它是面向多线程的，当get(key) 返回null 时：
  • 通过containskey(key) 无法确认key一开始是否存在？
    • 线程A执行get(key) 返回null；
    • 线程B执行put(key)设置，key = null或者删除了key；
    • 线程A执行containskey(key) 返回啥；问题来了，key一开始不存在(对于A就应该返回false)，后面被B设置了，实际返回true；或者一开始存在（对于A就应该返回true），value就是null，后面被B删除了，实际返回false；这key一开始到底存不存在？已经产生歧义了。
  • 为了避免歧义，ConcurrentHashMap直接禁止key、value为null的情况。

3.4、putVal方法

注意比HashMap中的putVal方法多了的循环是为了配合CAS操作。

CAS 一般都会伴随自旋操作，具体细节参阅 自旋、CLH、AQS浅析;

• 拉链法解决hash冲突，链表尾插法插入（链表长度超过8，尝试转换为红黑树）或者红黑树插入；
  • 链表尝试转换为红黑树时，和HashMap一致，数组长度小于64时，首选扩容；否则，转换。
• 解决冲突时，使用内置锁synchronized，锁的对象时数组 i 位置的节点，锁的粒度就是1个节点。
  • jdk 7 使用 ReentrantLock，锁的对象是segment，包含数组相邻位置多个节点。
  • 为了避免浪费空间去为每一个数组桶关联一个锁对象，所以使用数组桶中第一个元素作为一把锁。
• 注意下图判断链表和红黑树的判断方法
  • hash 值（下图变量fh）>=0 是链表；因为红黑树的根节点被节点TreeBin（hash值固定为 -2）指着。

3.5、get方法

注意上图红黑树查找时，如遇到数组正在扩容时，会先找到ForwardingNode节点，通过ForwardingNode找到扩容后的新数组，在新数组中查找(类似递归了)。

3.6、computeIfAbsent方法

我们只关注key不存在的情况，数组对应位置（记为 i ）元素为null，线程A、B同时执行此逻辑：

• 新建占位节点ReservationNode，记为 r, 通过CAS操作将占位节点设置设置到 数组i;
• 既然CAS，就会有失败的可能，所以外侧通过循环来自旋；
• CAS成功了，占位节点就会设置到数组 i 位置；后续就可以break，退出循环；
• CAS失败了，进入下次循环，注意下次循环进来后，不会再次进入CAS逻辑了；
  • CAS失败意味着数组位置 i 元素（图示f） ！= null，因为被别的线程设置了；
• 下次循环会进入图示下方的同步代码块，此处加锁的对象是f;
  • 此处加锁应该没有疑问，就是防止链表修改并发产生错误；

问题来了：占位节点r 作用域就在else if这个代码块，每个线程执行时创建的r都不同，为啥对r加锁？

加锁一定有并发场景，问题是此处r 会有其它线程来争抢吗？

• 回到上面CAS失败的情况，假设线程A CAS失败，线程B CAS成功；
  • 线程B CAS成功意味着：线程B之前对自己创建的r加锁成功了；
• 线程A 会进入下次循环，走到图示下方的同步代码块；
  • 此时，线程B还在图示上方同步块中执行；
  • 那线程A此时读到的对象是f就是线程B创建的r了，即f == r;
  • 线程A无法加锁成功，进入阻塞状态；
  • 因为占位节点r时临时节点，最终会被线程B替换为真正的节点Node;

综上，占位节点ReservationNode 和真正的节点替换作为一个原子操作，是不可以分开的，所以此处必须对占位节点ReservationNode 进行加锁。

四、TreeMap

TreeMap可以保持元素的自然顺序，所以使用时需要提供排序器或将key实现排序接口。

4.1、树节点Entry

• TreeMap中的Tree是红黑树；
• 时间复杂度O(log n);

4.2、put方法

4.3、get方法

4.4、getEntry方法