封面画师：ツチヤ封面ID：82542726

本文参考视频：小马哥教育(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)。

根据上面的需求，我们可以暂时的设计如下：

private 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 有“剁碎”的意思。

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

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

1
2
3

put("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，经过哈希函数计算出相同的结果（索引）。如：

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

1、开放定址法（Open Addressing）

按照一定的规则（线性探测、平方探测）向其他地址进行探测，直到遇到空桶

2、再哈希法（Re-Hashing）

设计多个哈希函数

3、链地址法（Separate Chaining）

比如通过链表将同一个索引的元素串起来

JDK 1.8 解决方法

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

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

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

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

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

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

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

1
2
3

put("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 的哈希值跟数组的大小进行相关运算，生成一个索引值，如：

1
2
3

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

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

1
2
3

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

【& 位运算规则：同为1取1，否则取0。即： 1011 & 1010 = 1010】

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

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

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

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

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

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

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

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

11001010 & 1111 ：

  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

1
2
3

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

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

1
2
3

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

long与double的哈希值

int 类型占 4 个字节，即： 32位。但是 long 类型是占 8 个字节的，即： 64 位。在 Java 中，哈希值必须是 int 类型的，就是说 long 类型的哈希值只能是 32 位，那应该咋办？

有一种方法是选择 long 类型的前 32 位或者后 32 位作为哈希值。但是这种方法有一个问题，因为我们前面所说：“尽量让 key 的所有信息参与运算”。那我们应该怎么做？现给出一种方法：

1
2
3

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

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

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

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

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

PS ：异或运算：相同为 0 ，不同为 1。

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

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

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

字符串的哈希值

整数 5489 是如何计算出来的？

通过： 5 * 10³ + 4 * 10² + 8 * 10¹ + 9 * 10⁰

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

j * n³ + a * n² + c * n¹ + k * n⁰ ，这个等价于[ (j * n + a) * n + c ] * n + k

那么这个 n 是多少呢？在JDK中，乘数 n 为 31 ，那又为什么是 31 呢？

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

比如：

public class Main {
    public static void main(String[] args) {
        String string = "jack"; // 3254239
        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;

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

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

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

31 的探讨：

JVM优化原理： 31 * i = (2⁵ - 1) * i = i * 2⁵ - i = (i << 5) - i

31 不仅仅是符合 2ⁿ - 1，它还是一个奇素数（既是奇数，又是素数）。素数和其他树相乘的结果比其他方式更容易产生唯一性，减少哈希冲突。

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

常见类型计算总结

static 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，其属性与构造方法如下：

public 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;
    }
}

然后我们可以尝试实例化这个对象，并打印出哈希值：

static 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()方法，自定义计算方式：

@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

Q 1: 哈希值太大，整型溢出怎么办？

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

Q 2: 不重写 hashCode() 方法有什么后果？

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

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() 方法。

@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() 方法，如果对 key 这两个方法都没有实现呢？

对于非自定义类型的数据就按照我们前面所说的方法计算哈希值，而对于自定义类型的数据计算哈希值得到的结果与内存有关。同时，没有实现equals()时进行相等性比较，会默认比较内存地址。假设向一个 HashMap 插入下列三组数据，Person类中没有实现 hashCode()、 equals() 方法：

static 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” 的索引是一样的（假设！），但最终输出 HashMap 的长度还是 3 。虽然会发生哈希冲突，但是没实现equals()，相等性比较时使用的是内存地址进行比较，显然这三者的内存地址是不一样的，因此得到的 HashMap 长度也就是 3 。

只实现equals()方法

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

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

三者计算得到的哈希值不一样，但是经过哈希函数计算得到的索引可能是一样，可能不一样。如果索引一样，一般是 p1 与 p2 的索引一样，这时候发生哈希冲突，使用链地址法解决，又因为重写了equals()方法，很显然 p1 与 p2 是相等的，因此得到的 HashMap 长度是 2 。如果三者的索引都不一样，不会发生哈希冲突，那么得到的 HashMap 长度是 3 。

根据上面的说明，我们发现一个问题：没有实现hashCode()会导致不稳定。所谓不稳定指的就是两个对象的属性值是一样的，但是会不会覆盖是不一定的，可能覆盖也可能不覆盖。

只实现hashCode()方法

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

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

哈希函数计算后得到的索引与 p1、p2 一样
哈希函数计算后得到的索引与 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

总结

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

对于自定义类型的Person，有三个成员变量： age 、 name 和 height。假设我们认为两个对象的 age 和 name 相等时，它们就相等，因此在重写的hashCode()、 equals() 方法中必须包含 age 和 name 。

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

重写的hashCode()、 equals() 方法中包含哪些成员变量是根据需求而定的。

2. 初步实现

在前文，我们已经介绍了 JDK8 中 HashMap 的实现，接下来我们也将自己实现一个 HashMap 。

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

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

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

接下来，我们自己实现一个简单的 HashMap ！😎

2.1 清空映射

简单方法实现

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

在完善clear()方法之前，我们可以先完善几个简单的方法。在实现 HashMap 时，肯定需要一个表示 Map 长度的成员变量，我们定这个成员变量为 size。根据这个成员变量，可以只实现两个方法：

public 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，并设置为内部类，最后可以完善一些构造函数。

public 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。

@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 ，可以直接进入循环以减少判断次数。

@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 位置的红黑树根节点的索引，用于获取该索引下的红黑树跟节点，但我们还没有编写这个方法，该方法具体如下：

private 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 的哈希值：

private 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;
    }
    
    // 省略其他方法
    .....
}

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

/**
 * @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()方法也需要进行修改：

@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()方法代码如下（仍有不足，稍后进行修改）：

/**
 * @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成员变量。但是哈希表的桶中存储的就是红黑树的根节点，我们可以编写一个方法，这个方法可以根据红黑树节点来获取哈希表的索引：

1
2
3

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

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

然后我们可以使用index()方法来修改afterRotate()方法：

private 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，他们仨的索引都是一样的。

测试代码：

static 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()方法。

node()方法：

private 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;
}

然后轻松地实现get()方法，并且还可以实现containsKey()方法：

@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 来进行删除的，而我们在自己编写的时候需要根据节点来进行删除，因此我们需要对原删除方法进行重载：

private 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()复制到当前类中：

private 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;
}

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

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

2.6 发现问题

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

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

先编写一个模型类Key：

public 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 + ")";
    }
}

然后编写一个测试类，使用刚刚新创建的模型类进行测试：

static 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()方法看一下红黑树的节点：

map.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()方法的问题。

private 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() （查询当前映射是否存在某个 keycontainsKey()）

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 以减少递归次数。

// 主要使用的方法
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，以达到增加效率的目的。

@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接口，代码如下：

public 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 时才可以进行覆盖。

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

static 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实体类中重写的方法，这一比较，p1 和 p2 的大小是相等的，就会令cmp = 0，从而使用 p2 覆盖 p1 ，这显然不是我们想要的。

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

问题解决

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

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

修改代码如下：

@Override
public V put(K key, V value) {
    // 省略其他代码
    ......
    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);
        }
    }
    // 省略其他代码
    ......
}

private Node<K, V> node(Node<K, V> node, K k1) {
    // 省略其他代码
    ......
        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 判断，由此就可以产生一些疑问：那么多的判断有必要吗？如果有必要又有什么用呢？

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

1、哈希值的比较

2、哈希值相等的情况下，进行 equals 判断

3、前两种比较无果的情况下，判断k1、k2有无可比较性，然后使用 compareTo() 进行比较

4、前三种比较无果的情况下，在红黑树中进行 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.10 哈希调整

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

private 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的时候就将经过扰动计算的哈希值作为对象的属性值，因此可以改写静态嵌套类 Node<K, V> 的构造方法：

public 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 ，然后返回经过扰动计算后的哈希值：

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

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

private 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属性值的代码进行改写：

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

// 根据 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()方法重新添加到新创建的新桶数组中，就需要重新 new 新的 Node 节点对象，这样会浪费大量的内存。为什么不重新利用以前的 Node 节点对象呢？👀

那么应该怎么挪动数据呢？直接将整棵树挪到新的桶数组中（将根节点放到新的桶数组中）？这种做法是肯定不行的，我们需要将红黑树中每个节点都挪过去 。因为进行扩容后，table.length会发生变化，节点的索引值可能会发生变化。

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

那又是怎样的变化呢？👇

索引的变化

前文已经分析过，table.length需要是 2 的次幂，然后进行减 1 运算后，table.length - 1的二进制数全是 1 。

假设最开始时table.length - 1的二进制数为 11，即：桶数组容量为 2² = 4 ，node.hash的二进制数为1010：

1010
& 11
-----
  10

然后桶数组容量扩容为 2³ = 8后：

1010
&111
----
 010

我们发现扩容后重新计算的索引并没有发生变化。那我们再举一个例：

node.hash的二进制数发生变化，为1110，最开始还未发生扩容时：

1110
& 11
----
  10

然后桶数组容量扩容为 8 时：

1110
&111
----
 110

这下扩容后重新计算的索引就发生了变化。

当扩容为原来容量的2倍时，节点的索引变化有两种情况：

1、保持不变

2、新的索引 = 旧索引 + 旧容量

3.3 扩容实现

我们进行扩容时，需要将原哈希表中桶内的每一个红黑树节点都挪到新的哈希表中，那有个小疑问：每个节点都要挪到新的哈希表中，那效率岂不是会很差？

效率是会降低，但是扩容后，桶数组容量增加，发生哈希冲突的概率减小，这样的挪动是为了以后的效率，而这是值得的。

调整大小

前面提到了装填因子的概念，因此我们需要在HashMap类中添加一个常量，表示默认装填因子：

public class HashMap<K, V> implements Map<K, V> {
    // 默认装填因子
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
}

接下来就可以编写调整大小的方法resize()：

1、计算的填装因子小于等于默认的填装因子时，直接返回；

2、创建一个新的桶数组，容量是原来的两倍（为啥是两倍？容量是 2 次幂没忘吧😒）

3、将原数组的每个节点进行层序遍历然后挪动

resize()方法具体代码如下：

private void resize() {
    // 装填因子 <= 0.75
    if (size / table.length <= DEFAULT_LOAD_FACTOR) return;

    Node<K, V>[] oldTable = table;
    table = new Node[oldTable.length << 1];

    Queue<Node<K, V>> queue = new LinkedList<>();
    for (int i = 0; i < oldTable.length; i++) {
        if (oldTable[i] == null) continue;
        queue.offer(oldTable[i]);
        while (!queue.isEmpty()) {
            Node<K, V> node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            // 节点挪动，可以思考下为啥要把挪动方法放在这里
            moveNode(node);
        }
    }
}

节点挪动

在调整大小的代码中使用了节点挪动方法moveNode()，在当前HashMap类中是没有这个方法的，因此我们需要编写这个方法：

1、因为是从原桶数组将节点挪动到新的数组中，所以需要将节点的属性重置 。真是因为这里重置了节点属性，因此在resize()方法中将挪动方法放到了最后。

2、接下来的代码与put()方法中的代码类似，但也存在着些许差异：

部分赋值语句、参数名进行修改
由于是挪动数据，当前映射的size并不需要像put()方法中一样进行加一
由于是挪动数据，也不需要新创建Node对象，直接使用传递的数据即可
删除 equals 判断，因为节点原来就是存在于映射中的，原映射中不可能存在两个相互 equals 的节点
删除递归搜索，原因与上一条一样
删除 cmp = 0 时进行的覆盖，在挪动节点时，cmp 不可能等于 0，原因同上
最后记得设置一下挪动节点的 parent 属性

总结一下，moveNode()方法与put()方法类似，但是由于挪动的是原本就存在于映射中的节点，因此在新桶数组中不可能出现节点相互 equals 或者 cmp = 0 的情况，我们只需要确定挪动节点在新桶数组中的位置即可。基于此，需要删除一些代码以减少判断，提高效率。

moveNode()方法具体代码如下：

private void moveNode(Node<K, V> newNode) {
    // 重置清空
    newNode.parent = null;
    newNode.left = null;
    newNode.right = null;
    newNode.color = RED;

    int index = index(newNode);
    // 取出 index 位置的红黑树根节点
    Node<K, V> root = table[index];
    if (root == null) {
        root = newNode;
        table[index] = root;
        afterPut(root);
        return;
    }
    // 添加新的节点到红黑树
    Node<K, V> parent = root;
    Node<K, V> node = root;
    int cmp = 0;
    K k1 = newNode.key;
    int h1 = newNode.hash;
    // 循环方式从 while 变为 do...while
    do {
        parent = node;  // 保存父节点
        K k2 = node.key;
        int h2 = node.hash;
        if (h1 > h2) {
            cmp = 1;
        } else if (h1 < h2) {
            cmp = -1;
            // 删除 equals，不可能存在相互 equals 的 key
        } else if (k1 != null && k2 != null
                && k1 instanceof Comparable
                && k1.getClass() == k2.getClass()
                && (cmp = ((Comparable) k1).compareTo(k2)) != 0) {
        } else { // 删除搜索，因为原桶数组的数据挪动过来不可能存在相等的
            cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
        }

        // 删除 cmp = 0 的情况，因为挪动过来的元素不能相等
        if (cmp > 0) {
            node = node.right;
        } else if (cmp < 0) {
            node = node.left;
        }
    } while (node != null);

    // 看看插入到父节点的哪个位置
    newNode.parent = parent;
    if (cmp > 0) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }

    // 添加节点后的处理 传入参数类型为Node
    afterPut(newNode);
}

扩容后单词统计耗时：

其实我们编写的 HashMap 中还有可以优化的地方：比如减少函数调用（染色的函数）等。

3.4 equals的规范

假设我现在有两个实体类，分别叫做 Key1 和 Key2 ，在这两个实体类中重写了equals()方法，但是重写的方法存在差异。然后我在一个测试方法中实例化这两个对象：

1 2	Key1 k1 = new Key1(1); Key2 k2 = new Key2(1);

然后调用 equals() 方法得到以下结果：

1 2	k1.equals(k2); // true k2.equals(k2); // false

真是因为重写方法存在的问题，导致了这样的结果。如果我们要使用这两个自定义对象作为 HashMap 的 key 时，就会出现不稳定的现象：

1
2
3

Map<Object, Integer> map = new HashMap<>();
map.put(k1,1);
map.put(k2,2);

在这种情况下，后添加的数据不会覆盖先添加的。

1
2
3

Map<Object, Integer> map = new HashMap<>();
map.put(k2,1);
map.put(k1,2);

在这种情况下，后添加的数据会覆盖先添加的。

这就是不稳定的现象，既然会出现不稳定的现象，难道是我们自己写的 HashMap 有问题？

当然没有问题，这是使用者的问题，是使用者自定义对象的equals()方法出了问题！😤

因此我们自己在重写equals()方法时一定要遵循一些规范！😒

equals的规范

在前文中已经说明，自定义对象作为 key 时，需要重写hashcode()和equals()方法。

equals()：用以判断 2 个 key 是否为同一个 key，重写equals()方法时需要遵守以下规范：

自反性：对于任何非 null 的 x，x.equals(x) 必须返回 true
对称性：对于任何非 null 的x、y，如果 y.equals(x) 返回 true ，x.equals(y) 也必须返回 true
传递性：对于任何非 null 的x、y、z，如果 x.equlas(y)、y.equals(z) 返回 true，那么 x.equals(z) 必须返回 true
一致性：对于任何非 null 的x、y，只要 equals 的比较操作在对象中所用的信息没有被修改，多次调用 x.equals(y) 就会一致地返回 true ，或者一致地返回 false 。就是说，假设我现在有一个实体类名为Person，其中重写了 equals() 方法，通过属性 name 进行 equals 判断，只要我 name 的属性值没有发生改变，那么equals()方法返回的结果就不能改变。
对于任何非 null 的x，x.euqals(null) 必须返回 false

3.5 选择与对比

我们使用自己编写的TreeMap和HashMap来统计一下单词数，比较一下两者的耗时：

结果很明显，两者的耗时相差很远，HashMap的效率、性能远好于TreeMap。

从时间复杂度来说，TreeMap 的增删改查都是 O(logn) 级别的，而使用哈希表实现的映射 HashMap 可以认定为 O(1) 级别的（装填因子的原因）。

二者抉择

HashMap的效率、性能远好于TreeMap，难道TreeMap就没用了吗？😕

当然不是！😎

以下情况可以选择TreeMap：元素具备可比较性且要求升序遍历（按照元素从小到大）

以下情况可以选择HashMap：只要要求无序遍历就选择 HashMap

3.6 取模运算

在编写哈希函数的时候，我们建议使用位运算 & 来计算以求得索引值。

如果我们执意要使用取模运算 % 来计算索引：建议把哈希表的长度设计为素数（质数），就像我们使用位运算要将哈希表的长度设计为 2 的次幂一样。

这样可以大大减小哈希冲突：

10 % 8 = 2			10 % 7 = 3
20 % 8 = 4			20 % 7 = 6
30 % 8 = 6			30 % 7 = 2
40 % 8 = 0			40 % 7 = 5
50 % 8 = 2			50 % 7 = 1
60 % 8 = 4			60 % 7 = 4
70 % 8 = 6			70 % 7 = 0

那要扩容应该怎么办呢？

下图列出了不同数据规模对应的最佳素数：

我们发现：每个素数略小于前一个素数的 2 倍，每个素数尽可能接近 2 的次幂（2ⁿ）

我们在设计时，可以把素数一栏的数据放到一个数组中，如果数据规模发生改变时，就可以启用数组中下一个数据作为桶数组的容量。

4. LinkedHashMap

在 HashMap 的基础上维护元素的添加顺序，使得遍历的结果是遵从添加顺序的。

比如，添加顺序为：

map.put("jack", 1);
map.put("rose", 2);
map.put("jim", 3);
map.put("tom", 4);

遍历结果的顺序是按照 jack — rose — jim — tom 的顺序遍历出来的。

4.1 节点创建

假设添加顺序为： 37、21、31、41、97、95、52、42、83

由于我们要实现LinkedHashMap，使遍历顺序按照添加顺序，那么必须要在原节点类Node上增加几个属性。

创建LinkedHashMap类，继承HashMap，然后在当前类中创建内部类LinkedNode，继承Node：

PS：记得前往HashMap类中将节点类Node的访问修饰符修改为protected。

public class LinkedHashMap<K, V> extends HashMap<K, V> {

    private static class LinkedNode<K, V> extends Node<K, V>{
        LinkedNode<K, V> prev;
        LinkedNode<K, V> next;

        public LinkedNode(K key, V value, Node<K, V> parent) {
            super(key, value, parent);
        }
    }
}

但是在HashMap中使用的某些方法中创建节点是通过 new Node() 完成的，无法在LinkedHashMap创建我们想要的LinkedNode。

针对这个原因，我们可以在HashMap中提供一个创建节点的方法：

1
2
3

protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {
    return new Node<>(key, value, parent);
}

然后将HashMap中创建节点的方法都改为调用这个方法，比如：

// 修改前
root = new Node(key, value, null);
// 修改后
root = createNode(key, value, null);

最后，在LinkedHashMap重写createNode()方法，就可以实现使用LinkedHashMap时创建的节点都是LinkedNode：

@Override
protected Node createNode(Object key, Object value, Node parent) {
    return new LinkedNode(key, value, parent);
}

4.2 方法改写

实现LinkedHashMap时，可以采用双向链表（对于单向链表访问效率更高）将节点串起来，因此需要在当前类中增加两个指针，分别表示头指针和尾指针：

public class LinkedHashMap<K, V> extends HashMap<K, V> {
    private LinkedNode<K, V> first;
    private LinkedNode<K, V> last;
    // 省略其他代码
}

串线

我们在上一步中已经把准备工作做得差不多了，接下来需要将节点们串在一起，方便后续遍历。

我们可以在创建节点的时候就将线串起来：

当创建的节点是第一个节点时，使头指针、尾指针都指向它。
当创建的节点不是第一个节点时，该节点就是最后一个节点。

@Override
protected Node createNode(Object key, Object value, Node parent) {
    LinkedNode node = new LinkedNode(key, value, parent);
    if (first == null) {
        first = last = node;
    } else {
        last.next = node;
        node.prev = last;
        last = node;
    }
    return node;
}

清空

因为引入了头尾指针，可以使用双向链表将添加的数据串起来，那么在清空映射时需要将头尾指针设置为null，不然映射无法被清空：

@Override
public void clear() {
    super.clear();
    first = null;
    last = null;
}

遍历

节点也串了起来，访问的时候就可以顺着链表访问即可。

@Override
public void traversal(Visitor<K, V> visitor) {
    if (visitor == null)  return;
    LinkedNode<K, V> node = first;
    while (node != null){
        if (visitor.visit(node.key, node.value)) return;
        node = node.next;
    }
}

存在

判断某个 value 是否存在也可以采取和遍历一样的方式：

@Override
public boolean containsValue(V value) {
    LinkedNode<K, V> node = first;
    while (node != null) {
        if (Objects.equals(value, node.value)) return true;
        node = node.next;
    }
    return false;
}

4.3 节点删除

节点添加很简单，只需要将创建节点的方法修改为调用createNode()方法创建即可。但是对于删除就不一样了，我们可以直接使用HashMap中删除节点的方法吗？

答案是否定的！因为我们在添加节点时按照添加顺序使用双向链表将节点都串了起来，使用 HashMap 中删除节点的方法时，只会删除红黑树中的节点，对于双向链表的节点并无作为。因此，我们还需要将双向链表的节点删除。

PS：前往HashMap中将remove(Node<K, V> node)方法的访问修饰符修改为protected。

然后在LinkedHashMap类中重写remove(Node<K, V> node)方法，删除双向链表中的节点：

@Override
protected V remove(Node<K, V> node) {
    if (node == null) return null;
    LinkedNode<K, V> linkedNode = ((LinkedNode<K, V>) node);

    LinkedNode<K, V> prev = linkedNode.prev;
    LinkedNode<K, V> next = linkedNode.next;
    if (prev == null) { // 删除双向链表的头结点时
        first = next;
    } else {
        prev.next = next;
    }
    if (next == null) { // 删除双向链表尾节点时
        last = prev;
    } else {
        next.prev = prev;
    }
    return super.remove(node);
}

这样就把删除方法写好了？😳

当然不可能啦，这么简单就写好了我还会开新的一节吗？😏

因为我们删除度为2的节点时，实际上真正删除的是它的前驱或后继节点，而传递的参数是被删除节点，我们所做的是将被删除节点在双向链表中的指向断开了，实际上应该断开其前驱或后继节点的指向。

因此我们还需要对代码进行修改。为了方便命名，我们将添加节点后修复红黑树的方法afterPut()重命名为fixAfterPut()，将删除节点后修复红黑树的方法afterRemove()重命名为fixAfterRemove()。

然后在HashMap中新编写一个方法afterRemove()，内部不书写任何代码：

1	protected void afterRemove(Node<K, V> removeNode) { }

将这个方法放在remove()方法最后，用于在 HashMap 的子类中重写。

protected V remove(Node<K, V> node) {
    // 省略其他的代码
    ......
    // 交给子类处理的代码
    afterRemove(node);
    return oldValue;
}

返回至LinkedHashMap中，删除前面重写的remove(Node<K, V> node)方法，重写afterRemove()方法：

@Override
protected void afterRemove(Node<K, V> removeNode) {
    LinkedNode<K, V> linkedNode = ((LinkedNode<K, V>) removeNode);

    LinkedNode<K, V> prev = linkedNode.prev;
    LinkedNode<K, V> next = linkedNode.next;
    if (prev == null) { // 删除双向链表的头结点时
        first = next;
    } else {
        prev.next = next;
    }
    if (next == null) { // 删除双向链表尾节点时
        last = prev;
    } else {
        next.prev = prev;
    }
}

你以为这样又完了？

当我们删除节点后，虽然将双向链表的引用正确删除了，但是访问顺序又发生了改变。比如在下图中，我们删除节点 31 后，37 会覆盖 31 ，原本 37 的内存会被销毁，但是这样访问顺序又发生了改变。

那么我们应该怎么做呢？交换一下链表中数据的位置就可以了：

注意：当删除度为2的节点node时，需要注意更换 node 与前驱 \ 后继节点的连接位置。

那么应该怎么交换呢？其实很简单，看下图： 👇

为了不重复书写代码，我们可以在 HashMap 给方法afterRemove()再添加一个参数：

/**
 * @param willNode   要被删除的节点
 * @param removeNode 真正被删除的节点
 */
protected void afterRemove(Node<K, V> willNode, Node<K, V> removeNode) {
}

然后在remove(Node<K, V> node)方法中也给出调整，定义一个局部变量willNode表示要被删除的节点：

protected V remove(Node<K, V> node) {
    if (node == null) return null;
    // 定义一个局部变量 willNode
    Node<K, V> willNode = node;
    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;
        }

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

最后在LinkedHashMap中，重写afterRemove()方法：

@Override
protected void afterRemove(Node<K, V> willNode, Node<K, V> removeNode) {
    LinkedNode<K, V> node1 = ((LinkedNode<K, V>) willNode);
    LinkedNode<K, V> node2 = ((LinkedNode<K, V>) removeNode);

    if (node1 != node2){ // 删除节点度为 2
        // 交换node1和node2在链表中的位置
        // 交换 prev
        LinkedNode<K, V> tmp = node1.prev;
        node1.prev = node2.prev;
        node2.prev = tmp;
        if (node1.prev == null) {
            first = node1;
        } else {
            node1.prev.next = node1;
        }
        if (node2.prev == null) {
            first = node2;
        } else {
            node2.prev.next = node2;
        }
        // 交换 next
        tmp = node1.next;
        node1.next = node2.next;
        node2.next = tmp;
        if (node1.next == null) {
            last = node1;
        } else {
            node1.next.prev = node1;
        }
        if (node2.next == null) {
            last = node2;
        } else {
            node2.next.prev = node2;
        }
    }

    LinkedNode<K, V> prev = node2.prev;
    LinkedNode<K, V> next = node2.next;
    if (prev == null) { // 删除双向链表的头结点时
        first = next;
    } else {
        prev.next = next;
    }
    if (next == null) { // 删除双向链表尾节点时
        last = prev;
    } else {
        next.prev = prev;
    }
}

到此，LinkedHashMap就基本完成了，其他的方法可以参考 HashMap 代码实现即可。

5. HashSet

HashMap都实现了，HashSet还不容易实现吗？

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

然后使用 HashMap 实现即可：

/**
 * @author 默烦
 * @date 2020/8/4
 */
public class HashSet<E> implements Set<E> {
    private HashMap<E, Object> map = new HashMap<>();

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

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public void clear() {
        map.clear();
    }

    @Override
    public boolean contains(E element) {
        return map.containsKey(element);
    }

    @Override
    public void add(E element) {
        map.put(element,null);
    }

    @Override
    public void remove(E element) {
        map.remove(element);
    }

    @Override
    public void traversal(Visitor<E> visitor) {
        map.traversal(new Map.Visitor<E, Object>() {
            @Override
            public boolean visit(E key, Object value) {
                return visitor.visit(key);
            }
        });
    }
}

那对于LinkedHashSet呢？那就是分分钟的事了：

public class LinkedHashSet<E> implements Set<E> {
    private LinkedHashMap<E, Object> map = new LinkedHashMap<>();

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

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public void clear() {
        map.clear();
    }

    @Override
    public boolean contains(E element) {
        return map.containsKey(element);
    }

    @Override
    public void add(E element) {
        map.put(element,null);
    }

    @Override
    public void remove(E element) {
        map.remove(element);
    }

    @Override
    public void traversal(Visitor<E> visitor) {
        map.traversal(new Map.Visitor<E, Object>() {
            @Override
            public boolean visit(E key, Object value) {
                return visitor.visit(key);
            }
        });
    }
}