键值之道：深入学习Java中强大的HashMap（一）-阿里云开发者社区

HashMap 基于哈希表的 Map 接口实现，主要用来存放键值对数据。HashMap 不是同步的，这意味着它不是线程安全的。如果需要满足线程安全，可以用 Collections 的 synchronizedMap 方法使 HashMap 具有线程安全的能力，或者使用ConcurrentHashMap。HashMap 最多允许一条数据的键为 null，允许多条数据的值为 null。此外，HashMap 中的映射不是有序的。

JDK1.8 之前 HashMap 由数组 + 链表组成，数组是 HashMap 的主体，链表则是主要使用链地址法解决哈希冲突，即当两个对象调用的 hashCode 方法计算的哈希值经哈希函数算出来的地址被别的元素占用了。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，默认为 8 ）并且当前数组的长度大于 64 时，此时此索引位置上的所有数据改为使用红黑树存储。

HashMap 继承自 AbstractMap 抽象类，并实现了 Map、Cloneable、Serializable，可以用来存储键值对类型的数据，同时支持复制和序列化。

父类 AbstractMap

AbstractMap 提供了一套基于键值对访问的接口。通过继承此类，子类仅需实现部分代码即可拥有完整的一套访问键值对数据的接口。

**AbstractMap 只有一个抽象方法 entrySet()，其他大多方法都是调用 entrySet() 去处理数据。**所以子类继承可以把关注点放在 entrySet() 方法上，这个方法返回一个保存所有 key-value 映射的 Set。

public abstract Set<Entry<K,V>> entrySet();

如果想要实现一个可变的 Map，我们还需要重写 put() 方法，因为 AbstractMap 类中默认不支持 put 实现，子类必须重写该方法的实现，否则会抛出异常：

public V put(K key, V value) {
  throw new UnsupportedOperationException();
}

成员变量

初始化容量：16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

当我们根据 key 的 hash 确定其在数组的位置时，如果 n 为 2 的幂次方，可以保证数据的均匀插入，如果 n 不是 2 的幂次方，可能数组的一些位置永远不会插入数据，浪费数组的空间，加大 hash 冲突，降低 HashMap 的性能
一般我们可能会想通过 % 求余来确定位置，只不过性能不如 & 运算。所以 HashMap 使用后者来确定位置，而且当 n 是 2 的幂次方时：hash & (length - 1) == hash % length
HashMap 容量为 2 次幂的原因为了数据的的均匀分布，减少冲突，毕竟 hash 冲突越大，代表数组中一个链的长度越大，这样的话会降低性能
如果创建 HashMap 对象时，输入的数组长度是 10（不是 2 的幂），HashMap 通过一系列位移运算和或运算得到离初始容量最近的 2 的幂次数

最大容量：2 的 30 次幂

static final int MAXIMUM_CAPACITY = 1 << 30;

HashMap 集合最大容量的上限是：2 的 30 次幂。

默认的负载因子： 0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

链表和树相互转换阈值

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

JDK1.8 新增特性，当桶中的链表的元素个数超过 8 则会转红黑树。当桶上的结点数小于 6 时红黑树又会转换成链表。

首先我们要知道，无论是链表的结构还是红黑树的结构，都是设计者在寻找一种时间和空间的平衡。链表的查找效率为 O(n)，而红黑树的查找效率为 O(logn)，查找效率是变高了，但是插入效率变低了，如果从一开始就用红黑树并不合适。从概率学的角度选了一个合适的临界值为 8。

当元素数量为 8 的时候，红黑树的平均查找长度是 3。而链表的平均查找长度是 4，显然树要快一些，而当元素数量小于等于 6 的时候，链表的平均查找长度是 3，其实也很快，没有必要使用红黑树结构，因为转换的过程也需要一定的时间。

6 和 8 中间有个差值 7 还可以防止链表和树之间频繁的转换。

最小树形化阈值：64

static final int MIN_TREEIFY_CAPACITY = 64;

当 HashMap 桶的容量超过这个值时才能进行树形化，否则会先选择扩容，而不是树形化。为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD。

存储元素的数组

transient Node<K,V>[] table;

在 JDK1.8 中我们了解到 HashMap 是由数组加链表加红黑树来组成的结构，其中 table 就是 HashMap 中的数组，JDK1.8 之前数组类型是 Entry 类型。从 JDK1.8 之后是 Node 类型。只是换了个名字，都实现了一样的接口：Map.Entry。负责存储键值对数据的。

存放元素的个数

transient int size;

存放元素（键值对）的个数，注意这个不等于数组的长度。

统计修改次数

transient int modCount;

每次扩容和更改 map 结构的计数器。

扩容临界值用来调整大小

int threshold;

计算公式：capacity（数组长度默认16）* loadFactor（负载因子默认 0.75）。这个值是当前已占用数组长度的最大值。当 size >= threshold 的时候，就要考虑对数组进行扩容操作，临界值是衡量数组是否需要扩增的一个标准，扩容后的 HashMap 容量是之前容量的两倍。

哈希表的加载因子：0.75

final float loadFactor;

用来衡量 HashMap 满的程度，表示 HashMap 的疏密程度。loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。计算 HashMap 的实时加载因子：size / capacity。

当 HashMap 里面容纳的元素已经达到 HashMap 数组长度的 75% 时，表示 HashMap 太挤了，需要扩容，而扩容这个过程涉及到 rehash、复制数据等操作，非常消耗性能。所以开发中尽量减少扩容的次数，可以通过创建 HashMap 集合对象时指定初始容量来尽量避免。

同时在 HashMap 的构造器中可以定制 loadFactor。

/**
 * 构造一个带指定初始容量和加载因子的空 HashMap
 */
public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " +
                                       initialCapacity);
  if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
  if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " +
                                       loadFactor);
  this.loadFactor = loadFactor;
  this.threshold = tableSizeFor(initialCapacity);
}

为什么加载因子设置为 0.75，初始化临界值是 12？

loadFactor 越趋近于 1，那么数组中存放的数据也就越多，也就越密，会让链表的长度增加，降低查询效率，loadFactor 越趋近于 0，数组中存放的数据也就越少，也就越稀疏。既要兼顾数组利用率还要考虑链表元素不要太多，经过大量测试 0.75 是最佳方案。

threshold 表示扩容临界值，计算公式：capacity（数组长度默认16）* loadFactor（负载因子默认 0.75）。当 size >= threshold 的时候，就要考虑对数组进行扩容操作。所以最开始的初始化临界值是 12，临界值是衡量数组是否需要扩增的一个标准，扩容后的 HashMap 容量是之前容量的两倍。那么接下来的临界值就是 24、48、96 …

构造方法

HashMap 的构造方法主要是用于设置初始化容量和加载因子，也可以传入 Map 对数据初始化。

无参构造

public HashMap() {
  this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

使用无参构造的时候，加载因子 DEFAULT_LOAD_FACTOR 默认值为 0.75f，初始化容量 DEFAULT_INITIAL_CAPACITY 为 16。

指定初始化容量和加载因子

public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " +
                                       initialCapacity);
  if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
  if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " +
                                       loadFactor);
  this.loadFactor = loadFactor;
  this.threshold = tableSizeFor(initialCapacity);
}

默认情况下 HashMap 的容量是 16，但是，如果用户通过构造函数指定了一个数字作为容量，那么会选择大于该数字的第一个 2 的幂作为容量（3->4、7->8、9->16），即 tableSizeFor 方法的作用。

指定初始化容量

public HashMap(int initialCapacity) {
  this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

本质上使用的还是上门的构造方法，只不过是指定初始化容量，使用默认的加载因子。

传入 Map 数据进行初始化

public HashMap(Map<? extends K, ? extends V> m) {
  this.loadFactor = DEFAULT_LOAD_FACTOR;
  putMapEntries(m, false);
}

使用默认的加载因子，之后调用 putMapEntries 处理元素，循环原始 Map，不断调用 putVal 方法添加数据。

成员方法

新增元素 put

public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}

HashMap 暴露 put 方法用于添加数据，而 put 方法种实际上调用 putVal 实现添加逻辑。

首先 putVal 方法接收的第一个参数为 key 的哈希值，计算逻辑如下：

static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

如果 key 等于 null，那么返回的哈希值为 0
如果 key 不等于 null，首先调用 key 的 hashCode 方法赋值给 h，然后和 h 无符号右移 16 位后的二进制进行按位异或得到最后的 hash 值

所以从 hash 方法中可以看出，HashMap 允许其中一条数据的键为空。按位异或运算（^）：相同的二进制数位上，数字相同，结果为 0，不同为 1。

键值之道：深入学习Java中强大的HashMap（二）https://developer.aliyun.com/article/1480892

键值之道：深入学习Java中强大的HashMap（一）