阅读共识

散列=哈希，互换成立。

哈希表本质就是一个数组，具有索引和元素，其元素称为桶。

在 JDK 中，桶 采用 单向链表 或 红黑树 来存储，主要为了解决哈希冲突。

哈希表

Hash Table，哈希表，也叫散列表。一种可以通过 key 去寻找对应 value 的数据结构。它通过把 key 映射到表中一个位置，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

关键词经过哈希函数解析出一个数组索引，将数据值放入该索引的位置中。

put("jack",666)
put("rose",777)
put("kate",888)

利用哈希函数生成 key 对应的 index 【O(1)】

根据 index 操作定位数组元素 【O(1)】

添加、搜索、删除的流程都是类似的，哈希表就是【空间换时间】的典型应用

哈希表内部的数组元素，很多地方叫做 Bucket(桶)，整个数组叫 Buckets 或者 Bucket Array

如上图中的 777,888,666 这些叫做 Bucket

哈希冲突

Hash Collision，哈希冲突，也叫哈希碰撞。

2个不同的 key，经过哈希函数计算出相同的结果。

key1 != key2 但 hash(key1) = hash(key2)

解决哈希冲突办法

1. 开放定址法

   1. 按照一定规则向其他地址探测，直到遇到空桶

2. 再哈希法

   1. 设计多个哈希函数

3. 链地址法（用得最多）

   1. 比如通过链表将同一个 index 的元素串起来

哈希冲突是不可避免的，我们做的就是尽量减少哈希冲突，出现了哈希冲突我们也可以解决，比如链地址法。

JDK1.8

默认使用 单向链表 将元素串起来

在添加元素时，当 哈希容量 >= 64 且 单向链表节点数量 > 8 ，会由 单向链表 转为 红黑树 来存储元素。

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

因此，JDK1.8 中的哈希表是使用 链表+红黑树 解决哈希冲突。

map.put("a",40)
map.put("b",50)
map.put("c",60)

假设 abc 计算出的索引都为01，那数据都存在同一单向链表。如果此时再来一个 key 为 d，会检测前三个位置是否 key 重复，不重复则对比到最后，添加到尾部；重复则替换值。这就是为什么要使用单向链表的原因。

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

哈希函数

前面我们提到的，会根据 key 去计算出一个数组索引，我们把这个方法称为哈希函数。

哈希函数实现步骤如下：

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

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

求模数组的长度，可以让索引值保持在长度范围内。但是求模效率较低，我们可以使用 & 位运算取代 % 运算，前提是数组的长度必须设计为 2 的幂（2^n）

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

如何理解上面的代码？

首先 & 位运算，1&1=1；1&0=0；0&0=0；

2^n 二进制

2^n-1

0可以省略

二进制数&全是1的数，意味着你原本是什么，结果就是什么。而且必然小于或等于全是1的数

这就是上面代码的由来。

良好的哈希函数

让哈希值更加均匀分布 -> 减少哈希冲突次数 -> 提高哈希表的性能

哈希值计算

前面我们已经知道哈希函数的第二步运算了，现在我们去研究做第一步。也就是代码中的 hash_code(key)

key 常见种类可能有：

• 整数、浮点数、字符串、自定义对象

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

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

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

这句我们后面再说，这也是面试必问的点。

整数

• 整数值直接当哈希值
• 比如 10 的哈希值就是 10

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

浮点数

• 将存储的二进制格式转为整数值

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

这里必须提一点常识：在 Java 中，哈希值必须是 Int 类型，必须是32位。

Long和Double

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

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

我们先看 double，因为 double 是 64bit，所以转为整数也是64bit，即 long 类型。

由于 long 64bit 不能作为哈希值返回，因此我们要转为 int。

首先你要知道，64bit 转 32bit 其实就是砍掉其 高32bit

>>> 和 ^ 的作用是什么？

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

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

>>>32 右移32位

我们可以发现，其实 value>>>32 后得到 低32bit 就是原本 value 值的 高32bit。

最后进行 ^ ，两者都参与进行计算，最后保留结果的 低32bit 即可。

字符串

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

5*10^3 + 4*10^2 + 8*10^1 + 9*10^0

字符串由若干个字符组成，比如 jack，由 j，a，c，k 四个字符组成（字符本身就是一个整数）

因此，jack 的哈希值可以表示为 j*n^3 + a*n^2 + c*n^1 + k*n^0，等价于 [(j*n + a) * n + c] * n + k

在 JDK 中，乘数 n 为 31，31 是一个奇素数，JVM会将 31*i 优化为 (i << 5) - i

public static void main(String[] args) {
    String s = "jack";
    int hashCode = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        hashCode = hashCode * 31 + c;
        //hashCode = (hashCode << 5) - hashCode + c;
    }
    // hashCode = [(j * 31 + a) * 31 + c] * 31 + k
    System.out.println(hashCode);
}

在 String 源码中，JDK 官方是这样写的

总结：

public static void myHashCode(){
    Integer a = 116;
    Float b = 10.6f;
    Double c = 10.9;
    String d = "abce";
    System.out.println("------int------");
    System.out.println("a = " + a);
    System.out.println("a.hashCode() = " + a.hashCode());
    System.out.println("------float------");
    System.out.println("Float.floatToIntBits(b) = " + Float.floatToIntBits(b));
    System.out.println("b.hashCode() = " + b.hashCode());
    System.out.println("------double------");
    long bits = Double.doubleToLongBits(c);
    int code = (int) (bits ^ bits >>> 32);
    System.out.println(code);
    System.out.println("c.hashCode() = " + c.hashCode());
    System.out.println("------string------");
    System.out.println(d.hashCode());
}

自定义对象

共识：自定义对象默认的 hashCode() 和 equals() 都与内存地址有关。

以下代码都是基于在 哈希表 中进行展开的讨论。

public class App {
    public static void main(String[] args) {
        Person p1 = new Person("钟小湖", 18, 1.68f);
        Person p2 = new Person("钟小湖", 18, 1.68f);
        System.out.println(p1.hashCode());
        System.out.println(p2.hashCode());
    }
}

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

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

1360875712

1625635731

对象内容实际是一样的，但计算出来的哈希值不一样，这是因为我们两个实例对象的内存地址不同，因此我们需要通过重写 hashCode() 来满足需求。

public static void main(String[] args) {
    Person p1 = new Person("钟小湖", 18, 1.68f);
    Person p2 = new Person("钟小湖", 18, 1.68f);
    System.out.println(p1.hashCode());
    System.out.println(p2.hashCode());
    HashMap<Object, Object> map = new HashMap<>();
    map.put(p1,"abc");
    map.put(p2,"abc");
    System.out.println(map.size()); //2
}

在 HashMap 结构中，我们存储了两个key，但这两个key的内容是一样的，应该存储为一个key才合理，原因在于 hashCode() 方法，我们需要重写它来满足自己的需求，实际开发中也是需要重写的。

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

-1717215247

-1717215247

2

我们看到哈希值计算结果是一样了，但 map 为什么还是存储了两个 key 呢？虽然此时的哈希值一样，在哈希表中存储的索引值一样了，但是内存地址的原因，依旧判断它是两个不同的key，不会进行覆盖，所以我们需要去重写这个判断方法，也就是 equals()

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

    Person person = (Person) o;

    if (age != person.age) return false;
    if (Float.compare(person.height, height) != 0) return false;
    return name != null ? name.equals(person.name) : person.name == null;
}

上面的代码应该不用过多解释，主要就是判断3个属性值是否相同，相同返回 true。

所以我们重写了 hashCode() 和 equals() 的道理是什么呢？

首先我们有两个属性值完全一样的实例对象，由于内存地址不同，默认的哈希值不同，索引值可能相同也可能不相同。

假设他们索引相同，存储在一个索引上，但由于内存地址不同，equals 判断结果为两个不同的key，依旧分开存储。

假设他们索引不同，也就意味着存储在不同的单向链表中，根本就不可能将两者关联到，怎么比较呢，肯定都是存储了。

为了解决上面的问题，你要确保计算出的索引稳定，再考虑 equals() 的比较。

因此重写 hashCode() 来保证两个实例对象的哈希值一样，进而保证了索引值一样，然后重写 equals() 保证两个实例对象可以直接比较属性值。