Map

What's Map?

相关信息

Java 容器中的 Map 根接口，定义键值对方式（key-value）存储的数据结构。

特性：

• key 不能重复。
• key 重复时覆盖旧的 value.

HashMap

HashMap 是 Map 接口的具体实现类，基于哈希表。

JDK1.7 底层数据结构是数组 + 链表。

JDK1.8 底层数据结构是数组 + 链表 / 红黑树。

特性：

• 无序排列。
• 非线程安全。
• 允许 null 键和 null 值，但只能有一个 key 为 null 的节点。

JDK1.7 中在进行链表插入时，使用的是头结点插入，不用每次遍历链表的长度。缺点是在进行扩容时，进入新数组时会出现倒序的情况，在多线程时出现线程的不安全性。

JDK1.8 中在进行链表插入时，因为要进行阙值的判断（是否进行红黑树和链表的转换），每次都要遍历链表的长度，于是使用的是尾部节点插入，防止扩容时会出现倒序情况，避免了线程死锁的问题。

HashMap重要参数

• DEFAULT_INITIAL_CAPACITY：数组的初始化长度，默认值为 1 << 4.
• MAXIMUM_CAPACITY：数组的最大长度，默认值为 1 << 30.
• DEFAULT_LOAD_FACTOR：负载因子，默认值为 0.75，当元素的总个数 > 当前数组的长度 * 负载因子，数组扩容为原来的两倍。
• TREEIFY_THRESHOLD：链表树化阙值，默认值为 8，表示在一个 node 节点下的值的个数大于 8 时候，会将链表转换成为红黑树。
• UNTREEIFY_THRESHOLD：红黑树链化阙值，默认值为 6，表示在进行扩容期间，单个 Node 节点下的红黑树节点的个数小于 6 时，会将红黑树转化成为链表。
• MIN_TREEIFY_CAPACITY：最小树化阈值，默认值为 64，当数组元素超过改值，才会进行树化（防止前期阶段频繁扩容和树化过程冲突）。

put()的工作流程

1. 首先根据 key 的值计算 hash 值，找到该元素在数组中存储的下标。
2. 如果数组为空，则调用 resize 进行初始化，如果没有哈希冲突直接放在对应的数组下标里。
3. 如果冲突，且 key 已存在，则覆盖掉 value.
4. 如果冲突后，该节点是红黑树，就将这个节点挂在树上。
5. 如果冲突后，该节点是是链表，判断该链表是否大于 8 ，如果大于 8 并且数组容量小于 64，进行扩容。
6. 如果链表长度大于 8 并且数组的容量大于等于 64，则将这个结构转换为红黑树；否则，链表插入键值对，若 key 存在，就覆盖掉 value.

HashTable

HashTable 是基于哈希表的 Map 接口的具体实现类。

其使用 synchronized 关键字对 put 等操作进行加锁。

特性：

• 线程安全，所有公共的方法都使用了 synchronized 关键字。
• key、value值均不可为 null，设计如此。

TreeMap

TreeMap 是基于红黑树实现的 Map 接口的具体实现类，是一个有序的 Map 集合，进行插入操作比较复杂，不适合频繁修改的场景。

特性：

• 元素根据 key 按自然排序规则或自定义规则顺序排列。
• 线程不安全。
• 不允许 null 键，允许 null 值，因为 TreeMap 的 put 方法会根据 key 排列，调用 compareTo 方法，key 为 null 时则报空指针错误。

LinkedHashMap

LinkedHashMap 具体实现了 Map 接口，继承自 HashMap 类，底层数据结构使用双向链表和哈希表，双向链表决定了内部的键值对的迭代顺序，保存了键值对被插入哈希表的顺序。

特性：

• 元素按输入顺序排列。
• key、value 允许 null 值，底层数据结构是双向链表，空键值不影响。
• 线程不安全。

ConCurrentHashMap

ConCurrentHashMap 是 Map 接口的具体实现类，底层数据结构是双数组加链表，为了解决 HashMap 线程不安全，而 HashTable 效率低下。

JDK1.5 ~ 1.7中使用了分段锁机制实现： ConcurrentHashMap 由一个个 Segment 数组组成，Segment 将整个 Hash 表划分为多个分段，每个 Segment 类似一个 HashTable。

在执行 put 操作时首先根据 hash 算法定位到元素属于哪个 Segment，然后对该 Segment 加锁。

Segment 通过继承 ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 Segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全。

concurrencyLevel 参数默认是 16，就是有 16 个 Segments，理论上最多可以同时支持 16 个线程并发写，只要操作分别分布在不同的 Segment 上。这个值可以在初始化的时候设置为其他值，但是一旦初始化以后，它是不可以扩容的。

在 JDK1.8 中 ConcurrentHashMap 的实现原理摒弃了这种设计，选择了与 HashMap 类似的数组 + 链表 + 红黑树的方式实现，而加锁则采用 CAS 和 synchronized 实现。