面试官问我:hashcode 是什么?和equals是兄弟吗?

2020/12/15 10:13
阅读数 109

秋招的时候还记得面试官问过我hashcode是什么,对于int、long、string类型的hashcode有什么区别,和equals一起是怎么使用的,为什么重写hashcode的同时也要重写equals。
八股文背多了,也只是会表面,有空的时候还是整理一下,顺便写了几个例子加深下印象。

hashcode 是什么?

hash 一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值。hash 是一个函数,该函数中的实现就是一种算法,就是通过一系列的算法来得到一个 hash 值。每个对象都有 hashcode,对象的 hashcode 怎么得来的呢?
首先一个对象肯定有物理地址,对象的物理地址跟这个 hashcode 地址不一样,hashcode 代表对象的地址说的是对象在 hash 表中的位置,通过对象的内部地址(也就是物理地址)转换成一个整数,然后该整数通过 hash 函数的算法就得到了 hashcode。所以,hashcode 就是在 hash 表中对应的位置。
所有散列函数都有如下一个基本特性:根据同一散列函数计算出的散列值如果不同,那么输入值肯定也不同。但是,根据同一散列函数计算出的散列值如果相同,输入值不一定相同。
两个不同的输入值,根据同一散列函数计算出的散列值相同的现象叫做碰撞。
常见的 Hash 函数有以下几个:
直接定址法:直接以关键字 k 或者 k 加上某个常数(k+c)作为哈希地址。
数字分析法:提取关键字中取值比较均匀的数字作为哈希地址。
除留余数法:用关键字 k 除以某个不大于哈希表长度 m 的数 p,将所得余数作为哈希表地址。
分段叠加法:按照哈希表地址位数将关键字分成位数相等的几部分,其中最后一部分可以比较短。然后将这几部分相加,舍弃最高进位后的结果就是该关键字的哈希地址。
平方取中法:如果关键字各个部分分布都不均匀的话,可以先求出它的平方值,然后按照需求取中间的几位作为哈希地址。
伪随机数法:采用一个伪随机数当作哈希函数。









定义

以下是关于 HashCode 的官方文档定义:
hashcode 方法返回该对象的哈希码值。支持该方法是为哈希表提供一些优点,例如,java.util.Hashtable 提供的哈希表。
hashCode 的常规协定是:
在 Java 应用程序执行期间,在同一对象上多次调用 hashCode 方法时,必须一致地返回相同的整数,前提是对象上 equals 比较中所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行,该整数无需保持一致。
如果根据 equals(Object) 方法,两个对象是相等的,那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。
以下情况不是必需的:
如果根据 equals(java.lang.Object)方法,两个对象不相等,那么在两个对象中的任一对象上调用 hashCode 方法必定会生成不同的整数结果。但是,程序员应该知道,为不相等的对象生成不同整数结果可以提高哈希表的性能
实际上,由 Object 类定义的 hashCode 方法确实会针对不同的对象返回不同的整数。(这一般是通过将该对象的内部地址转换成一个整数来实现的,但是 JavaTM 编程语言不需要这种实现技巧。)当 equals 方法被重写时,通常有必要重写 hashCode 方法,以维护 hashCode 方法的常规协定,该协定声明相等对象必须具有相等的哈希码。







总结一下:
1.hashcode 一致性 同一个对象的 hashcode 肯定是一样的,无论调用多少次 hashcode 都不会变化,随着 equals 肯定也是一样的
2.两个对象的 hashCode 相同,并不一定表示两个对象就相同,也就是不一定适用于 equals(java.lang.Object) 方法,只能够说明这两个对象在散列存储结构中,如 Hashtable,他们“存放在同一个篮子里”。
3.如果对象的 equals 方法被重写,那么对象的 hashCode 也尽量重写,并且产生 hashCode 使用的对象,一定要和 equals 方法中使用的一致,
刚刚提到的碰撞,指的是不同对象的 hashcode 处在同一个 bucket 当中,这个情况发生的概率越大说明这个 hashcode 设计的不够理想
面试官问我:hashcode 是什么?和equals是兄弟吗?




hashcode 和 equals 的联系

当且仅当两个对象的hashcode和equals相同时,这两个对象才是同一个对象,否则不是。
那么快速判断两个对象的步骤是怎么样的呢,我们假设这里有两个不同的对象A和B。当我们的hashcode设计合理的时候,这两个对象的hashcode(A)是和hashcode(B)不相等的,那么这个时候我们就可以直接判断A和B不是同一对象。但如果hashcode(A)==hashcode(B)呢? 这个时候就要继续通过equals方法进行比较了,但是整个equals方法比hashcode复杂,所以设计一个好的hashcode函数至少可以节约90%以上的时间。

java 中的 hashcode 是如何实现的

我们知道 java 内部 HashSet 和 HashMap 都是基于 hash 算法去实现的
hash算法的好坏,直接影响这个hashcode碰撞的几率,好的hashcode可以使得所有对象均匀地分布在bucket中

1.Integer、Byte、Short、Character都是转换为int类型作为hashcode

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

可以看到hashcode在遇到Integer、Byte、Short、Character直接返回原数,不做处理。

public class HashMapTest {
    public static void main(String[] args) {
        Integer a = 1;
        Integer b = 1;
        System.out.println(a.hashCode()+"  "+b.hashCode());
        System.out.println(a.equals(b));
    }
}
------------------------------------------------------------
1  1
true

2.Long 取高32位和低32位与值转成int类型作为hashcode

Double 将64bit值转成long类型,然后按照Long类型进行获取hashcode**


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

long型是将自己的高32位和低32位拆成两个部分,然后两个部份直接做与操作得出的数字作为hashcode。
demo中a=1,b=1<<32,均为Long型,按照我们的设计两者的hashcode应该是一样的,但是不equals。看看我们的实验是否验证这个说法。

public class HashMapTest {
    public static void main(String[] args) {
        long number = 1;
        Long a =(long)1;
        Long b = number<<32;
        System.out.println(a+" "+b);
        System.out.println(a.hashCode()+" "+b.hashCode() );
        System.out.println(a.equals(b));
    }
}
------------------
1 4294967296
1 1
false

看来还是逃不过equals。
doubleToLongBits该方法可以将double类型数据转换成long类型数据,从而可以使double类型数据按照long的方法判断大小(<, >, ==)。
3.String 将字符串里面的字符以31进制求和,既hash=hash*31+value[i]


     public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

为什么选择31作为乘子

31是一个不大不小的质数,是作为 hashCode 乘子的优选质数之一。另外一些相近的质数,比如37、41、43等等,也都是不错的选择。那么为啥偏偏选中了31呢?请看第二个原因。
31可以被 JVM 优化,31 * i = (i << 5) - i。

4.Boolean true值hashcode为1231,false值hashcode为1237


      public static int hashCode(boolean value) {
        return value ? 1231 : 1237;
    }

5.hashmap 放置元素的hashcode


    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

由于和(length-1)运算,length 绝大多数情况小于2的16次方。所以始终是hashcode 的低16位(甚至更低)参与运算。要是高16位也参与运算,会让得到的下标更加散列。
所以这样高16位是用不到的,如何让高16也参与运算呢。所以才有hash(Object key)方法。让他的hashCode()和自己的高16位^运算。所以(h >>> 16)得到他的高16位与hashCode()进行^运算。
值得注意的是hashset存放的时候也是声明了一个hashmap进行存储,所以原理等同于hashmap

demo

demo1 案例 不重写 hashcode 和 equals:

public class HashCodeTest {
    private int number;
    public HashCodeTest(int number){
        this.number =number;
    }

    public static void main(String[] args) {
        HashCodeTest a = new HashCodeTest(1);
        HashCodeTest b = new HashCodeTest(1);
        System.out.println(a.hashCode());
        System.out.println(b.hashCode());
        System.out.println(a.equals(b));
    }
}

输出

460141958
1163157884
false

分析:

两个不同的对象hashcode(a)和hashcode(b)肯定不同,a 对象和 b 对象调用 equal 函数肯定返回 false

demo2 案例 只重写 hashcode:

public class HashCodeTest {
    private int number;
    public HashCodeTest(int number){
        this.number =number;
    }

    @Override
    public int hashCode() {
        return number%8;
    }

    public static void main(String[] args) {
        HashCodeTest a = new HashCodeTest(1);
        HashCodeTest b = new HashCodeTest(1);
        System.out.println(a.hashCode());
        System.out.println(b.hashCode());
        System.out.println(a.equals(b));
    }
}

输出:

1
1
false

分析:

这个案例中只是覆写了 hashcode 这个方法,没有覆写 equals。
这两个不同的对象 hashcode 相同,但是 equals 不同。
从定义上看是 可以成立的。
但是 hashcode 过于简单,可能存在严重的哈希碰撞问题。而且必须满足同一对象的 hashcode 是一致的。最好是 equals 和 hashcode 同时覆写。


demo3 只重写equals

public class HashCodeTest {
    private int number;
    public HashCodeTest(int number){
        this.number =number;
    }

    @Override
    public boolean equals(Object o) {
        HashCodeTest that = (HashCodeTest) o;
        return number == that.number;
    }

    public static void main(String[] args) {
        HashCodeTest a = new HashCodeTest(1);
        HashCodeTest b = new HashCodeTest(1);
        System.out.println(a.hashCode());
        System.out.println(b.hashCode());
        System.out.println(a.equals(b));

    }
}

输出:

1956725890
356573597
true

只重写equals,可能会因为重写的方法不够完善导致原本两个hashcode不同的对象equals返回true,这是最无法容忍的现象。

面试官问我:hashcode 是什么?和equals是兄弟吗?

和Jerry哥聊技术,聊生活

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部