本文参考视频：小马哥教育(SEEMYGO) 2019 年 恋上数据结构与算法（第一季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化

0. 需求分析

0.1 TreeMap 分析

时间复杂度（平均）

由于 TreeMap 底层采用的红黑树实现的，因此 TreeMap 的添加、删除、搜索的平均时间复杂度都为$O(logn)$。

TreeMap 的特点

• key 必须具备可比较性
• 元素的分布是有顺序的

实际应用

实际应用中，很多时候的需求：

• Map 中存储的元素不需要讲究顺序
• Map 中的 key 不需要具备可比较性

如果这个时候还使用底层红黑树实现的 TreeMap 就会造成不必要的浪费。

不考虑顺序、不考虑 key 的可比较性，Map 有更好的实现方案，这个方案的平均时间复杂度可以达到 $O(1)$。

这个方案就是采用 哈希表 实现 Map。💪

0.2 需求由来

现有一个需求： 设计一个写字楼通讯录，存放所有公司的通讯信息。

座机号码作为 key （假设座机号码最长为 8 位），公司详情（名称、地址等信息）作为 value。

同时要求添加、删除、搜索的时间复杂度都是 $O(1)$。

根据上面的需求，可以有如下设计：

12345678910111213private Company[] companies = new Company[100000000];

public void add(int phone, Company company) {
    companies[phone] = company;
}

public void remove(int phone) {
    companies[phone] = null;
}

public Company get(int index) {
    return conpanies[phone];
}

虽然上述的代码满足需求，但是也存在很大的问题：

• 空间复杂度非常大
• 空间使用率极低，存在大量空间未使用，非常浪费内存空间
• 数组 companies 是一个哈希表，是典型的「空间换时间」

1. 基本概念

本节中涉及的 HashMap 暂由 JDK 提供。

1.1 初始哈希表

哈希表（Hash Table），又叫散列表，其中 hash 有「剁碎」的意思。

那么哈希表是如何高效处理顺序的呢？

假设现有这样几组数据需要被放入哈希表中：

123put("jack", 666);
put("Rose", 777);
put("Kate", 888);

这些数据由 key 和 value 组成，哈希表底层是数组，key 通过哈希函数计算（$O(1)$级别的计算）后，得到数组的索引，然后在数组索引位置放入 value。如：

在哈希表中，哈希表的长度最好是 2 的幂。原因在哈希函数中介绍~

数据操作流程

添加、搜索、删除的流程都是类似的：

1. 利用哈希函数生成 key 对应的索引 index，时间复杂度 $O(1)$
2. 根据索引 index 操作定位数组元素，时间复杂度 $O(1)$

哈希表是「空间换时间」的典型应用。

哈希函数，也叫作散列函数。

哈希表内部的数组元素，在很多地方也被叫做 Bucket （桶），整个数组叫 Buckets 或者 Buckets Array。

1.2 哈希冲突

哈希冲突（Hash Collision），又被叫做哈希碰撞。其含义是： 两个不同的 key，经过哈希函数计算出相同的结果（索引）。如：

那么应该如何解决哈希冲突呢？

• 开放定址法（Open Addressing）：按照一定的规则（线性探测、平方探测）向其他地址进行探测，直到遇到空桶
• 再哈希法（Re-Hashing）：设计多个哈希函数
• 链地址法（Separate Chaining）：比如通过链表将同一个索引的元素串起来

JDK 1.8 解决方法

在 JDK 1.8 中，使用的是 链地址法 ，默认使用 单向链表 将元素串起来。

在添加元素时，可能会由 单向链表 转为 红黑树 来存储元素。

• 比如当哈希表容量 >= 64 且 单向链表 的节点数量大于 8 时，如下图所示：

当红黑树节点数量少到一定程度时，又会转为单向链表。

所以，JDK 1.8 中的哈希表是使用 链表 + 红黑树 解决哈希冲突的。

思考： 这里为啥使用单向链表，而不是双向链表？

假设现在向一个哈希表中插入以下数据，同时这些数据的 key 通过哈希函数计算后得到的 index 是一样的，又假设都是 01：

123put("a", 40);
put("b", 50);
put("c", 60);

为防止哈希冲突，会采用 链地址法，结构和上图一样。

如果这时再插入一个数据 put("b", 70);，显然新插入数据的 key 在原哈希表中已经存在，也会产生哈希冲突。这个时候要怎么做呢？

将新插入的数据与原本的数据从链表头一个一个进行比较（比较 key）：先与节点 40 进行 key 值比较，发现不一样，然后跳到下一个；再与节点 50 进行 key 值比较，key 值一样，用新数据覆盖旧数据；如果比较到链表尾都没找到相同的 key 值，那么直接在链表尾插入添加数据。

使用单链表的主要原因有：

• 每次都是从头结点开始遍历的
• 单向链表比双向链表少一个指针，可以节约内存空间

此时又会发现一个问题：不是说使用哈希表不考虑顺序、 key 值的比较性吗？这下又需要使用红黑树，就必须要使节点有可比较性，那么是否矛盾呢？

这个问题后续编码时解决，暂时不急。😜

1.3 哈希函数

哈希表中哈希函数的实现步骤大致如下：

1. 先生成 key 的哈希值（必须是 整数）
2. 再让 key 的哈希值 跟 数组的大小 进行相关运算，生成一个 索引值，如：

123public int index(Object key) {
    return hash_code(key) % table.length;
}

为了提高效率，可以使用 & 位运算取代 % （模）运算，前提是 将数组的长度设计为 2 的幂，即 $2^n$：

123public int index(Object key) {
    return hash_code(key) & (table.length - 1);
}

& 运算规则

& 位运算规则：同 1 取 1，否则取 0。即 $1011 \ \& \ 1010 = 1010$。

那么使用 & 位运算后的代码为什么是这样的呢？

首先要明白数的二进制表示，如：

12341           2^0
10          2^1
100         2^2
1000        2^3

如果对上面的数减一后，二进制又是怎样的呢？

12340           2^0 - 1
01          2^1 - 1
011         2^2 - 1
0111        2^3 - 1

二进制表示的数中，前面的 0 可以省略。

然后用一个二进制的数与全 1 的数进行 & 位运算会得到什么结果呢？

1234  101101011
& 111111111
--------------
  101101011

发现进行 & 位运算后得到的结果与原来的数一样。但这只是最浅显的特点，还有一个更加重要的特点： 得到的结果一定不大于进行 & 位运算中全 1 的数。

11001010 & 1111 ：

1234  11001010
& 00001111
-----------
  00001010

位数不足用 0 填充。

得到的结果 1010 比 1111 要小，如果是 11001111 与 1111 进行 & 位运算，得到的结果为 1111，两者相同。

正是因为这个特点，可以使用 & 位运算来代替模运算以提高效率。

如果需要自行设计一个哈希函数，应该怎么设计一个良好的哈希函数呢？

让哈希值更加均匀分布，减少哈希冲突次数，从而提升哈希表的性能。

1.4 哈希值计算

如何生成 key 的哈希值

key 的常见种类有很多，比如： 整数、浮点数、字符串、自定义对象

不同种类的 key，哈希值的生成方式是不一样的，但目标是一致的

• 尽量让每个 key 的哈希值是唯一的
• 尽量让 key 的所有信息参与运算

在 Java 中， HashMap 的 key 必须实现 hashCode()、 equals() 方法，允许 key 为 null。

在 Java 中，哈希值必须是 int 类型的。

int 与 float 的哈希值

key 为整数时：其整数值就当作哈希值，比如 10 的哈希值就是 10

123public static int hashCode(int value) {
    return value;
}

key 为单精度浮点数时： 将存储的二进制格式转为整数值

123public static int hashCode(float value) {
    return floatToIntBits(value);
}

long 与 double 的哈希值

int 类型占 4 个字节，即： 32 位，long 类型是占 8 个字节，即： 64 位。

在 Java 中，哈希值必须是 int 类型，就是说 long 类型的哈希值只能是 32 位，那应该咋办？

有一种方法是选择 long 类型的前 32 位 或者后 32 位作为哈希值，但这种方法有一个问题，怎么「尽量让 key 的所有信息参与运算」呢？

123public static int hashCode(long value) {
    return (int) (value ^ (value >>> 32));
}

同样，double 类型也占 8 个字节，即： 64 位。现给出一种方法：

1234public static int hashCode(double value) {
    long bits = doubleToLongBits(value);
    return (int) (bits ^ (bits >>> 32));
}

在这两段代码中， >>> （无符号右移）与 ^ （异或）的作用是什么呢？

• 高 32 bit 和低 32 bit 混合计算出 32 bit 的哈希值
• 充分利用所有信息计算出的哈希值

^ 异或运算的规则是相同为 0，不同为 1。

通过上面的图示，可以看到 64 bit 都参与了运算。

那为什么运算的时候用异或？而不是与运算或者或运算？

如果使用其他运算，得到的结果没有意义，都是参加计算的数据，而不是得到的不同的数据。

字符串的哈希值

整数 5489 应该怎么用十进制计算？

字符串是由若干个字符组成的，比如字符串 jack， 由 j、a、c、k 四个字符组成（字符的本质就是一个整数）。因此，jack 的哈希值可以表示为：

那么这个 $n$ 是多少呢？在 JDK 中，$n$ 被设定为 $31$，那又为什么是 $31$ 呢？

31 是个神奇的数字。它是一个奇素数， JVM 会将 31 * i 优化成 (i << 5) - i 。

12345678910111213141516public class Main {
    public static void main(String[] args) {
        // 3254239
        String string = "jack";
        int len = string.length();
        int hashCode = 0;
        for (int i = 0; i < len; i++) {
            char c = string.charAt(i);
            hashCode = hashCode * 31 + c;
            // hashCode = (hashCode << 5) - hashCode + c;

        }
        // 3254239
        System.out.println(hashCode);
    }
}

每次在编写 Java 代码计算字符串的哈希值时，都要书写上面的代码吗？

其实不用，JDK 已经提供了计算字符串哈希值的方法 string.hashCode()，其内部实现与上面书写的代码是一样的。

31 的探讨

JVM 优化原理：

$31$ 不仅仅是符合 $2^n - 1$，它还是一个奇素数（既是奇数，又是素数）。

素数和其他树相乘的结果比其他方式更容易产生唯一性，减少哈希冲突。

最终选择 31 是经过观测分布结果后的选择。

常见类型计算总结

12345678910111213static void test2() {
    Integer a = 110;
    Float b = 10.6f;
    Long c = 156l;
    Double d = 10.9;
    String e = "mofan";

    System.out.println(a.hashCode()); // 110
    System.out.println(b.hashCode()); // 1093245338
    System.out.println(c.hashCode()); // 156
    System.out.println(d.hashCode()); // -1930887167
    System.out.println(e.hashCode()); // 104071729
}

上面的代码就是使用 JDK 中提供的方法求一些数据的哈希值。在倒数第二个输出中可以看到，求得结果是负数，那么计算索引时会出现负数吗？

其实是不会的，因为求索引进行的是位运算。无视符号，数值直接运算。😉（如果有计算机组成原理的知识就十分好理解了）

自定义对象

假设现在有一个自定义对象 Person，其属性与构造方法如下：

1234567891011public class Person {
    private int age;
    private float height;
    private String name;

    public Person(int age, float height, String name) {
        this.age = age;
        this.height = height;
        this.name = name;
    }
}

尝试实例化这个对象，并打印出哈希值：

1234567static void test3() {
    Person p1 = new Person(20, 1.76f, "mofan");
    Person p2 = new Person(20, 1.76f, "mofan");
    // 和内存地址有关 因此两个输出并不相等
    System.out.println(p1.hashCode());
    System.out.println(p2.hashCode());
}

最终打印出来的两个哈希值是不一样的。

因为直接使用自定义对象的 hashCode() 方法计算出的哈希值和内存地址有关，这两个对象显然不是同一个内存地址，因此它俩也就不相等。

但在实际开发中，就实例化的 Person 对象而言，当年龄、身高、姓名都相等时，会将这两个对象视为同一个对象，这时它们打印出的哈希值应该是相等的。

那应该怎么做？

需要在 Person 类中重写 hashCode() 方法，自定义计算方式：

1234567@Override
public int hashCode() {
    int hashCode = Integer.hashCode(age);
    hashCode = hashCode * 31 + Float.hashCode(height);
    hashCode = hashCode * 31 + (name != null ? name.hashCode() : 0);
    return hashCode;
}

这时得到的结果是：

不同实例对象得到的哈希值是一样的！ 🎉🎊

Q & A

Q1：哈希值太大，整型溢出怎么办？

A1：不做任何处理。计算哈希值就是为了得到一个整型的数据，溢出就溢出，无所谓~

Q2：不重写 hashCode() 方法有什么后果？

A2：如果不重写，会按照默认的方式进行计算，计算结果与内存有关。即使是属性值都相等的两个对象，由于内存分配不同，最终得到的哈希值也往往不同。

1.5 equals() 方法

在上一节中说明了：

• 在 Java 中， HashMap 的 key 必须实现 hashCode()、 equals() 方法，也允许 key 为 null
• 解释了为什么要重写 hashCode() 方法

那么为什么还要重写 equals() 方法呢？

假设哈希表中索引为 01 的位置已经发送了哈希冲突，并在这个位置使用了链地址法解决哈希冲突，再次假设这个位置已经有 3 个数据。

此时再向哈希表插入一个数据，这个数据的 key 经过哈希函数计算后得到的索引又是 01，再次发生哈希冲突，继续使用链地址法解决。

获取新插入元素的 key 与原来索引 01 位置的其他数据的 key 进行相等性比较，如果原来的数据中存在一个数据与新插入数据的 key 相等，使用新插入数据覆盖原有数据，如果不存在这样的数据，使用链地址法在链表尾插入新添加的元素。

这其中涉及到一个相等性比较，而且是 key 值的相等比较，那为什么是 key 值比较，不能用哈希值进行比较吗？

答案是不行的。

因为很可能有几种完全不相干的数据（比如数据类型不同）却计算出相同的哈希值，如果采用哈希值进行相等比较，难道这个时候要用完全不相干的数据去覆盖原数据吗？

显然还是不行的。

针对同一类型的不同实例，计算得到的哈希值也可能是一样的，此时也不能认为这些对象就相等了（属性值可能不同）。同时应当明白发生哈希冲突并不是指计算出的哈希值一样就发生了哈希冲突，哈希冲突是由哈希函数计算出的哈希表索引 index 相同而产生的。（可以参考前面 哈希函数 中的代码理解）

说了这么多，就是为了说明必须要在实体类（用作 HashMap key 的类型）中重写 equals() 方法。

123456789101112131415@Override
public boolean equals(Object obj) {
    // 内存地址相等时
    if (obj == this) return true;
    // 传递对象为 null 时，传递对象与调用对象类型不同时
    if (obj == null || obj.getClass() != getClass()) return false;
    // if (obj == null || !(obj instanceof Person)) return false;
    Person person = ((Person) obj);
    return person.age == age && person.height == height
        && valueEquals(person.name, name);
}

private boolean valueEquals(Object v1, Object v2) {
    return v1 == null ? v2 == null : v1.equals(v2);
}

上述代码给出了两种比较类型的方式：

• obj.getClass() != getClass()
• !(obj instanceof Person)

假设有一个类叫 Person，它有一个子类叫 Student。

如果这时候 obj 的类型是 Student，对于第一种方式的结果是 true，而对于第二种方式的结果是 false。显然，第一种得到的结果才是需要的，因此建议使用第一种比较类型的方式。

PS：如果 obj 是 Person 的子类，采取 obj instanceof Person 进行类型判断，得到的结果会是 true。

1.6 阶段性总结

在 Java 中， HashMap 的 key 必须重写 hashCode()、 equals() 方法，允许 key 为 null。

重写两个方法

其中，hashCode() 方法是在生成索引的时候使用；而 equals() 方法是在发生哈希冲突后，将新插入数据与进行了链地址法生成的数据链（单向链表或红黑树）中的数据挨个进行相等性比较，如果存在相等元素，使用新插入数据覆盖原数据，否则在数据链尾添加新插入数据。

两个方法都没重写

如果 HashMap 的 key 对应的类型都没重写 hashCode() 和 equals() 方法，又会怎么样呢？

非自定义类型的数据按照前面所说的方法计算哈希值，自定义类型数据的哈希值与内存地址有关。

由于没有实现 equals() 而进行相等性比较，会默认比较内存地址。

假设向一个 HashMap 插入下列三组数据，Person 类中没有重写 hashCode()、 equals() 方法：

12345678910111213static void test3() {
    Person p1 = new Person(20, 1.76f, "mofan");
    Person p2 = new Person(20, 1.76f, "mofan");
    // 和内存地址有关 因此两个输出并不相等
    System.out.println(p1.hashCode());
    System.out.println(p2.hashCode());

    Map<Object, Object> map = new HashMap<>();
    map.put(p1, "abc");
    map.put("test", "ccc");
    map.put(p2, "bcd");
    System.out.println(map.size()); // 3
}

假设 p1、p2 的哈希值不一样，但经过哈希函数的运算后，p1、p2 和 test 的索引是一样的（假设！），虽然会发生哈希冲突，由于没重写 equals()，使用内存地址进行相等性比较，显然这三者的内存地址不一样，因此 HashMap 最终的长度是 3。

只重写 equals() 方法

如果只重写 equals() 方法，而不重写 hashCode() 方法，计算哈希值时会采用默认方式。对于自定义类型，算出的哈希值与内存地址有关。

还是以上述的代码，这个时候 p1、p2 计算得到哈希值不是同一个，key 为 test 的数据计算出的哈希值也大概率和它们不同（类型都不一样）。

三者的哈希值不一样，但经过哈希函数计算得到的索引可能是一样，可能不一样：

• 如果索引一样，一般是 p1 与 p2 的索引一样，发生哈希冲突，使用链地址法解决，又因为重写了 equals() 方法，p1 与 p2 相等，最终得到的 HashMap 长度是 2（存在 p2 和 test 的 key）

• 如果索引不一样，那么这三个 key 不会发生哈希冲突，最终得到的 HashMap 长度是 3

没有重写 hashCode() 会导致不稳定。所谓不稳定指的是两个对象的属性值是一样的，但是会不会覆盖是无法确定的。

只重写 hashCode() 方法

如果只实现 hashCode() 方法，而不实现 equals() 方法，进行相等性比较时会采取默认的方法。对于自定义类型，比较的是内存地址，因此对于同一类型的不同实例，就算它们包含相同的字段值，它们也不相等。

依旧采用上述代码，因为重写了 hashCode() 方法，此时 p1、p2 计算得到的哈希值是一样的，通过哈希函数计算得到的索引也是一样的，而对于 key 为 test 的数据就会有两种情况：

1. 哈希函数计算后得到的索引与 p1、p2 一样
2. 哈希函数计算后得到的索引与 p1、p2 不一样

当 key 为 test 的数据通过哈希函数计算后得到的索引与 p1、p2 一样时，这三个数据会发生哈希冲突，但是因为没实现 equals() 方法，使用内存地址进行相等性比较，它们三个的内存地址是不相等的，因此不会相互覆盖，最终得到的 HashMap 长度是 3。

当 key 为 test 的数据通过哈希函数计算后得到的索引与 p1、p2 不一样时，p1、p2 会发生哈希冲突，但它俩的内存地址不同，两者不相等，彼此也不会进行覆盖，最终得到的 HashMap 长度还是 3。

两个方法都重写

自定义对象作为 key 时，需要同时重写 hashCode()、 equals() 方法。

• equals()：用以判断 2 个 key 是否为同一个 key

• hashCode()：必须保证 equals() 为 true 的 2 个 key 的哈希值一样，不同对象尽量拥有不同的哈希值，使得哈希冲突尽量少

反过来，hashCode() 相等的 key，equals() 的判定不一定为 true。

总结

Object 类中默认的实现：

• equals() 以对象的内存地址作为相等性判断
• hashCode() 返回对象内存地址的哈希值

没有同时重写这两个方法，并且存在两个内部字段相同的对象时：

• 如果都没重写，由于两个对象的内存地址不同，会被认定为两个不相等的对象，使得 HashMap 里存在相同的 key
• 如果只重写了 equals() 方法，将按照对象内存地址计算这两个对象的哈希值，可能得到不同的哈希值，最终也会使得 HashMap 里存在相同的 key
• 如果只重写了 hashCode() 方法，这两个对象的哈希值一样，发生哈希冲突，但无法通过相等性判断，最终依旧会导致 HashMap 里存在相同的 key

在 Java 中， 如果一个对象要作为 HashMap 的 key，那么必须重写 hashCode()、 equals() 方法。

重写的 hashCode()、 equals() 方法中包含哪些成员变量是根据需求而定的。对于自定义类型的 Person，有三个成员变量：age、name 和 height：

• 假设认为两个对象的 age 和 name 相等时，它们就相等，因此在重写的 hashCode() 和 equals() 方法中必须包含 age 和 name

• 如果要 age、name、height 都相等时才相等，那么在重写的 hashCode()、equals() 方法中必须包含 age、 name 和 height

2. 初步实现

前文已经介绍了 JDK8 中 HashMap 的实现，接下来自行实现一个 HashMap。

首先要声明几点，为了便于编写：

• 发生哈希冲突后，使用链地址法解决，只使用红黑树，不再使用单链表
• 在哈希表中，每个桶内不存放红黑树对象，而是存放红黑树的根节点

如果哈希表中存放的是红黑树节点，那么就不再需要红黑树中的 size 成员变量。这个成员变量也确实没用，需要的是哈希表的 size，而非每个桶内红黑树的的 size。

接下来将自行实现一个简单的 HashMap！😎

2.1 清空映射

简单方法实现

先创建一个类，名为 HashMap，然后实现 Map 接口（这个 Map 接口是 集合与映射 一文中编写的接口，在此不再提供代码）。

完善 clear() 方法之前，可以先完善几个简单的方法。

在实现 HashMap 时，肯定需要一个表示 Map 长度的成员变量，定这个成员变量为 size。根据这个成员变量，可以实现两个方法：

12345678910111213public class HashMap<K, V> implements Map<K, V> {
    private int size;

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }
}

实现清空 Map

在实现 clear() 方法之前，可以先设置几个与红黑树有关的常量，再定义一个用于存储红黑树根节点的数组。既然需要存储红黑树根节点，自然少不了需要一个表示节点的类，把这个类命名为 Node，并设置为内部类，最后可以完善一些构造函数。

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758public class HashMap<K, V> implements Map<K, V> {
    private static final boolean RED = false;
    private static final boolean BLACK = true;
    private int size;
    private Node<K, V>[] table; // 存储的红黑树根节点
    // 哈希表数组默认容量 16
    private static final int DEFAULT_CAPACITY = 1 << 4;

    public HashMap() {
        table = new Node[DEFAULT_CAPACITY];
    }

    // 省略实现方法

    private static class Node<K, V> {
        K key;
        V value;
        boolean color = RED;
        Node<K, V> left;   // 左节点
        Node<K, V> right;  // 右节点
        Node<K, V> parent; // 父节点

        public Node(K key, V value, Node<K, V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }

        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        // 判断当前节点是否是其父节点的左子节点
        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }

        // 判断当前节点是否是其父节点的右子节点
        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }

        // 获取兄弟节点
        public Node<K, V> sibling() {
            if (isLeftChild()) {
                return parent.right;
            }
            if (isRightChild()) {
                return parent.left;
            }
            return null;
        }
    }
}

编写 clear() 方法之前，明白它的一些步骤：

1. 如果当前 Map 长度为 0，直接返回；
2. 清空哈希表中每个桶存储的红黑树根节点；
3. 令 Map 长度为 0。

12345678@Override
public void clear() {
    if (size == 0) return;
    for (int i = 0; i < table.length; i++) {
        table[i] = null;
    }
    size = 0;
}

2.2 添加元素

添加元素方法，即：put() 方法。

该方法与 TreeMap 中的添加方法是一样的，但是在这次编写时，对其中部分代码进行了优化：当红黑树根节点不为空时（发生哈希冲突时），将原来的 while 循环变成 do...while 循环，这样可以减少一次判断。

因为这个时候的 root 节点一定不为 null，同时又将 root 赋值给 node，那么这个时候 node 一定不为 null，可以直接进入循环以减少判断次数。

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950@Override
public V put(K key, V value) {
    int index = index(key);
    // 取出 index 位置的红黑树根节点
    Node<K, V> root = table[index];
    if (root == null) {
        root = new Node<>(key, value, null);
        table[index] = root;
        size++;
        afterPut(root);
        return null;
    }
    // 根节点不为空时，产生哈希冲突
    // 添加新的节点到红黑树
    Node<K, V> parent = root;
    Node<K, V> node = root;
    int cmp = 0;
    // 循环方式从 while 变为 do...while
    do {
        cmp = compare(key, node.key);
        parent = node;  // 保存父节点
        if (cmp > 0) {
            node = node.right;
        } else if (cmp < 0) {
            node = node.left;
        } else { // 相等
            node.key = key; // 相等时覆盖
            V oldValue = node.value;
            node.value = value;
            /*
             * 到这一步时，是两个 key equals
             * 表明两个 key 的哈希值一定相等
             * 因此，可以不覆盖哈希值：
             * node.hash = h1;
             */
            return oldValue;
        }
    } while (node != null);
    // 看看插入到父节点的哪个位置
    Node<K, V> newNode = new Node<>(key, value, parent);
    if (cmp > 0) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }
    size++;
    // 添加节点后的处理 传入参数类型为Node
    afterPut(newNode);
    return null;
}

在这个方法第一步，使用方法 index() 获取哈希表 key 位置的红黑树根节点的索引，用于获取该索引下的红黑树跟节点，但还没有编写这个方法，该方法具体如下：

123456789private int index(K key) {
    if (key == null) return 0;
    int hash = key.hashCode();
    /*
     * 高低16位混合运算再次生成哈希值
     * 因为 hashCode() 是用户实现，无法保证是否均匀使用了高低16位运算
     */
    return (hash ^ (hash >>> 16)) & (table.length - 1);
}

除此之外还要将一些在红黑树中常用的方法复制到当前类中，比如：

• compare()：用于对产生哈希冲突而要添加至红黑树的节点的 key 和原红黑树节点 key 进行比较（不能直接使用复制过来的代码，在后续进行调整）
• afterPut()： 向红黑树中添加元素后进行的调整
• rotateLeft()： 左旋转
• rotateRight()：右旋转
• afterRotate()： 旋转之后的调整（该方法直接复制会出错，在后续进行调整）
• color()： 给节点染色
• red()： 使节点染红
• black()： 使节点染黑
• colorOf()：获取节点的颜色
• isBlack()： 判断当前节点是否为黑色
• isRed()： 判断当前节点是否为红色

由于这些方法代码过多，再次不再列出，可以前往以前的博文查看。同时部分方法也存在出入，将会在下面的内容进行介绍~

2.3 节点比较

首先得强调： 用户向 HashMap 中添加数据是可以不考虑顺序、不考虑 key 的可比较性。但由于可能存在哈希冲突，选用了链地址法来解决，并引入了红黑树，而这需要对节点的 key 进行比较，但这也不是说必须具有可比较性，HashMap 有自己的比较方式，并不需要用户考虑。

先理一下添加节点会进行覆盖的情况：哈希值一样，就会发生哈希冲突，使用 equals() 方法得到 true 后，新元素就会覆盖旧元素。

然后理一下比较的方式：

1. 先比较哈希值，哈希值不相等时，返回减法运算结果
2. 哈希值相等时，使用 equals() 进行比较，equasl() 比较相等时，返回 0，进行覆盖
3. equasl() 比较不相等时，对类名进行比较，类名不等时，返回较大的类名
4. 类名相等时，如果具有可比较性，使用自己定义的方式进行比较
5. 同一种类型，哈希值一样，但又不具备可比较性，使用内存地址的哈希值进行比较

注意上面列出的方式是层层递进的。

为了便于计算，也为了避免多次计算同一个节点的哈希值，可以在 Node 类中添加一个表示当前节点哈希值的成员变量，并修改构造方法，让节点在创建时就自动计算出 key 的哈希值：

12345678910111213141516171819private static class Node<K, V> {
    int hash; // key 的哈希值
    K key;
    V value;
    boolean color = RED;
    Node<K, V> left;   // 左节点
    Node<K, V> right;  // 右节点
    Node<K, V> parent; // 父节点

    public Node(K key, V value, Node<K, V> parent) {
        this.key = key;
        this.hash = key == null ? 0 : key.hashCode();
        this.value = value;
        this.parent = parent;
    }
    
    // 省略其他方法
    // --snip--
}

修改从 TreeMap 中复制过来的 compare() 方法，并给它增加两个参数，这两个参数表示前两个参数的哈希值：

12345678910/**
 * @param k1
 * @param k2
 * @param h1 k1 的哈希值
 * @param h2 k2 的哈希值
 * @return
 */
private int compare(K k1, K k2, int h1, int h2) {
    return 0;
}

因为增加了参数，对于 put() 方法也需要进行修改：

123456789101112131415161718192021222324252627282930313233343536373839404142434445@Override
public V put(K key, V value) {
    int index = index(key);
    // 取出 index 位置的红黑树根节点
    Node<K, V> root = table[index];
    if (root == null) {
        root = new Node<>(key, value, null);
        table[index] = root;
        size++;
        afterPut(root);
        return null;
    }
    // 根节点不为空时，产生哈希冲突
    // 添加新的节点到红黑树
    Node<K, V> parent = root;
    Node<K, V> node = root;
    int cmp = 0;
    int h1 = key == null ? 0 : key.hashCode();
    // 循环方式从 while 变为 do...while
    do {
        cmp = compare(key, node.key, h1, node.hash);
        parent = node;  // 保存父节点
        if (cmp > 0) {
            node = node.right;
        } else if (cmp < 0) {
            node = node.left;
        } else { // 相等
            node.key = key; // 相等时覆盖
            V oldValue = node.value;
            node.value = value;
            return oldValue;
        }
    } while (node != null);
    // 看看插入到父节点的哪个位置
    Node<K, V> newNode = new Node<>(key, value, parent);
    if (cmp > 0) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }
    size++;
    // 添加节点后的处理 传入参数类型为Node
    afterPut(newNode);
    return null;
}

完整的 compare() 方法代码如下（仍有不足，稍后进行修改）：

1234567891011121314151617181920212223242526272829303132333435/**
 * @param k1
 * @param k2
 * @param h1 k1 的哈希值
 * @param h2 k2 的哈希值
 * @return 返回值大于 0，表示 k1更大
 */
private int compare(K k1, K k2, int h1, int h2) {
    // 比较哈希值 且 不相等
    int result = h1 - h2;
    if (result != 0) return result;
    // 哈希值相等时，比较 equals()
    if (Objects.equals(k1, k2)) return 0;
    // 哈希值相等，但并不 equals
    // 比较类名
    if (k1 != null && k2 != null) {
        String k1Cls = k1.getClass().getName();
        String k2Cls = k2.getClass().getName();
        result = k1Cls.compareTo(k2Cls);
        // 类名不等时
        if (result != 0) return result;
        // 同一种类型 判断是否具有可比较性
        if (k1 instanceof Comparable) {
            return ((Comparable) k1).compareTo(k2);
        }
    }
    // 同一种类型，哈希值一样，但不具备可比较性
    /**
     * 不为 null的对象哈希值也有可能为 0
     * 1. k1 不为 null，k2 为 null
     * 2. k1 为 null，k2 不为 null
     */
    // 利用内存地址算出的哈希值
    return System.identityHashCode(k1) - System.identityHashCode(k2);
}

compare() 方法不能一开始就使用内存地址计算出哈希值进行比较，因为用户可能会自定义一些比较规则，必须在「走投无路」，实在没法的时候才使用内存地址计算出的哈希值进行比较。

写好 compare() 方法后，也代表 put() 方法写好了，可以编写一个测试方法。

在编写测试方法前，需要先解决当前类中的一些错误。

从 TreeMap 中复制到当前类的 afterRotate() 方法是错误的，因为当前类是一个 HashMap，并没有红黑树的根节点 root 成员变量，但哈希表的桶中存储的就是红黑树的根节点，可以编写一个方法，根据红黑树节点来获取哈希表的索引：

123private int index(Node<K, V> node) {
    return (node.hash ^ (node.hash >>> 16)) & (table.length - 1);
}

上面的 index() 方法其实是方法的重载。

使用 index() 方法来修改 afterRotate() 方法：

1234567891011121314151617private void afterRotate(Node<K, V> grand, Node<K, V> parent, Node<K, V> child) {
    // 让 parent 成为根节点
    parent.parent = grand.parent;
    if (grand.isLeftChild()) {
        grand.parent.left = parent;
    } else if (grand.isRightChild()) {
        grand.parent.right = parent;
    } else { // 没有父节点， grand是根节点
        // 修改前： root = parent
        table[index(grand)] = parent;
    }
    // 更新其他节点的父节点
    if (child != null) {
        child.parent = grand;
    }
    grand.parent = parent;
}

发生了哈希冲突后才会在红黑树中添加非根节点的节点，也正是因为发生了哈希冲突，这些节点的索引是一样的。因此在 afterRotate() 方法中获取红黑树的根节点时，index() 方法的参数可以是 afterRotate() 方法三个参数的任意一个 grand、parent 和 child，它们仨的索引都是一样的。

1234567891011static void test4() {
    Person p1 = new Person(20, 1.76f, "mofan");
    Person p2 = new Person(20, 1.76f, "mofan");
    Map<Object, Integer> map = new HashMap<>();
    map.put(p1, 1);
    map.put(p2, 3);
    map.put("jack", 1);
    map.put("rose", 1);
    map.put("jack", 3);
    System.out.println(map.size()); // 3
}

2.4 获取元素

获取方法 get() 是根据一个 key 获取 HashMap 中的值，可以编写一个 node() 方法，这个方法可以根据 key 来获取节点。根据方法 node() 就可以很轻松地实现 get() 方法。

1234567891011121314private Node<K, V> node(K key) {
    Node<K, V> node = table[index(key)];
    int h1 = key == null ? 0 : key.hashCode();
    while (node != null) {
        int cmp = compare(key, node.key, h1, node.hash);
        if (cmp == 0) return node;
        if (cmp > 0) {
            node = node.right;
        } else if (cmp < 0) {
            node = node.left;
        }
    }
    return null;
}

凭借 node() 方法轻松实现 get() 和 containsKey()：

123456789@Override
public V get(K key) {
    Node<K, V> node = node(key);
    return node != null ? node.value : null;
}
@Override
public boolean containsKey(K key) {
    return node(key) != null;
}

2.5 删除元素

Map 接口中的删除元素方法 remove(K key) 是根据 key 来进行删除的，而自行实现的时候需要根据节点来进行删除，因此我们需要对原删除方法进行重载：

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647private V remove(Node<K, V> node) {
    if (node == null) return null;
    size--;
    V oldValue = node.value;
    if (node.hasTwoChildren()) { // 度为2的节点
        // 找到后继节点
        Node<K, V> s = successor(node);
        // 用后继节点的值覆盖被删除节点的值
        node.key = s.key;
        node.value = s.value;
        // 节点的哈希值也要覆盖，不然还是以前节点的哈希值
        node.hash = s.hash;
        // 变量node指向其后继节点，等待后续删除
        node = s;
    }
    // 删除node节点（node的度必然为1或0）
    Node<K, V> replacement = node.left != null ? node.left : node.right;
    // 获取红黑树节点在哈希表中的索引
    int index = index(node);
    if (replacement != null) {   // node度为1
        // 更改parent
        replacement.parent = node.parent;
        // 更改node的parent的left、right的指向
        if (node.parent == null) { // node度为1，且为根节点
            table[index] = replacement;
        } else if (node == node.parent.left) {
            node.parent.left = replacement;
        } else { // node == node.parent.right
            node.parent.right = replacement;
        }

        afterRemove(replacement);
    } else if (node.parent == null) { // node度为0，是叶子节点，并且是根节点
        table[index] = null;
        // 被删除的节点
        afterRemove(node);
    } else { // node是叶子节点，但不是根节点
        if (node == node.parent.left) {
            node.parent.left = null;
        } else {
            node.parent.right = null;
        }
        // 被删除的节点
        afterRemove(node);
    }
    return oldValue;
}

在重载方法中用到了获取后继节点的方法，因此需要将获取后继节点的方法 successor() 复制到当前类中：

123456789101112131415161718private Node<K, V> successor(Node<K, V> node) {
    if (node == null) return null;
    // 后继节点在右子树中
    Node<K, V> p = node.right;
    if (p != null) {
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }
    // 从“祖宗节点”中寻找后继节点
    while (node.parent != null && node == node.parent.right) {
        node = node.parent;
    }

    // node.parent == null || node == node.parent.left
    return node.parent;
}

最后在原删除方法中调用重载的方法：

1234@Override
public V remove(K key) {
    return remove(node(key));
}

2.6 发现问题

注意： 以下测试涉及到内存地址，不同的测试环境输出不同。

到此已经实现了 HashMap 的所有接口，并进行了简单的测试，似乎都没有问题，其实非也，再进行一下测试。

123456789101112131415161718192021222324public class Key {
    protected int value;

    public Key(int value) {
        this.value = value;
    }

    @Override
    public int hashCode() {
        return value / 20;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) return true;
        if (obj == null || obj.getClass() != getClass()) return false;
        return ((Key) obj).value == value;
    }

    @Override
    public String toString() {
        return "v(" + value + ")";
    }
}

编写一个测试类，使用刚刚新创建的 Key 类进行测试：

123456789static void test5() {
    Map<Object, Integer> map = new HashMap<>();
    for (int i = 1; i <= 19; i++) {
        // 这 19 个元素都在同一个红黑树上
        map.put(new Key(i), i);
    }
    System.out.println(map.size()); // 应该输出 19 
    System.out.println(map.get(new Key(8))); // 应该输出 8
}

实际输出结果为 19 和 null，与预想的不一致。😥

可以在这个方法中让 map 调用 traversal() 方法看一下红黑树的节点：

1234567map.traversal(new Map.Visitor<Object, Integer>() {
    @Override
    public boolean visit(Object key, Integer value) {
        System.out.println(key + "_" + value);
        return false;
    }
});

发现从 1 到 19 都是有的，但是为什么获取 8 的时候却打印的 null 呢？

现在换一个数字，假设获取 1，看看能否获取成功，结果发现 1 又可以被打印出现。

这就出现了一个问题：不稳定！

为什么会出现这种情况呢？其主要原因就是 compare() 方法的问题。

123456789101112131415private int compare(K k1, K k2, int h1, int h2) {
    int result = h1 - h2;
    if (result != 0) return result;
    if (Objects.equals(k1, k2)) return 0;
    if (k1 != null && k2 != null) {
        String k1Cls = k1.getClass().getName();
        String k2Cls = k2.getClass().getName();
        result = k1Cls.compareTo(k2Cls);
        if (result != 0) return result;
        if (k1 instanceof Comparable) {
            return ((Comparable) k1).compareTo(k2);
        }
    }
    return System.identityHashCode(k1) - System.identityHashCode(k2);
}

在比较两个 value（差值小于 20）不同的 Key 对象时，这两个 Key 对象的哈希值是一样的，但又不 equals，也没有比较性，因此在比较时就会到 compare() 方法的最后一步，使用内存地址进行比较，导致出现不稳定的现象。

为什么说使用内存地址比较会出现不稳定的现象呢？

假设在哈希表的桶中已经存放了一棵红黑树，同时在红黑树的左子树中有一个 Key 对象，名叫 A，A 的 value 为 1。这时候新创建一个 Key 对象，名叫 B，B 的 value 也是 1，此时想要查询当前 HashMap 中是否存在以 B 为 key 的数据。由于 Key 类中定义了哈希值的计算方法， A 和 B 的哈希值都是一样的。根据前面的分析， 会在 A 所在的红黑树中进行搜索查找。

假设运气好， B 的内存地址的哈希值比根节点的内存地址的哈希值要小，然后又一路比较，最后恰好与 A 进行比较，A 和 B 的哈希值一样，进行 equals 比较，它们的 value 又一样，表明它俩 equals。就是说，当前 HashMap 中 存在 以 B 为 key 的数据。😁

假设运气不好， B 的内存地址的哈希值比根节点的内存地址的哈希值要大，或者比根节点的内存地址的哈希值要小，但在一路向下比较的时候出了岔子，导致找到叶子节点（非空，不是指红黑树中假想的叶子节点）时，也没有发现一个节点的 value 与 B 的 value 相等。就是说，当前 HashMap 中 不存在 以 B 为 key 的数据。😔

这也太离谱了吧？比较节点还得靠运气？运气好就能找到，运气不好还找不到了？😡

这就是因为比较内存地址的哈希值带来的危害，需要对其进行修复。

2.7 方法修改

因为是比较方法 compare() 出现的问题，放弃该方法的使用，但是代码中多处使用了 compare() 方法，需要对使用了 compare() 方法的地方进行改写。

有两个地方使用了 compare() 方法：

1. 根据 key 获取值 get() （查询当前映射是否存在某个 key 的 containsKey()）
2. 添加元素 put()

修改优化 node() 方法

在第一种情况里，主要使用了 node() 方法，该方法是 查询映射中以 key 为键的节点 ，如果存在返回那个节点，否则返回 null。

以前的 node() 方法中，使用了 compare() 方法来对两个节点进行比较。

这里简单说一下为什么要使用 compare() 方法进行比较：因为需要根据 key 来获取值，知道 key 就可以知道求得 key 的哈希值，然后自然地得到这个 key 对应的哈希表索引。但并不是这个索引对应的值就是目标值，因为可能发生哈希冲突，这个索引对应的桶内有一棵红黑树，需要用当前的 key 与红黑树中节点的 key 进行比较，遍历红黑树查询是否存在当前 key 对应的值（value）。

因为 compare() 方法存在弊端，放弃使用该方法，需要改写 node() 方法，达成上面的描述。

实现也很简单，基本相当于将 compare() 中的代码复制过来，但是当两个 key 出现「哈希值相等，不具备可比较性，也不 equals」的情况时，不能使用内存地址进行比较，而是采取 扫描 整棵红黑树的方式进行比较，在这其中会使用到递归。

当先扫描 node.right 未得到满意的结果时，进而扫描 node.left，其实在扫描 node.left 时就是将 node.left 传入了方法 node(Node<K, V> node, K k1) 中。根据这个原理，对方法进行优化，直接使 node = node.left 以减少递归次数。

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556// 主要使用的方法
private Node<K, V> node(K key) {
    Node<K, V> root = table[index(key)];
    // 递归查找
    return root == null ? null : node(root, key);
}

// 递归的方法
// 根据 key 查询节点
private Node<K, V> node(Node<K, V> node, K k1) {
    int h1 = k1 == null ? 0 : k1.hashCode();
    // 存储查找结果
    Node<K, V> result = null;
    while (node != null) {
        int h2 = node.hash;
        K k2 = node.key;
        // 先比较哈希值
        /*
         * int cmp = h1 - h2;
         * 使用减法比较大小是不靠谱的，因为 int 可能会溢出，减去一个负数
         */
        if (h1 > h2) {
            node = node.right;
        } else if (h1 < h2) {
            node = node.left;
            // 哈希值相等，是否 equals
        } else if (Objects.equals(k1, k2)) {
            return node;
            // 哈希值相等，但不equals，是否有可比较性
        } else if (k1 != null && k2 != null
                   && k1.getClass() == k2.getClass()
                   && k1 instanceof Comparable) {
            int cmp = ((Comparable) k1).compareTo(k2);
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {
                return node;
            }
            // 哈希值相等，不equals，也不具备可比较性，使用扫描（递归）
        } else if (node.right != null
                   && (result = node(node.right, k1)) != null) {
            return result;
        } else { // 只能往左边找
            node = node.left;
        }
        //            } else if (node.left != null
        //                    && (result = node(node.left, k1)) != null) {
        //                return result;
        //            } else {
        //                return null;
        //            }
    }
    return null;
}

修改优化 put() 方法

put() 方法中也使用了 compare() 方法，放弃使用 compare() 方法，并对 put() 进行改写。改写使用的方式与原来的 compare() 方法差不多，但也有些变化。如果不存在参数中传递的 key 时，还是只能使用内存地址比较。

为了不过多的修改代码，还需要注意修改的方式，注意理解代码中局部变量 node 与 result 的关系和区别。

由于舍弃 compare() 方法，引入扫描的机制，但需要注意的是，直接像 node(Node<K, V> node, K k1) 方法一样进行扫描会存在重复扫描的情况。

假设新插入一个映射 A，A 会与当前映射中其他映射发生哈希冲突，且发生冲突的桶中的红黑树节点的 key 的哈希值相等，但不 equals，它们也没有可比较性，映射 A 的 key 亦是如此。这时就会扫描整棵红黑树查看是否存在节点的 key 与 A 的 key 相等，如果存在就覆盖，不存在就比较当前红黑树根节点 key 与 A 的 key 内存地址的哈希值，确定 A 的插入位置。

又假设根节点 key 内存地址的哈希值较大，那么 A 的插入位置就会在当前红黑树的左子树。但这只是第一步，还要充分确定 A 的插入位置。由于循环，又会进行一系列判断，并扫描当前红黑树的左子树，扫描当然是无果的，因为最开始已经扫描了一遍，最后会比较根节点的左子节点的 key 与 A 的 key 内存地址的哈希值，进一步确定 A 的插入位置。

重复以上操作，直到确定 A 的插入位置。

在确定位置的过程中，发现对这棵红黑树进行了多次且不必要的扫描，降低了效率。其实只需要进行一次扫描，后续比较内存地址的哈希值即可。因此可以引入一个成员变量 searched 来表示是否扫描了红黑树搜索了 A 的 key，以达到增加效率的目的。

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182@Override
public V put(K key, V value) {
    int index = index(key);
    // 取出 index 位置的红黑树根节点
    Node<K, V> root = table[index];
    if (root == null) {
        root = new Node<>(key, value, null);
        table[index] = root;
        size++;
        afterPut(root);
        return null;
    }
    // 根节点不为空时，产生哈希冲突
    // 添加新的节点到红黑树
    Node<K, V> parent = root;
    Node<K, V> node = root;
    int cmp = 0;
    K k1 = key;
    int h1 = k1 == null ? 0 : k1.hashCode();
    Node<K, V> result = null;
    boolean searched = false; // 是否已经搜索过 key
    // 循环方式从 while 变为 do...while
    do {
        parent = node;  // 保存父节点
        K k2 = node.key;
        int h2 = node.hash;
        if (h1 > h2) {
            cmp = 1; // cmp > 0，向右遍历
        } else if (h1 < h2) {
            cmp = -1; // cmp < 0，向左遍历
        } else if (Objects.equals(k1, k2)) {
            cmp = 0;
        } else if (k1 != null && k2 != null
                   && k1.getClass() == k2.getClass()
                   && k1 instanceof Comparable) {
            cmp = ((Comparable) k1).compareTo(k2);
        } else if (searched) { // 已经扫描了
            cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
        } else { // searched == false 还没扫描，先扫描再根据内存地址大小左右
            if ((node.left != null
                 && (result = node(node.left, k1)) != null)
                || (node.right != null
                    && (result = node(node.right, k1)) != null)) {
                // 已经存在这个 key ，进行覆盖
                // 需要覆盖的是 result，为了代码复用，使 node = result
                node = result;
                cmp = 0;
            } else { // 不存在这个 key 时，使用内存地址比较
                searched = true;
                cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
            }
        }

        if (cmp > 0) {
            node = node.right;
        } else if (cmp < 0) {
            node = node.left;
        } else { // 相等
            node.key = key; // 相等时覆盖
            V oldValue = node.value;
            node.value = value;
            /**
             * 到这一步时，是两个 key equals
             * 表明两个 key 的哈希值一定相等
             * 因此，可以不覆盖哈希值：
             * node.hash = h1;
             */
            return oldValue;
        }
    } while (node != null);
    // 看看插入到父节点的哪个位置
    Node<K, V> newNode = new Node<>(key, value, parent);
    if (cmp > 0) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }
    size++;
    // 添加节点后的处理 传入参数类型为Node
    afterPut(newNode);
    return null;
}

2.8 compareTo

尽管放弃使用 compare() 方法，并对 node() 方法和 put() 方法进行了改写、优化，但是这其中依旧存在着问题。

发现问题

假设现在又有一个类 Person，这个类不仅重写 equals() 方法，还实现了 Comparable 接口，代码如下：

1234567891011121314151617181920212223242526272829303132333435363738public class Person implements Comparable<Person> {
    private int age;
    private float height;
    private String name;

    public Person(int age, float height, String name) {
        this.age = age;
        this.height = height;
        this.name = name;
    }

    @Override
    public int hashCode() {
        int hashCode = Integer.hashCode(age);
        hashCode = hashCode * 31 + Float.hashCode(height);
        hashCode = hashCode * 31 + (name != null ? name.hashCode() : 0);
        return hashCode;
    }

    @Override
    public boolean equals(Object obj) { // 是否相等
        if (obj == this) return true;
        if (obj == null || obj.getClass() != getClass()) return false;
        Person person = ((Person) obj);
        return person.age == age && person.height == height
               && valueEquals(person.name, name);
    }

    private boolean valueEquals(Object v1, Object v2) {
        return v1 == null ? v2 == null : v1.equals(v2);
    }

    // age 较大的对象更大
    @Override
    public int compareTo(Person o) { // 比大小
        return age - o.age;
    }
}

equals() 方法用于判断实例对象们是否相等，而 compareTo() 方法用于比较这个实例对象们的大小。

大小相等，并不代表这两个对象相等，就像给出的示例代码一样，大小相等只表示这两个对象的 age 相等，但它们其他的属性可能不相等。

在二叉搜索树中，节点一定是具有可比较性的，要么实体类实现 Comparable 接口，要么自定义比较器，因此可以仅靠比较大小就确定节点的位置（大小相等就可以覆盖）。但在 HashMap 中不是这样的，对于 HashMap 中的节点，它们的可比较性并不是必须的，这就表明对象的大小相等时是不能覆盖的，有且仅当两个对象 equals 时才可以进行覆盖。

现有一段测试代码，输出结果已经注释出来：

123456static void test6() {
    Person p1 = new Person(10, 1.7f, "jack");
    Person p2 = new Person(10, 1.8f, "rose");
    System.out.println(p1.equals(p2)); // false
    System.out.println(p1.compareTo(p2)); // 0
}

将 p1、p2 对象作为 Map 的 key，value 任取，先后存入 HashMap 中。

根据先前编写的代码，先判断 p1、p2 是否 equals，显然是不 equals 的。然后发现两个具有可比较性，使用 compareTo() 方法进行比较，由于 Person 类中重写了 compareTo() 方法，这一比较，p1 和 p2 的大小是相等的，就会令 cmp = 0，从而使用 p2 覆盖 p1，这显然不是期望的那样。

因此，需要排除当两个 key 大小相等就进行覆盖的操作。

问题解决

上述所说的情况在 node() 方法和 put() 方法中都存在，需要一一进行解决。

解决方法就是当两个 key 大小相等时，不进行覆盖操作，也不进行其他操作，即：不进行任何操作，但是会落入下一个判断，进行全树扫描。

修改代码如下：

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657@Override
public V put(K key, V value) {
    // 省略其他代码
    // --snip--

    if (Objects.equals(k1, k2)) {
        cmp = 0;
    } else if (k1 != null && k2 != null
               && k1.getClass() == k2.getClass()
               && k1 instanceof Comparable
               && (cmp = ((Comparable) k1).compareTo(k2)) != 0) {
        // 此时 k1、k2一定不为同一个对象，因此在这进行比大小
        // cmp 结果 > 0 < 0 == 0
        // cmp == 0 时，不进行操作，直接前往下一个判断
    } else if (searched) { // 已经扫描了
        cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
    } else { // searched == false 还没扫描，先扫描再根据内存地址大小左右
        if ((node.left != null
             && (result = node(node.left, k1)) != null)
            || (node.right != null
                && (result = node(node.right, k1)) != null)) {
            // 已经存在这个 key ，进行覆盖
            // 需要覆盖的是 result，为了代码复用，使 node = result
            node = result;
            cmp = 0;
        } else { // 不存在这个 key 时，使用内存地址比较
            searched = true;
            cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
        }
    }
    // 省略其他代码
    // --snip--
}

private Node<K, V> node(Node<K, V> node, K k1) {
    // 省略其他代码
    // --snip--
    
    if (Objects.equals(k1, k2)) {
        return node;
        // 哈希值相等，但不equals，是否有可比较性
    } else if (k1 != null && k2 != null
               && k1.getClass() == k2.getClass()
               && k1 instanceof Comparable
               && (cmp = ((Comparable) k1).compareTo(k2)) != 0) {
        // 此时已排除 cmp == 0 的情况
        node = cmp > 0 ? node.right : node.left;
        // cmp == 0 时，不进行操作，直接前往下一个判断
        // 哈希值相等，不equals，也不具备可比较性，使用扫描（递归）
    } else if (node.right != null
               && (result = node(node.right, k1)) != null) {
        return result;
    } else { // 只能往左边找
        node = node.left;
    }

}

2.9 深度理解

在前几节花了大量的精力编写、优化 node() 方法和 put() 方法，在这两个方法中出现了许多情况，同时也产生了很多的 if 判断，由此就可以产生一些疑问：那么多的判断有必要吗？如果有必要又有什么用呢？

首先要清楚进行了那些判断：

• 哈希值的比较
• 哈希值相等的情况下，进行 equals 判断
• 前两种比较无果的情况下，判断 k1、k2 有无可比较性，然后使用 compareTo() 进行比较
• 前三种比较无果的情况下，在红黑树中进行 k1 的扫描

可以在 put() 方法中去掉第一种和第三种判断，只使用第二种和第四种的判断，同时在 node() 方法中也要移除第一种和第三种判断。那这又是为什么呢？😦

在实现 put() 方法和 node() 方法时，内部存在相似的逻辑判断，这是有意为之的，使用相似的逻辑判断可以减少判断次数。如果判断逻辑不一样， 比如 node() 方法中先进行 equals 判断，再进行哈希值的比较，在 put() 方法中恰好在第一步哈希值的比较中就得出结果，那么后续获取元素时就会多进行一次判断。

重回主题，去掉这两种判断后不会影响 HashMap 的功能，依旧可以正常插入元素、获取元素，但是会带来效率的损失，比如使用 HashMap 来统计单词数（共 1072799 个存在重复的单词）：

耗时两分钟，最终统计结果：共有 514483 个不同的单词。

然后在 put() 方法和 node() 中重新添加哈希值的比较，再次进行统计（共 1072799 个存在重复的单词）：

耗时只用了半秒钟，效率得到了巨大的提升。

这是因为单词数量巨大，大量的单词之间并不 equals，如果没有哈希值的比较进行判断，最终就会进行全节点扫描，而扫描会消耗大量的时间；如果一开始就有哈希值的比较，直接使用单词的哈希值就可以减少一半的搜索量，从而使效率得到巨大的提升。😳

最后将第三种判断也添加上去，再次进行测试时，发现耗时可能出现耗时增加的情况。不要慌张！ 这是正常情况！😎 耗时增加可能只是数据量不够多的原因，如果数据量足够大，可以看出耗时的减少。增加判断规则后，会减少全节点扫描的情况，效率会得到增加。

下图是添加第三种判断后的耗时（开始忘记截图，后面才发现，不要吐槽为啥时间差那么多 😂）：

Q & A

Q1： 为什么要先比较哈希值，再进行 equals 判断？

A1：当元素数量很多时（比如 10w 个），此时新添加一个元素，并且这个元素的 key_1 在现在的 HashMap 中并不存在，也就是哈希表中不存在与新添加元素的 key_1 equals 的 key_2。如果先 equals 会多进行一次判断，一般的场景下，添加进去的大多数 key 与原 HashMap 中的 key 都是不 equals 的，先比较哈希值就可以排除一大半的元素比较。

Q2：在 put() 方法中最后的判断会使用 key 的内存地址进行比较，但是在 node() 方法中又没有使用内存地址进行查询，那么使用内存地址进行比较是否显得多余？

A2：首先需要说明为什么 node() 方法中没有使用内存地址进行查询，并不是不使用，而是不能使用，因为内存地址在不同的环境中可能是不一样的，如果使用内存地址进行查询可能会造成无法预料的结果，因此在 node() 方法中使用的是全节点扫描。回到正题，put() 方法中最后确实可以不使用 key 的内存地址进行比较，甚至可以写死 cmp，直接使 cmp = 1; 或者 cmp = -1;，但是这样做会使红黑树插入节点后的调整（经常调用 afterPut() 方法）变得频繁，进而降低效率。因此需要在这里指定一个规则的。

那么使用随机数来指定可以吗？比如 cmp = Math.random() > 0.5 ? -1 : 1;，单从实现的角度讲是可以的，但是为了方便使用人员调试，还是使用一种明确、显式的规则更好，因此就选择使用内存地址进行比较。

2.1 0 哈希调整

在之前编写代码中有这样两个方法：

123456789private int index(K key) {
    if (key == null) return 0;
    int hash = key.hashCode();
    return (hash ^ (hash >>> 16)) & (table.length - 1);
}

private int index(Node<K, V> node) {
    return (node.hash ^ (node.hash >>> 16)) & (table.length - 1);
}

在这两个方法中，node.hash ^ (node.hash >>> 16) 被称为「扰动计算」，而这两个方法中都书写了扰动计算，使代码显得很臃肿、复杂，可以对代码进行优化、提取公共代码。

当 key 已经确定时，那么它的哈希值也已经确定了。因此可以在创建节点对象 Node 时就将经过扰动计算的哈希值作为对象的属性值：

12345678public Node(K key, V value, Node<K, V> parent) {
    this.key = key;
    int hash = key == null ? 0 : key.hashCode();
    // 扰动计算
    this.hash = hash ^ (hash >>> 16);
    this.value = value;
    this.parent = parent;
}

既然哈希值是确定的，而哈希表容量也是确定的，为什么不直接计算出索引呢？直接计算出索引岂不是更好？在这 里是不能直接计算出索引的，因为哈希表的容量在一定条件下是要进行扩容的，就是说 table.length 是会改变的。具体是怎么扩容的将会在下面的内容介绍！ 😜

然后可以编写一个私有的方法 hash(K key)，这个方法通过传递一个参数 key，然后返回经过扰动计算后的哈希值：

12345private int hash(K key) {
    if (key == null) return 0;
    int hash = key.hashCode();
    return hash ^ (hash >>> 16);
}

再然后对 index() 方法进行改写：

12345678private int index(K key) {
    return hash(key) & (table.length - 1);
}

private int index(Node<K, V> node) {
    // return (node.hash ^ (node.hash >>> 16)) & (table.length - 1);
    return node.hash & (table.length - 1);
}

最后，对一些使用到 Node 的 hash 属性值的代码进行改写：

⚠️ 警告，以下涉及大量代码，请注意折叠！ ⚠️

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123// 根据 key 查询节点
private Node<K, V> node(Node<K, V> node, K k1) {
    int h1 = hash(k1); // 对 k1 进行扰动计算
    // 存储查找结果
    Node<K, V> result = null;
    int cmp = 0;
    while (node != null) {
        int h2 = node.hash;
        K k2 = node.key;
        // 先比较哈希值
        if (h1 > h2) {
            node = node.right;
        } else if (h1 < h2) {
            node = node.left;
        } else if (Objects.equals(k1, k2)) {
            return node;
        } else if (k1 != null && k2 != null
                   && k1 instanceof Comparable
                   && k1.getClass() == k2.getClass()
                   && (cmp = ((Comparable) k1).compareTo(k2)) != 0) {
            node = cmp > 0 ? node.right : node.left;
        } else if (node.right != null
                   && (result = node(node.right, k1)) != null) {
            return result;
        } else { // 只能往左边找
            node = node.left;
        }
    }
    return null;
}

@Override
public V put(K key, V value) {
    int index = index(key);
    // 取出 index 位置的红黑树根节点
    Node<K, V> root = table[index];
    if (root == null) {
        root = new Node<>(key, value, null);
        table[index] = root;
        size++;
        afterPut(root);
        return null;
    }
    // 根节点不为空时，产生哈希冲突
    // 添加新的节点到红黑树
    Node<K, V> parent = root;
    Node<K, V> node = root;
    int cmp = 0;
    K k1 = key;
    int h1 = hash(k1); // 对 k1 进行扰动计算
    Node<K, V> result = null;
    boolean searched = false; // 是否已经搜索过 key
    // 循环方式从 while 变为 do...while
    do {
        parent = node;  // 保存父节点
        K k2 = node.key;
        int h2 = node.hash;
        /*
         * 先比较哈希值，再进行 equals
         * 当我们元素数量很多时(10w个)，这个时候新添加一个元素
         * 这个元素的key在现在的HashMap中并不存在
         * 如果先 equals 会多进行一次判断
         * 一般的场景的，添加进去的大多数 key 也都是不equals的
         * 因此先比较哈希值就可以排除一大半的元素比较
         */
        if (h1 > h2) {
            cmp = 1;
        } else if (h1 < h2) {
            cmp = -1;
        } else if (Objects.equals(k1, k2)) {
            cmp = 0;
        } else if (k1 != null && k2 != null
                   && k1 instanceof Comparable
                   && k1.getClass() == k2.getClass()
                   && (cmp = ((Comparable) k1).compareTo(k2)) != 0) {

        } else if (searched) { // 已经扫描了
            cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
        } else { // searched == false 还没扫描，先扫描再根据内存地址大小左右
            if ((node.left != null
                 && (result = node(node.left, k1)) != null)
                || (node.right != null
                    && (result = node(node.right, k1)) != null)) {
                // 已经存在这个 key ，进行覆盖
                // 需要覆盖的是 result，为了代码复用，使 node = result
                node = result;
                cmp = 0;
            } else { // 不存在这个 key 时，使用内存地址比较
                searched = true;
                //                    cmp = Math.random() > 0.5 ? -1 : 1;
                cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
            }
        }

        if (cmp > 0) {
            node = node.right;
        } else if (cmp < 0) {
            node = node.left;
        } else { // 相等
            node.key = key; // 相等时覆盖
            V oldValue = node.value;
            node.value = value;
            /*
             * 到这一步时，是两个 key equals
             * 表明两个 key 的哈希值一定相等
             * 因此，可以不覆盖哈希值：
             * node.hash = h1;
             */
            return oldValue;
        }
    } while (node != null);
    // 看看插入到父节点的哪个位置
    Node<K, V> newNode = new Node<>(key, value, parent);
    if (cmp > 0) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }
    size++;
    // 添加节点后的处理 传入参数类型为Node
    afterPut(newNode);
    return null;
}

（又是这两大串代码 😖）

到此， HashMap 的基本实现就完成了，功能测试也基本没有问题。

但是仍有可以优化的地方！ 👇

3. 优化完善

3.1 装填因子

问题由来

向自行设计的 HashMap 中插入大量的数据（10w？或 100w）时，因为哈希函数的计算方式以及哈希表的默认容量（默认容量 16），会导致频繁出现哈希冲突，并在每个桶中的红黑树也会存在大量节点，导致红黑树的高度变得异常地高。

需要规避这种情况，不能让桶中的红黑树高度变得很高，因为在高度很高而又要进行全节点扫描时，会造成效率的巨大损失。

因此需要指定一个标准，在数据量达到一定值时，对哈希表进行扩容，从而让红黑树的高度不那么高，提高搜索效率。

那这个标准是什么？

装填因子

装填因子（Load Factor）：节点总数量 / 哈希表桶数组的长度，也叫作 负载因子。

在 JDK 1.8 的 HashMap 中，如果装填因子超过 0.75，就会扩容为原来的两倍。

至于为什么选择 0.75 作为装填因子，网上有说是因为通过泊松分布计算出来的，其实这是不对的，两者没有必然联系，真实原因是：通过时间和空间上的权衡后，选择装填因子为 0.75（可查看 JDK 中 HashMap 的注释）。

3.2 扩容思路

既然需要扩容，那么在创建了新的桶数组后，就要将原来桶数组中的数据搬到新的桶数组中。

首先想到一种方式：遍历原桶数组中的每个元素，其中的每个元素都是红黑树的根节点，然后根据这些根节点使用层序遍历来遍历整个红黑树，将遍历的节点使用 put() 方法插入到新的桶数组中（size 记得清零）。

但是！这是一个 极其煞笔的做法 ！为什么？

效率极低！

因为将旧桶数组中的元素使用 put() 方法重新添加到新创建的新桶数组中，就需要重新构造新的 Node 实例对象，会浪费大量的内存。为什么不重新利用以前的 Node 节点对象呢？👀

那么应该怎么挪动数据呢？

直接将整棵树挪到新的桶数组中（将根节点放到新的桶数组中）？

这种做法是肯定不行的，需要 将红黑树中每个节点都挪过去 。

因为进行扩容后，table.length 会发生变化，节点的索引值可能会发生变化。

123456private int index(Node<K, V> node) {
    // 重复利用原先的节点
    // node.hash 不会发生变化，但table.length会发生变化
    // 最终结果就有可能发生变化
    return node.hash & (table.length - 1);
}