重谈HashMap（二）

发表于 | 分类于

在上文中，主要针对于HashMap定义中的JavaDoc进行了解读，以及了解了一些HashMap实现中所定义的常量。本文将继续针对于HashMap的源码进行解读，了解其设计背后的理念。

HashMap类及成员定义

在Java语言的实践中，一个类主要包括类定义、成员定义以及方法定义。类定义作为最基础的部分，在其中告诉了我们该类与其他类的关系。HashMap的类定义部分如下：

1
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

由以上可知，HashMap继承自AbstractMap这一Map的抽象实现，同时实现了Cloneable和Serializable这两个标记接口来保证其具有可被克隆和序列化的能力。

此处如果关注AbstractMap的定义可以发现，其已经实现了Map接口。但是HashMap在继承自AbstractMap的基础上，又实现了Map接口。针对于该实现的原因，请参考stackoverflow的讨论

在成员定义上，HashMap定义的非静态成员有6个，具体定义及含义如下：

1
2
3
4
5
6
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;

  • Node[] table: HashMap数据结构的基础，每个数组元素都是不同Hash值的真实数据节点；其长度永远是2的n次幂
  • Set> entrySet: Map内元素的集合视图
  • int size: HashMap中包含的k-v对数量
  • int modCount: 针对于HashMap内元素变更的记录，供迭代等方法调用
  • threshold: 阈值，达到该阈值后，会触发扩容操作
  • loadFactor: 哈希表负载因子

以上便是HashMap中变量的定义。可以看出，HashMap中并没有很多晦涩的成员定义。其定义的六个变量，即可完成数据存储和整个容器变化的支撑。
如果仔细观察，可以发现在HashMap中除却阈值和负载因子外，全部成员都被定义成了 transient 的，也就是说在序列化的时候这些属性不会被序列化处理。针对于size和modCount，如果不序列化还可以理解，因为这些值可以通过反序列化后再获取，但是table作为数据的载体，不进行序列化的话数据就没办法成功保存。仔细阅读HashMap的实现后，可以知道其实现了 writeObject 和 readObject 方法来实现序列化与反序列化，在方法中有针对于table等属性的具体序列化实现。有关于序列化相关内容，将在后续内容中进行详细介绍。

HashMap的构造方法

构造方法在对象初始化时被调用。在HashMap中，构造方法有四个重载，具体构造方法声明分别如下：

1
2
3
4
5
6
7
public HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity)
public HashMap()
public HashMap(Map<? extends K, ? extends V> m)

  • 指定初始容量和负载因子，在HashMap初始化时会根据指定的参数进行loadFactor、threshold两个参数进行初始化；
  • 指定初始容量，使用该初始容量和默认的负载因子进行loadFactor、threshold两个参数的初始化；
  • 不指定默认初始容量和负载因子，采用默认机制初始化
  • 由一个现有Map实例构建新的HashMap

详细查看HashMap构造方法的源码，可发现其不同重载下的实现是不同的。在指定初始容量和负载因子或仅指定初始容量的实现中，主要做了指定负载因子和扩容阈值两个操作。具体可查看如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and load factor.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
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);
}
/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

上文方法定义中，可以看到，HashMap初始化时主要是针对loadFactor和threshold这两个属性进行初始化。
随着继续向下看，可以看到HashMap中对于无参构造方法的重载定义如下：

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

看到这，我们发现了一个问题：为什么在前两个有参数的构造方法重载中，会初始化loadFactor和threshold两个参数，但是在无参构造函数中却仅仅是初始化loadFactor一个参数呢。
我们从头来想，虽然threshold未在构造方法中声明，但是在HashMap的使用中是必不可缺的。那么为什么没在构造方法中声明呢？答案其实已经有了一个方向，就是在需要该成员的操作前，将其进行了声明。有了这一思路，我们就可以把眼光转向HashMap中对于put方法的实现：在put中，首次添加元素到HashMap会调用resize方法进行初始化，在resize的过程中，则进行了threshold的初始化。

除了三个初始化空HashMap的构造方法外，HashMap中还提供了从一个已有的Map构造HashMap的构造方法。该方法主要进行的便是遍历传入Map的entry，并将其插入新HashMap中并返回。

tableSizeFor方法

在阅读HashMap构造方法的源码中，我们发现其通过 tableSizeFor(int) 这一方法实现了获取threshold。该方法定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

刚见该方法，感觉毫无头绪，方法的注释仅仅告诉我们该方法的作用是：根据目标容量返回一个2的幂次的数。
反观这个方法，我们来具体看看它做了什么。
首先，利用如下测试用例对该方法的实际运行结果进行了测试。

1
2
3
4
5
System.err.println(tableSizeFor(0));
System.err.println(tableSizeFor(1));
System.err.println(tableSizeFor(2));
System.err.println(tableSizeFor(4));
System.err.println(tableSizeFor(10));

输出结果如下：

1
2
3
4
5
1
1
2
4
16

由以上测试的运行结果可以看出，该方法主要获取到的是大于或等于输入值的最小2的幂次的值。
再观tableSizeFor方法，我们来具体看这个方法到底做了什么。
针对于传入参数，是一个int型的整数。在Java中int型所占空间是32位。
所以在这五次运算中，其主要意义是将传入参数的二进制表示中，首个1出现的位置之后的值全部变为1。

该算法首先将传入参数在基础上减一，再在结尾后加一。这样做的目的主要是能够得到大于或等于传入参数的2的幂次值，并同时能够防止加1操作导致的溢出。

tableSizeFor的方法作为jdk 1.8版本中的一项改进，通过位运算的方式提高了运行速度。在jdk12中，针对于该方法继续进行了优化，才用通过二进制表现形式中前导0的个数计算移动位数，只进行唯一一次移动即可。

小结

随着tableSizeFor的分析，我们可以得到threshold这个属性一直都是2的幂次。HashMap的容量同样是2^n。那么HashMap为什么这么设计呢？其容量与put、get方法又有什么关系。在下一篇系列文章中，会针对put、get两个操作进行源码解析。探究HashMap为什么设置成只能是2^n。