玖叶教程网

一、数据结构

在JDK1.8之前，HashMap是基于链式哈希实现的，而在JDK1.8之后，为了提高冲突节点的访问性能，在链式哈希实现的基础上，在哈希表大小超过64时，针对冲突节点链条，如果节点数量超过8个，则升级为红黑树，小于等于6个时，则降级为链表结构。

链式哈希

• 链式哈希是一个数组结构，数组元素为链表或者红黑树。如下为HashMap的内部数据存储结构，也是链式哈希的实现。其中Node为一个key的hash值相同的数据的链表（或红黑树）的头节点，即为冲突节点的链表。

// 链式哈希表实现
transient Node<K,V>[] table;

链表节点

• 如下为链表节点的数据结构设计：包括key，value，key的hash值，当前节点在链表中的下一个节点next。
• 该链表内的所有节点的key的hash值是相同的，链表头结点存放在哈希表table中，基于hash值与table大小获取该链表头结点在table中的位置下标。

红黑树节点

• 与链表节点一样，红黑树中存放key的hash值相同的节点集合，其中红黑树根节点root存放在哈希表table中，对应的table数组下标也是基于key的hash值和数组table大小获取。

二、核心设计

table数组容量与阈值

// 数组初始大小为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 数组最大大小
static final int MAXIMUM_CAPACITY = 1 << 30;
// 负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

• DEFAULT_INITIAL_CAPACITY： table数组默认大小为16，即在应用代码中，创建一个HashMap时，不指定容量，则之后在第一次添加数据到该HashMap，首先分配一个大小为16的数组table。
• MAXIMUM_CAPACITY：数组最大大小，超过则不再进行拓容，大小为2的30次方。
• DEFAULT_LOAD_FACTOR：数组拓容阈值，即在当前数组存放的数据节点达到容量的0.75时，则进行数组拓容，具体拓容逻辑在resize方法定义。

构建红黑树阈值

• 默认哈希表对应的数组的每个元素是一个链表，具体为存放链表头节点，而在冲突节点较多时，即存在较多key的hash值相同的元素，则会导致链表过长，在应用代码中获取某个key的值value，时间复杂度就会增加，即默认的O(1)变为了O(N)，其中N为该链表长度。
• 所以为了解决这种情况下的性能问题，JDK1.8提供了从链表转为红黑树，或者从红黑树还原为链表的设计，在红黑树中获取某个节点的时间复杂度为O(logN)，具体阈值如下：

// 转为红黑树节点的阀值
static final int TREEIFY_THRESHOLD = 8;
// 转为链表节点的阀值
static final int UNTREEIFY_THRESHOLD = 6;
// 转为红黑树节点的节点个数阀值
static final int MIN_TREEIFY_CAPACITY = 64;

• TREEIFY_THRESHOLD：构造红黑树的阈值，默认为8，即链表的元素个数超过8个的时候，则将链表转为红黑树，不过前提是数组大小大于MIN_TREEIFY_CAPACITY。使用8作为阀值的原因是：红黑树的操作复杂度为O(logN)，如果是8则平均查找次数为3，如果使用链表，则平均查找次数为8/2=4，故红黑树性能更高；
• MIN_TREEIFY_CAPACITY：触发红黑树化的前提条件，默认值为64，即哈希表数组table的大小超过64的时候，如果某个数组元素对应的链表的长度超过TREEIFY_THRESHOLD，则将该数组元素（即链表头结点）对应的链表转为红黑树结构。
• UNTREEIFY_THRESHOLD：从红黑树退化为链表的条件，默认为6，即当红黑树中节点个数不超过6时，则退化为链表。使用6作为退化阀值原因是：如果使用链表，平均查找次数为6/2=3，速度也很快，如果使用树，则转为树结构和调整树也需要开销，故可以直接使用链表。中间使用7作为差值，主要是有效防止树和链表的频繁转换。

三、核心操作设计

数组大小capacity调整

• HashMap内部存储数据所用的链式哈希表是基于数组实现的，即数组 + 链表或者数组 + 红黑树，所以在往HashMap存放数据之前，需要指定数组大小来创建这个数组。
• 在存放某个数据时，需要根据该数据的key的hash值与数组大小取模，从而确定该数据所在的链表（具体为链表头结点）在数组中的位置下标。在HashMap的设计中，为了提高性能，采用的是位运算的方式，而不是使用%的方式取模，具体方式如下：

(capacity - 1) & hash

• 这种方式的实现基础为capacity的值为2的N次方，则capacity - 1的值对应二进制就全是1了，如16的二进制为：10000，15的二进制为：01111，则01111与任何数字的与运算的结果为0到15，如：

01111 & 00010 = 00010，即15与2取模等于2
01111 & 100001 = 00001，即15与33取模等于1

• 所以在指定HashMap的容量capacity时，则内部会将capacity调整为2的N次方，即调整后的capacity大于或等于应用代码指定的capacity。调整实现为：在tableSizeFor方法定义，如下：

put设值

• put操作往HashMap存放数据，在内部主要是在putVal方法定义实现逻辑。具体过程请看代码注释：

resize扩容

• resize操作主要是对哈希表数组table进行拓容或初始化，拓容为每次增大为原来的2倍，从而保证容量capacity为2的N次方的设计。
• 拓容阈值threshold：threshold = capacity * load factor，即默认为容量capacity的0.75，当存放的元素达到容量的3/4时，进行拓容resize操作。

treeifyBin构造红黑树

• 主要用来将某个数组元素对应的链表，转为红黑树结构，从而解决链表长度过长时的访问性能问题。

clear清空

• 清空HashMap，具体为将哈希表数组table的每个元素置为null，则该元素对应的链表或红黑树则没有被引用了，可以被GC回收。

哈希表节点Node集合

EntrySet：哈希表所有节点集合

• 从数组的每个元素对应的链表中取出链表节点放到该集合

keySet：哈希表key集合

• 哈希表所有节点的key集合

Values：哈希表value集合

• 哈希表所有节点的value集合

链表迭代器基类：HashIterator

• 主要被以上集合用来遍历哈希表数组，然后遍历每个数组对应的链表，从而获取所有的数据，即Node节点，然后放到集合中。
• 派生类包括：KeyIterator，ValueIterator，EntryIterator，其中下一个节点都依赖nextNode方法，从链表头结点开始，获取该链表的下一个节点。
• 迭代器是快速失败fail-fast的，即在使用过程中，如果往HashMap中添加或删除了数据，则抛异常退出。

四、线程安全

• HashMap不是线程安全的，故如果需要保证多线程访问的并发安全性，需要使用ConcurrentHashMap，或者使用Collections.synchronizedMap方法来对HashMap进行包装成类型为SynchronizedMap的，线程安全的map。
• ConcurrentHashMap主要是基于CAS来实现乐观锁来实现线程安全；
• SynchronizedMap的内部实现，主要是通过synchronized关键字结合一个对象锁mutex，来对会产生并发问题的操作，如get，put，remove，clear，contains操作进行同步操作。