如何正确实现Java中的hashCode方法

你知道一个对象的唯一标志

太棒了,不过现在你也必须实现hashCode方法。

让我们看看为什么和怎么做才是正确的。

相等和哈希码

相等是从一般的方面来讲,哈希码更加具有技术性。如果我们在理解方面存在困难,我们可以说,他们通过只是一个实现细节来提高了性能。

大多数的数据结构通过equals方法来判断他们是否包含一个元素,例如:

List<String> list = Arrays.asList("a", "b", "c");
boolean contains = list.contains("b");

这个变量contains结果是true,因为,虽然”b”是不相同的实例(此外,忽略字符串驻留),但是他们是相等的。

通过比较实例的每个元素,然后将比较结果赋值给contains是比较浪费的,虽然整个类的数据结构进行了优化,能够提升性能。

他们通过使用一种快捷的方式(减少潜在的实例相等)进行比较,从而代替通过比较实例所包含的每个元素。而快捷比较仅需要比较下面这些方面:

快捷方式比较即通过比较哈希值,它可以将一个实例用一个整数值来代替。哈希码相同的实例不一定相等,但相等的实例一定具有有相同的哈希值。(或应该有,我们很快就会讨论这个)这些数据结构经常通过这种这种技术来命名,可以通过Hash来识别他们的,其中,HashMap是其中最著名的代表。

它们通常是这样这样运作的

  • 当添加一个元素,它的哈希码是用来计算内部数组的索引(即所谓的桶)
  • 如果是,不相等的元素有相同的哈希码,他们最终在同一个桶上并且捆绑在一起,例如通过添加到列表。
  • 当一个实例来进行contains操作时,它的哈希码将用来计算桶值(索引值),只有当对应索引值上存在元素时,才会对实例进行比较。

因此equalshashCode是定义在Object类中。

散列法的思想

如果hashCode作为快捷方式来确定相等,那么只有一件事我们应该关心:相等的对象应该具有相同的哈希码,这也是为什么如果我们重写了equals方法后,我们必须创建一个与之匹配的hashCode实现的原因!

否则相等的对象是可能不会有相同的哈希码的,因为它们将调用的是Object's的默认实现。

HashCode 准则

引用自官方文档

hashCode通用约定: * 调用运行Java应用程序中的同一对象,hashCode方法必须始终返回相同的整数。这个整数不需要在不同的Java应用程序中保持一致。 * 根据equals(Object)的方法来比较,如果两个对象是相等的,两个对象调用hashCode方法必须产生相同的结果。 * 根据equals(Object)的方法是比较,如果两个对象是不相等的,那么两个对象调用hashCode方法并不一定产生不同的整数的结果。但是,程序员应该意识到给不相等的对象产生不同的整数结果将有可能提高哈希表的性能。

第一点反映出了相等的一致性属性,第二个就是我们上面提出的要求。第三个阐述了一个重要的细节,我们将在稍后讨论。

HashCode实现

下面是非常简单的Person.hashCode的实现

@Override
public int hashCode() {
    return Objects.hash(firstName, lastName);
}

person’s是通过多个字段结合来计算哈希码的。都是通过Objecthash函数来计算。

选择字段

但哪些字段是相关的吗?需求将会帮助我们回答这个问题:如果相等的对象必须具有相同的哈希码,那么计算哈希码就不应包括任何不用于相等检查的字段。(否则两个对象只是这些字段不同但是仍然有可能会相等,此时他们这两个对象哈希码却会不相同。)

所以用于哈希组字段应该相等时使用的字段的子集。默认情况下都使用相同的字段,但有一些细节需要考虑。

一致性

首先,有一致性的要求。它应该相当严格。虽然它允许如果一些字段改变对应的哈希码发生变化(对于可变的类是不可避免的),但是哈希数据结构并不是为这种场景准备的。

正如我们以上所见的哈希码用于确定元素的桶。但如果hash-relevant字段发生了改变,并不会重新计算哈希码、也不会更新内部数组。

这意味着以后通过相等的对象,甚至同一实例进行查询也会失败,数据结构计算当前的哈希码与之前存储实例计算的哈希码并不一致,并是错误的桶。

结论:最好不要使用可变字段计算哈希码!

性能

哈希码最终计算的频率与可能调用equals差不多,那么这里将是影响性能的关键部分,因此考虑此部分性能也是非常有意义的。并且与equals相比,优化之后又更大的上升空间。

除非使用非常复杂的算法或者涉及非常多的字段,那么计算哈希码的运算成本是微不足道的、同样也是不可避免的。但是也应该考虑是否需要包含所有的字段来进行运算。集合需要特别警惕的对待。以Listssets为例,将会包含集合里面的每一个元素来计算哈希码。是否需要调用它们需要具体情况具体分析。

如果性能是至关重要的,使用Objects.hash因为需要为varargs创建一个数组也许并不是最好的选择。但一般规则优化是适用的:不要过早地使用一个通用的散列码算法,也许需要放弃集合,只有优化分析显示潜在的改进。

碰撞

总是关注性能,这个实现怎么呢?

@Override
public int hashCode() {
    return 0;
}

快是肯定的。相等的对象将具有相同的哈希码。并且,没有可变的字段!

但是,我们之前说过的桶呢?!这种方式下所有的实例将会有相同的桶!这将会导致一个链表来包含所有的元素,这样一来将会有非常差的性能。每次调用contains将会触发对整个list线性扫描。

我们希望尽可能少的元素在同一个桶!一个算法返回变化多端的哈希码,即使对于非常相似的对象,是一个好的开始。

怎样才能达到上面的效果部分取决于选取的字段,我们在计算中包含更多的细节,越有可能获取到不同的哈希码。注意:这个与我们所说的性能是完全相反的。因此,有趣的是,使用过多或者过少的字段都会导致糟糕的性能。

防止碰撞的另一部分是使用实际计算散列的算法。

计算Hsah

最简单的方法来计算一个字段的哈希码是通过直接调用hashCode,结合的话会自动完成。常见的算法是首先在以任意数量的数值(通常是基本数据类型)反复进行相乘操作再与字段哈希码相加

int prime = 31;
int result = 1;
result = prime * result + ((firstName == null) ? 0 : firstName.hashCode());
result = prime * result + ((lastName == null) ? 0 : lastName.hashCode());
return result;

这可能导致溢出,但是不是特别有问题的,因为他们并没有产生Java异常。

注意,即使是非常良好的的哈希算法也可能因为输入特定的模式的数据有导致频繁碰撞。作为一个简单的例子假设我们会计算点的散列通过增加他们的x和y坐标。当我们处理f(x) = -x线上的点时,线上的点都满足:x + y == 0,将会有大量的碰撞。

但是:我们可以使用一个通用的算法,只到分析表明并不正确,才需要对哈希算法进行修改。

总结

我们了解到计算哈希码就是压缩相等的一个整数值:相等的对象必须有相同的哈希码,而出于对性能的考虑:最好是尽可能少的不相等的对象共享相同的哈希码。

这就意味着如果重写了equals方法,那么就必须重写hashCode方法

当实现hashCode

  • 使用与equals中使用的相同的字段(或者equals中使用字段的子集)
  • 最好不要包含可变的字段。
  • 对集合不要考虑调用hashCode
  • 如果没有特殊的输入特定的模式,尽量采用通用的哈希算法

记住hashCode性能,所以除非分析表明必要性,否则不要浪费太多的精力。

原文发布于微信公众号 - 大数据钻研(bigdata118)

原文发表时间:2016-06-22

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏hbbliyong

看到他我一下子就悟了-- 泛型(2)

   先说些题外话,只所以写这些东西。是看了CSDN上的曹版主的一篇:手把手教编程,不知道有没有人愿意参与。说实话,我工作四年,总感觉晕晕乎乎的,好多技术都 懂...

2979
来自专栏C语言C++游戏编程

C语言第一个字符串Hello,C语言基础教程之字符串

C 语言中,字符串实际上是使用 null 字符 '' 终止的一维字符数组。因此,一个以 null 结尾的字符串,包含了组成字符串的字符。

1192
来自专栏MyBlog

Effective.Java 读书笔记(8)关于equals方法

重写equals看上去十分简单对吧,但是我觉得很多时候重写equals可能会招致一些问题,这些问题有时可能会特别严重,当然了不重写不就完事了吗?但是这只适用于那...

854
来自专栏pangguoming

全面理解面向对象的 JavaScript

前言 当今 JavaScript 大行其道,各种应用对其依赖日深。web 程序员已逐渐习惯使用各种优秀的 JavaScript 框架快速开发 Web 应用,从而...

38110
来自专栏blackheart的专栏

[程序设计语言]-[核心概念]-03:控制流

0.概述 前面介绍了语言的演进以及一些基础概念后,从本篇开始进入了语言的核心问题中。这一篇讨论的是语言计算模型(大致可以用控制流来表述),大致如下7种: 顺序执...

21110
来自专栏非著名程序员

鸡蛋问题来了,是先有Class还是先有Object?

周末比较无聊,在浏览论坛的时候,偶然看到一个程序猿提问的问题,他时这样提问的:突然想到一个很菜的问题, 倒底先有Object还是先有Class?所有类都是Obj...

2036
来自专栏zhisheng

运算优先级、结合性、求值顺序、副作用和顺序点

标题中这几个概念,是很多C/C++程序员在表达式上容易出问题或不清楚的地方,虽然这些概念在很多语言都有体现,但C里面特别明显,所以就以C语言为例子总结下 运算...

4697
来自专栏C语言C++游戏编程

C语言编程中复杂的循环结构,你被循环晕了吗?

当一段代码需要执行多次时,您可能会遇到这种情况。通常,语句按顺序执行:首先执行函数中的第一个语句,然后执行第二个语句,依此类推。

1292
来自专栏诸葛青云的专栏

想当黑客?浅谈C语言编程:不会这个知识就别想了!

看到标题点进来的朋友,应该对黑客这个名词很敏感吧?我想应该是这样的,但是你们知道作为一名黑客需要学习哪些知识吗?小编不是什么大佬,但小编可以明确的告诉你,学习C...

2370
来自专栏Leetcode名企之路

【Leetcode】58. 最后一个单词的长度

这个题比较水,主要是注意一下前后有空格这种情况。 如下代码用preLong记录截止到当前字符最后一个单词的长度.

1042

扫码关注云+社区

领取腾讯云代金券