5.1 HashMap 的工作原理

HashMap 是一种键 - 值（key-value）映射表，它通过 key 快速查找对应的 value。HashMap 内部使用一个大数组存储所有 value，并根据 key 直接计算出 value 应该存储在哪个索引，从而实现快速存取。这种方式是一种典型的空间换时间策略。

5.2 Key 的比较

当我们使用 key 从 Map 中获取 value 时，传入的 key 对象不一定与当初放入 Map 中的 key 对象是同一个对象。 换句话说，两个 key 对象可能是内容相同，但并非指向内存中的同一地址。

为了验证这一点，参考以下示例代码：

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        String key1 = "a";
        Map<String, Integer> map = new HashMap<>();
        map.put(key1, 123);

        String key2 = new String("a");
        map.get(key2); // 123

        System.out.println(key1 == key2); // false
        System.out.println(key1.equals(key2)); // true
    }
}

从代码的运行结果可以看出，key1 == key2 的结果是 false，这意味着 key1 和 key2 指向的是不同的对象。 但是，key1.equals(key2) 的结果是 true，这意味着 key1 和 key2 的内容相同。

HashMap 内部通过 equals() 方法比较 key 是否相等。 因此，作为 HashMap 的 key 的对象，必须正确覆写 equals() 方法。 这与在 List 中查找元素时需要正确覆写 equals() 方法是类似的。 如果 key 对象没有正确覆写 equals() 方法，HashMap 可能无法正确地找到对应的 value。

5.3 hashCode() 方法的作用

HashMap 通过 key 对象的 hashCode() 方法计算索引，相同的 key 对象（使用 equals() 判断时返回 true）必须计算出相同的索引，否则相同的 key 每次取出的 value 就不一定对。

因此，正确使用 Map 必须保证：

1. 作为 key 的对象必须正确覆写 equals() 方法，相等的两个 key 实例调用 equals() 必须返回 true；

2. 作为 key 的对象还必须正确覆写 hashCode() 方法，且 hashCode() 方法要严格遵循以下规范：

   • 如果两个对象相等，则两个对象的 hashCode() 必须相等；
   • 如果两个对象不相等，则两个对象的 hashCode() 尽量不要相等。

对应两个实例 a 和 b：

• 如果 a 和 b 相等，那么 a.equals(b) 一定为 true，则 a.hashCode() 必须等于 b.hashCode()；
• 如果 a 和 b 不相等，那么 a.equals(b) 一定为 false，则 a.hashCode() 和 b.hashCode() 尽量不要相等。

第一条规范是正确性，必须保证实现，否则 HashMap 不能正常工作。第二条如果尽量满足，则可以保证查询效率，因为不同的对象，如果返回相同的 hashCode()，会造成 Map 内部存储冲突，使存取的效率下降。

5.4 hashCode() 方法的编写

在正确实现 equals() 的基础上，还需要正确实现 hashCode()。equals() 中用到的用于比较的每一个字段，都必须在 hashCode() 中用于计算；equals() 中没有使用到的字段，绝不可放在 hashCode() 中计算。

以 Person 类为例：

public class Person {
    String firstName;
    String lastName;
    int age;
}

把需要比较的字段找出来：

• firstName
• lastName
• age

然后，引用类型使用 Objects.equals() 比较，基本类型使用 == 比较。

在正确实现 equals() 的基础上，我们还需要正确实现 hashCode()，即上述 3 个字段分别相同的实例，hashCode() 返回的 int 必须相同：

public class Person {
    String firstName;
    String lastName;
    int age;

    @Override
    int hashCode() {
        int h = 0;
        h = 31 * h + firstName.hashCode();
        h = 31 * h + lastName.hashCode();
        h = 31 * h + age;
        return h;
    }
}

上述代码展示了如何手动实现 hashCode() 方法。

String 类已经正确实现了 hashCode() 方法，我们在计算 Person 的 hashCode() 时，反复使用 31 * h，这样做的目的是为了尽量把不同的 Person 实例的 hashCode() 均匀分布到整个 int 范围。

和实现 equals() 方法遇到的问题类似，如果 firstName 或 lastName 为 null，上述代码工作起来就会抛 NullPointerException。为了解决这个问题，我们在计算 hashCode() 的时候，经常借助 Objects.hash() 来计算：

int hashCode() {
    return Objects.hash(firstName, lastName, age);
}

Objects.hash() 方法可以处理 null 值，避免空指针异常。

5.5 延伸阅读

5.5.1 HashMap 的数组大小

HashMap 初始化时默认的数组大小只有 16，任何 key，无论它的 hashCode() 有多大，都可以简单地通过：

int index = key.hashCode() & 0xf; // 0xf = 15

把索引确定在 0 ~ 15，即永远不会超出数组范围，上述算法只是一种最简单的实现。

这段代码展示了如何将 hashCode() 的结果转换为 HashMap 内部数组的索引。

• key.hashCode() 获取 key 对象的哈希码，它是一个 32 位的整数。
• & 0xf 是一个按位与运算，其中 0xf 是一个十六进制数，相当于十进制的 15。这个操作的目的是保留 hashCode() 的低 4 位，其余位全部置为 0。
• 由于低 4 位的取值范围是 0000 到 1111，即十进制的 0 到 15，因此 index 的取值范围被限制在 0 到 15 之间，正好对应数组的索引范围。

5.5.2 HashMap 的扩容

添加超过一定数量的 key-value 时，HashMap 会在内部自动扩容，每次扩容一倍，即长度为 16 的数组扩展为长度 32，相应地，需要重新确定 hashCode() 计算的索引位置。例如，对长度为 32 的数组计算 hashCode() 对应的索引，计算方式要改为：

int index = key.hashCode() & 0x1f; // 0x1f = 31

由于扩容会导致重新分布已有的 key-value，所以，频繁扩容对 HashMap 的性能影响很大。如果我们确定要使用一个容量为 10000 个 key-value 的 HashMap，更好的方式是创建 HashMap 时就指定容量：

Map<String, Integer> map = new HashMap<>(10000);

虽然指定容量是 10000，但 HashMap 内部的数组长度总是 2ⁿ，因此，实际数组长度被初始化为比 10000 大的 16384（2¹⁴）。

5.5.3 哈希冲突

如果不同的两个 key，例如 "a" 和 "b"，它们的 hashCode() 恰好是相同的（这种情况是完全可能的，因为不相等的两个实例，只要求 hashCode() 尽量不相等），那么，当我们放入：

map.put("a", new Person("Xiao Ming"));
map.put("b", new Person("Xiao Hong"));

时，由于计算出的数组索引相同，后面放入的 "Xiao Hong" 不会把 "Xiao Ming" 覆盖。

在 HashMap 内部，确实可能存在不同的 key，映射到相同的 hashCode()，即相同的数组索引上。

我们就假设 "a" 和 "b" 这两个 key 最终计算出的索引都是 5，那么，在 HashMap 的数组中，实际存储的不是一个 Person 实例，而是一个 List，它包含两个 Entry，一个是 "a" 的映射，一个是 "b" 的映射。

在查找的时候，例如：

Person p = map.get("a");

HashMap 内部通过 "a" 找到的实际上是 List<Entry<String, Person>>，它还需要遍历这个 List，并找到一个 Entry，它的 key 字段是 "a"，才能返回对应的 Person 实例。

我们把不同的 key 具有相同的 hashCode() 的情况称之为哈希冲突。在冲突的时候，一种最简单的解决办法是用 List 存储 hashCode() 相同的 key-value。显然，如果冲突的概率越大，这个 List 就越长，Map 的 get() 方法效率就越低。

hashCode() 方法编写得越好，HashMap 工作的效率就越高。