专栏首页MyBlogEffective.Java 读书笔记(9)关于HashCode

Effective.Java 读书笔记(9)关于HashCode

9.Always override hashCode when you override equals

大意为 在你重写equals方法的时候要经常重写hashCode

有很多程序会错误的原因之一,就是当你重写一个类的equals方法的时候忘记重写它的hashCode了

请记住当你重写一个类的equals方法的时候,一定要重写hashCode,如果你不这样做的话,就会违反了Object.hashCode的 通用规范,这通常会导致一些hash类的问题,比如HashMap,HashSet以及HashTable

以下有一些来自于Object类的规范 [JavaSE6]:

  • 当你不断在一个程序里面调用一个对象的hashCode方法,它总应该返回一个相同的整形数值

需要注意的是,这个和重写equals方法的规范中的一致性不大一样,不要求在反复执行相同的程序的情况下,返回一样的值

  • 如果两个对象使用equals方法比较然后返回true的话,那么这两个对象的hashCode应该返回相同的数值
  • 对于两个对象使用equals方法比较返回false的情况,并不强制要求hashCode也不一样

当然,对两个不同的对象返回不同的hashCode值会提高hashTable的表现

在这里指出最为关键的部分,即第二个条件是最容易犯错的,两个对象用equals比较,一定要返回一样的hashCode 两个不一样的实例可能由于修改了equals方法,可能逻辑上是相等的,但是Object的hashCode并不会去在意这些,只会简单地返回不一样的数值,并不会根据规范而返回相同值

举一个简单的例子来说,我们来看一个PhoneNumber的类,我们已经重写了它的构造方法:

public final class PhoneNumber {
    private final short areaCode;
    private final short prefix;
    private final short lineNumber;
    public PhoneNumber(int areaCode, int prefix, int lineNumber) {
        rangeCheck(areaCode, 999, "area code");
        rangeCheck(prefix, 999, "prefix");
        rangeCheck(lineNumber, 9999, "line number");
        this.areaCode = (short) areaCode;
        this.prefix = (short) prefix;
        this.lineNumber = (short) lineNumber;
    }
    private static void rangeCheck(int arg, int max, String name) {
        if (arg < 0 || arg > max)
            throw new IllegalArgumentException(name +": " + arg);
    }
    @Override public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof PhoneNumber))
            return false;
        PhoneNumber pn = (PhoneNumber)o;
        return pn.lineNumber == lineNumber && pn.prefix == prefix
                                    && pn.areaCode == areaCode;
    }
    // Broken - no hashCode method!
    ... // Remainder omitted
}

好的,我们用一个HashMap来储存这个类的实例

Map<PhoneNumber, String> m = new HashMap<PhoneNumber, String>();
m.put(new PhoneNumber(707, 867, 5309), "Jenny")

这个时候,你可能会认为以下这条语句会返回Jenny

m.get(new PhoneNumber(707 , 867 , 5309))

事实却是它返回了一个null,明显存在的问题就是没有重写hashCode方法导致这样,修复这问题只需要重写一个合适的hashCode方法即可

在这里要说一点,即使两个实例运气足够好,散列到同一个bucket里面,HashMap的get方法也会返回null,只要hashCode不一样HashMap就不会去检查逻辑上的相等

下面给出一个无脑的解决的方法:

    // The worst possible legal hash function - never use!
    @Override public int hashCode() { return 42; }

这样看上去好像合法,但是你千万别这样用,它合法是由于它保证了相等的对象一定会有相同的hash code,但是这样的做法太过于粗暴以至于让所有的对象的hash code都一样,所有的对象都散列到相同的bucket里面,HashTable就退化成链表了

一个好的hashCode方法对于不同的对象应该返回不同的值,理想情况下,hashCode方法应该均匀地分配数值给那些不相等的对象,但是实现起来好像比较困难,不过接近这样的方案还是有的:

  1. 存一些连续的非零整形数值,比如说17,把它记为result
  2. 对于每一个重要的域,做下列的事情:
    1. 对这个域计算int类型的hash code,我们把这个hash code叫做c
      1. 如果这个域是布尔变量,返回(f?1:0)
      2. 如果是byte,char,short或者是int,返回(int)f
      3. 如果是long类型,返回 (int) (f ^ (f >>> 32))
      4. 如果是float类型,返回 Float.floatToIntBits(f)
      5. 如果是double类型,先使用 Double.doubleToLongBits(f) 转变为long类型,再按long类型来计算
      6. 如果这个域是对象的引用,而且这个类在使用equals方法的时候会递归地来调用这个引用,那就直接递归地调用这个引用的hashCode方法,当然如果是需要更加复杂的比较,可以先计算出一个规范的表示,然后在这个规范的表示中去调用hashCode方法,如果该域是null,就直接返回0

      返回0是比较传统的做法,你也可以返回其他的

      1. 如果域是一个数组,你可以把元素看成是分离的域的组合,对于那些重要的域使用上述的原则进行计算,当然如果整个数组的元素都是重要的,必须要比较的,那你可以直接使用Arrays.hashCode方法
    2. 通过计算得到的result和c我们可以来更新result,公式为:$$ result=result*31+c$$
  3. 返回result
  4. 结束对hashCode方法的编写,并且检查有没有符合上文所说的那几条规范

在对hash code进行计算的时候,你可能不会把一些“冗余的”域也计算进去,需要注意的是,那些可以由其他域计算而来的域称为冗余的域,计算hash code的时候把它们忽略不理可能不是一件正确的事,很有可能就会导致对于第二个规范的违反

回看一下计算的过程,我们初始化了一个非零的值,这个值对于hash code的最后生成有着极大的影响,但是这个值不能是0,如果是0的话,那么初始化的域的影响就没了,这样就可能产生冲突,故17这个值是合适的

多维的对于不同类型的不同操作表现出了不错的hash特性,另外选择31作为因子是由于它是一个奇素数,而且利用位运算很容易计算,只要右移5位减去1即可

目前使用素数还是不大明确其优点,但传统上是这么用的,在溢出的情况下能够在一定意义上保留信息

我们使用PhoneNumber类来实际操作一次

@Override public int hashCode() {
    int result = 17;
    result = 31 * result + areaCode;
    result = 31 * result + prefix;
    result = 31 * result + lineNumber;
    return result;
}

这样的方法实现保证了逻辑相同的实例有着相同的hashCode,这个方法看似简单,它的性能却和Java平台库的函数性能上不相上下,十分简单而且高效,将逻辑不同的实例散列到不同的bucket中

需要说明的是,如果计算hash code的代价开销不小,你必须考虑把hash code缓存起来而不是每一次都重新计算

我们在PhoneNumber类上简单实现一下

// Lazily initialized, cached hashCode
private volatile int hashCode; 
@Override public int hashCode() {
    int result = hashCode;
    if (result == 0) {
        result = 17;
        result = 31 * result + areaCode;
        result = 31 * result + prefix;
        result = 31 * result + lineNumber;
        hashCode = result;
    }
    return result;
}

这里所提及的hash函数并不是最先进的,你可以利用数学和计算机科学理论的知识结合最前沿的论文探讨一下这个函数的更好的实现方案,但是将一个对象重要的域在hash code的计算中忽略以试图提高性能的做法绝对是完全错误的,最多加快了方法的速度,但对于整个hash集合的性能来说是得不偿失的

目前Integer类的hashCode方法都是返回实确的值,这并不是一个好的办法,希望有一天可以被修改成更为高效的方法

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • When Does Machine Learning FAIL? Generalized Transferability for Evasion and Poisoning Attacks论文笔记

    该论文主要是介绍了一个FAIL模型, 即一个通用框架用来分析针对机器学习系统的真实攻击, 同时也提出了一种有目标的投毒攻击, 称作StingRay, 使得该攻击...

    Mezereon
  • Procedural Noise Adversarial Examples for Black-Box Attacks on Deep Neural Networks论文笔记(1)

    如今一些深度神经网络对于一些对抗性样本(Adversarial sample)是弱势的, 对抗性样本就是指我们对输入进行特定的改变, 通过原有的学习算法最终导致...

    Mezereon
  • 软件工程攻略

    由于软件的开发存在这么多的问题, 其主要原因是规模太大并且缺少一种有效的方法来进行整个软件的开发 从而引出软件工程

    Mezereon
  • 存储性能加速引擎之预读

    顺序预读(prefetch,在Linux中也称为预读,read ahead)是一种用于提升顺序读性能的技术,用于缩小存储设备和应用程序之间巨大的效率差距。Lin...

    焱融科技
  • 负二进制加法实现

    N进制,即表示位数可表示范围为 [0, N)(数学表示法,包括首,不包括尾),比如二进制,位数上可用数字只有0或者1,遇2进位,而我们常用的十进制,位数可用数字...

    用户7685359
  • 案例:Oracle报错ASM磁盘组不存在或没有mount

    环境:RHEL 6.5 + Oracle Standby RAC 11.2.0.4 我做Standby RAC实验时,在恢复控制文件时,报错无法在磁盘组创建文...

    Alfred Zhao
  • CNCC | 深度学习如何“助攻”医学影像?我们来听听学界大拿的解释

    AI 科技评论消息, 10 月 26 日上午 8:30 分,由中国计算机学会(CCF)主办,福州市人民政府、福州大学承办,福建师范大学、福建工程学院协办的 20...

    AI科技评论
  • SpringCloud的入门学习之概念理解、Eureka入门

      答:微服务强调的是服务的大小,它关注的是某一个点,是具体解决某一个问题、提供落地对应服务的一个服务应用,狭意的看,可以看作Eclipse里面的一个个微服务工...

    别先生
  • 【无监督学习最新研究】简单的「图像旋转」预测,为图像特征学习提供强大监督信号

    【新智元导读】在论文中,研究人员训练卷积神经网络来识别被应用到作为输入的图像上的二维旋转。从定性和定量两方面证明,这个看似简单的任务实际上为语义特征学习提供了非...

    新智元
  • Redis过期策略以及内存淘汰机制

    如果你的 Redis 只能存10G数据,你写了12G,那么 Redis 会怎么淘汰那2G数据呢?

    ITer.996

扫码关注云+社区

领取腾讯云代金券