如何正确的重写 hashcode()

2021 年 12 月 20 日
本文字数：2741 字
阅读完需：约 9 分钟

1、简介

不知道大家有没有在开发中重写过 hashcode 方法，或者在面试中遇到相关的问题。比如一些比较基础的 Java 工作岗位可能会问：你有使用过对象作为 HashMap 的 key 吗？这个问题其实考察的就是程序员对应 hashcode 方法重写的相关知识点，如下 HashMap 的 put 方法截图可以看出，往容器中添加元素计算 hash 值时，调用了 key 对象的 hashcode 方法。

如何正确的重写 hashcode 方法？这其实是一个非常常见而又看似非常简单的问题，但是真正能写的很完善的程序员小捌见得确实不多。（往往越迷人的越危险，越简单的越复杂！！！）

大家往下瞅，看看自己属不属于那个写的很完善的程序员！

2、正文

2.1 什么时候重写

在深入研究如何重写 hashcode 方法之前，必须要先明白什么时候需要重写 hashcode？关于这个问题，总结起来就一句话：需要重写 equals 方法的类，都需要重写 hashcode 方法！

那这个时候你肯定会问，什么时候需要重写 equals 方法呢？关于这个问题小捌已经在上一篇文章中讲过啦，需要的兄弟们可以去我的专栏《Java小知识100例》系列看看，顺便点波订阅，关注小捌学习 Java 不迷路哦！

2.2 如何重写

hashcode 方法是 Java 的 java.lang.Object 提供的本地方法，这个方法在 jvm 中实现，它能返回当前对象在内存中地址。

// 返回对象在内存中的地址public native int hashCode();

复制代码

所以当我们的类未重写 hashcode 方法，且类的其余超类也未重写；那么我们在调用 hashcode 方法时，它将永远返回的是对象的内存地址。这可能不是你想要的结果，那我们如何来重写它呢？

思路

首先我们需要知道，我们是通过对象的域来计算 hash 的，在对象中域无非数组、引用类型、基本数据类型，有这么多类型的域，我们肯定不能选择某一个域的 hash 值来作为对象的 hashcode 方法的返回值；因此我们考虑将域的 hash 值累加起来返回！

基本数据类型，大家可以参考其对应的包装类型的 hashcode 方法
引用类型则直接调用 hashcode()
数组类型则需要遍历数组，依次调用 hashcode()

通用实现

这是 java.util.Objects 提供的 hash 方法，用于计算 hashcode。虽然这个不是一个计算 hashcode 的银弹，但是我们可以借鉴这种实现，而且 Java JDK 源码中大部分类的 hashcode 都是类似这种实现方式！

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

复制代码

这个方法大致可以分为两步：

如果 a==null，则返回 hashcode 为 0
如果 a != null，则遍历每一个域，域不为 null，则调用域的 hashcode 方法并累加

这其中有一个非常显眼的数字 31，每次循环时会将当前 result*31，这是为什么呢？其实每次计算 result*31 的作用是为了，防止 hash 冲突！因为如果不设置一个乘积因子，result 计算的结果比较小，非常容易在累加的过程后出现相同的 hash 值，这种情况不是我们想见到的！

那为什么是 31 呢？31 为什么能成为 JDK 计算团队选中的真命天子，就不能是 2？不能是 1001？其实使用 31 作为乘积因子是有原因的，其原因小捌觉得有三点：

31 是一个不大不小的数，它不会过小导致 hashcode 计算的结果容易发生冲突；因为返回值是一个 int 整数类型也不至于过大，导致 hashcode 返回值溢出。
31 是一个奇数，一个数与奇数相乘，不容易丢失低位；因为乘以 2 相当于无符号左移一位，这样会在低位补 0，这样的话 hashcode 计算的值，就非常容易冲突了。
31 对虚拟机的识别非常友好，对于虚拟机来说 31 = 2^5 - 1，他能针对这种数字做优化并转换为位运算，因此相乘的时候性能较好

小捌在这里分别用乘积因子 2 和乘积因子 31 做个测试：

package com.liziba.part2;
import org.apache.commons.lang3.RandomStringUtils;
import java.util.ArrayList;import java.util.Comparator;import java.util.List;import java.util.Objects;
/** * <p> * HashCode方法测试 * </p> * * @Author: Liziba * @Date: 2021/10/24 11:54 */public class HashCodeMethodDemo {
    /**     * 计算hashcode     *     * @param value         需计算hashcode字符串     * @param capacity      乘数因子     * @return     */    public static int hashCode(String value, int capacity) {
        int hash = 0;        if (Objects.nonNull(value) && value.length() > 0) {            char[] chars = value.toCharArray();            for (int i = 0; i < chars.length; i++) {                hash = capacity * hash + chars[i];            }        }
        return hash;    }

    /**     * hash值冲突比较     *     * @param capacity     * @param hashValues     */    public static void conflictCompare(int capacity, List<Integer> hashValues) {
        Comparator<Integer> comparator = (x, y) -> (x > y) ? 1 : ((x < y) ? -1 : 0);        Integer max = hashValues.stream().max(comparator).get();        Integer min = hashValues.stream().min(comparator).get();        long conflictNum = hashValues.size() - hashValues.stream().distinct().count();        double conflictRate = conflictNum * 1.0 / hashValues.size() ;
        System.out.println(String.format("乘数因子capacity=%d 冲突数=%d 冲突率：%.4f%% 最大值：%d 最小hashCode：%d",                capacity, conflictNum, conflictRate * 100, max, min));    }
           public static void main(String[] args) {
        int num = 100000;        int capacity2 = 2;        int capacity31 = 31;        List<Integer> hashValues2 = new ArrayList<>(num);        List<Integer> hashValues31 = new ArrayList<>(num);        for (int i = 0; i < num; i++) {            // 生成随机数 org.apache.commons.lang3.RandomStringUtils            String value = RandomStringUtils.randomAlphabetic(15);            hashValues2.add(hashCode(value, capacity2));            hashValues31.add(hashCode(value, capacity31));        }
        conflictCompare(capacity2, hashValues2);        conflictCompare(capacity31, hashValues31);
    }
}

复制代码

一共测试 10 万个 15 位长的随机字符串

当乘数因子为 2 时，冲突率接近 4%
当乘数因子为 31 时，冲突率只有 0.0010%

那是不是重写 hashcode 方法的时候，都需要乘上 31 呢？**这肯定不是这样的啦！**乘积因子 31 只是为了减小 hash 冲突的一种解决方案，当你用不上的时候肯定不需要使用乘积因子啦！

发布于: 1 小时前阅读数: 5

原文链接:【http://xie.infoq.cn/article/86441aadedeb94e4d68f30437】。

李子捌

关注

华为云享专家 2020.07.20 加入

公众号【李子捌】

发布

暂无评论

创作场景

如何正确的重写 hashcode()

1、简介

2、正文

2.1 什么时候重写

2.2 如何重写

思路

通用实现

李子捌

评论