为啥要重写hashCode和equals方法？

在一个长度为n（假设是10000）的线性表（假设是ArrayList）里，存放着无序的数字；

如果我们要找一个指定的数字，就不得不通过从头到尾依次遍历来查找，这样的平均查找次数是n除以2（这里是5000）。

散列表的基本概念

由此可以看出，线性表的平均查找时间比较长，如果要缩短平均查找时间，我们就可以用到散列表（也叫哈希表），它的平均查找时间接近于**O(1)**。

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

散列函数

其中存放的元素和它存放的位置，是用Hash函数来关联的。

散列函数，顾名思义，它是一个函数。我们可以把它定义成 hash(key)，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。

三点散列函数设计的基本要求：

1. 散列函数计算得到的散列值是一个非负整数；
2. 如果 key1 = key2，那 hash(key1) == hash(key2)；
3. 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

假设一个Hash函数是：x * x % 5 ，如果Hash表是一个长度为 11 的线性表。

如果我们要把 6 这个元素放到其中，那么我们先用 6 进行计算一下：6 * 6 % 5 = 1 ，它的Hash值为1，那么它应该放在下标为 1 的位置，同理：7 应该放在下标为 4 的位置。

如果我们要从散列表中找 6 这个元素，那么我们可以对这个元素进行一次Hash运算，然后再从结果中找到这个元素的索引位置。

散列冲突

不过这里我们会遇到一个Hash冲突的问题，比如，我们要把 7 和 8 都放到 Hash表，根据Hash函数x * x % 5 计算，这两个数字的Hash值是一样的，也就是说，它会被放在Hash表中同一个索引，这样就导致了Hash冲突。

再好的散列函数也无法避免散列冲突。那究竟该如何解决散列冲突问题呢？我们常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。

1. 开放寻址法

开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。那如何重新探测新的位置呢？

• 线性探测（Linear Probing）
• 二次探测（Quadratic probing）
• 双重散列（Double hashing）

不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子（load factor）来表示空位的多少。

装载因子的计算公式是：

散列表的装载因子=填入表中的元素个数/散列表的长度

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

2. 链表法

链表法是一种更加常用的散列冲突解决办法，在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

下面我们采用“链表法（拉链法）”，也就是说，在这个位置，通过一个链表存放冲突数字。

hashcode 和 equals

当我们用HashMap存入自定义类时，如果不重写 equals 和 hashCode 方法，得到的结果可能会和我们预期的不一样。

package cn.luziyangde.hash;

import java.util.HashMap;

/**
 * @author ZYang
 * @date 2021-03-09 13:19
 */

class Key {
    private Integer id;

    public Integer getId() {
        return id;
    }

    public Key(Integer id) {
        this.id = id;
    }
}


public class WithoutHashCode {
    public static void main(String[] args) {
        Key k1 = new Key(1);
        Key k2 = new Key(1);
        HashMap<Key, String> hm = new HashMap<>();
        hm.put(k1, "Key with id is 1");
        System.out.println(k1.hashCode());
        System.out.println(k2.hashCode());
        System.out.println(hm.get(k2));
    }
}

当我们向HashMap存放k1时，首先会调用key这个类的hashCode方法，计算它的hash值，随后把k1放入这个hash值所指引的内存位置。

但是由于key这个类没有重写equals和hashCode方法，它就会默认调用Object类的hashCode方法，而Object类里的hashCode方法返回的hash值，其实k1的内存地址，假设是1000。

这个时候，如果我们用k2去拿，它也会计算k2的hash值，随后用这个hash值到相应的位置去拿，但是k1和k2的内存地址是不一样的，因此，用k2无法拿到k1存放在HashMap中的值。

重写Key类的hashCode方法

package cn.luziyangde.hash;

import java.util.HashMap;
import java.util.Objects;

/**
 * @author ZYang
 * @date 2021-03-09 13:19
 */

class Key {
    private Integer id;

    public Integer getId() {
        return id;
    }

    public Key(Integer id) {
        this.id = id;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}


public class WithoutHashCode {
    public static void main(String[] args) {
        Key k1 = new Key(1);
        Key k2 = new Key(1);
        HashMap<Key, String> hm = new HashMap<>();
        hm.put(k1, "Key with id is 1");
        System.out.println(k1.hashCode());
        System.out.println(k2.hashCode());
        System.out.println(hm.get(k2));
    }
}

发现输出的k1和k2的hashCode是一样的，但是k2依然无法获取k1存放在HashMap中的值。

我们重写hashCode方法之后，k1和k2确实具有了相同的hash值，k1和k2确实在Hash表中的下标是一致的，但是由于Hash函数处理Hash冲突的机制，会在k1这个位置维护一个链表，上面依次存放着k1和k2。

所以，尽管k1和k2的hash值一样，但是二者存放的地址却不相同（由于k1和k2是new出来的，所以二者的地址绝不可能一样），因为没有重写equals方法，所以默认调用Object的equals方法，二者比较的仍然是地址，所以k2无法取到k1的值。

重写Key类的equals和hashCode方法

package cn.luziyangde.hash;

import java.util.HashMap;
import java.util.Objects;

/**
 * @author ZYang
 * @date 2021-03-09 13:19
 */

class Key {
    private Integer id;

    public Integer getId() {
        return id;
    }

    public Key(Integer id) {
        this.id = id;
    }

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

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}


public class WithoutHashCode {
    public static void main(String[] args) {
        Key k1 = new Key(1);
        Key k2 = new Key(1);
        HashMap<Key, String> hm = new HashMap<>();
        hm.put(k1, "Key with id is 1");
        System.out.println(hm.get(k2));
    }
}

在什么场景下重写呢？

如果我们在HashMap里存放自定义的键时，我们就需要重写自定义类的hashCode和equals方法。

一般，我们在equals方法里定义判断两个对象是否相等的标准，比如，这里我们可以定义：如果两个对象的id一样，就认为这两个对象一样。

而在定义hashCode时，我们一般可以用主键的hashCode方法，比如这里我们可以用 id.hashCode() 方法来重写hashCode方法。

@Override
public int hashCode() {
	return Objects.hash(id);
}


public static int hash(Object... values) {
	return Arrays.hashCode(values);
}

public static int hashCode(Object a[]) {
	if (a == null)
		return 0;

	int result = 1;

	for (Object element : a)
		result = 31 * result + (element == null ? 0 : element.hashCode());

	return result;
}

在面试中如何引出这个话题？

• 自我介绍
  • 我用过Java集合里的List对象以及HashMap对象，在用的时候，我需要在一定场景下重写hashCode和equals方法；
• 项目介绍
  • 我在项目里用HashMap来存储日志对象，其中它的键是我们自定义的，在自定义的键中，我们需要重写hashCode和equals方法；
• 相关问题展开
  • 面试官在问相关问题时，可以展开说明；比如：面试官问你：你用过Java集合中的哪些集合对象，你就可以说，我用过HashMap，并且我知道在一定场景里，我需要重写hashCode和equals方法；