hashCode 方法及 equals 方法的规范

在Java中,hashCode 方法和 equals 方法都是 java.lang.Object 类的方法,在 The Java Language Specification, Java SE 8 Edition 中定义如下:

  • The method equals defines a notion of object equality, which is based on value,
    not reference, comparison.
  • The method hashCode is very useful, together with the method equals , in
    hashtables such as java.util.HashMap .

简而言之,equals 是判断两个对象是否等价的方法,而 hashCode 则是为散列数据结构服务的计算散列值的方法。下面分别对这两个方法进行讨论。

equals方法

重写规则

equals 方法注重 两个对象在逻辑上是否相等。重写 equals 方法看似比较简单,但实际编写的时候还是要考虑具体类的意义。
一般来说,以下几种情况不需要重写 equals 方法:

  • 一个类的每个实例在本质上都是独立的、不同的,比如 Thread
  • 不需要 equals 方法,也就是判断对象相等的逻辑是没有必要的
  • 父类已重写 equals 方法,并且子类的判断逻辑与父类相符
  • 一个类的访问权限为 private 或 package-private,并且可以确定 equals 方法不会被调用

那么,另外的情况通常需要重写 equals 方法。一般来说,equals 方法遵循离散数学中的 等价关系(equivalence relation)。从 OOP 的角度来说,等价关系三原则如下:

  • 自反性(Reflexive):一个对象与自身相等,即 $x = x$。对任何非空对象 x, x.equals(x) 必定为 true。
  • 对称性(Symmetric):对象之间的等价关系是可交换的,即 $a=b \Leftrightarrow b=a$。对任何非空对象 x、y, x.equals(y) 为 true,当且仅当 y.equals(x) 为 true。
  • 传递性(Transitive):$(a=b)\wedge(b=c) \Rightarrow (a=c)$。对任何非空对象 x、y、z, 若 x.equals(y) 为 true 且 y.equals(z) 为 true,则 x.equals(z) 为 true。

除了遵循这三原则之外,还要遵循:

  • 一致性(Consistent):对任何非空对象 x、y,只要所比较的信息未变,则连续调用 x.equals(y) 总是得到一致的结果。这要求了 equals 所依赖的值必须是可靠的。
  • 对任何非空对象 x, x.equals(null) 必定为 false。

所以,根据上面的原则,equals 函数的一个比较好的实践如下:

  1. 首先先判断传入的对象与自身是否为同一对象,如果是的话直接返回 true。这相当于一种性能优化,尤其是在各种比较操作代价高昂的时候,这种优化非常有效。
  2. 判断对象是否为正确的类型。若此方法接受子类,即子类判断等价的逻辑与父类相同,则可以用 instanceof 操作符;若逻辑不同,即仅接受当前类型,则可以用 getClass 方法获取 Class 对象来判断。注意使用 getClass 方法时必须保证非空,而用 instanceof 操作符则不用非空(null instanceof o 的值为 false)。
  3. 将对象转换为相应的类型:由于前面已经做过校验,因此这里做类型转换的时候不应当抛出 ClassCastException 异常。
  4. 进行对应的判断逻辑

几个注意事项:

  • 我们无法在扩展一个可实例化的类的同时,即增加新的成员变量,同时又保留原先的 equals 约定
  • 注意不要写错 equals 方法的参数类型,标准的应该是 public boolean equals(Object o),若写错就变成重载而不是重写了
  • 不要让 equals 变得太“智能”而使其性能下降
  • 如果重写了 equals 方法,则一定要重写 hashCode 方法(具体见下面)

老生常谈的equals和==

上面提到过,equals方法用来判断 两个对象在逻辑上是否相等,而 == 用来判断两个引用对象是否指向同一个对象(是否为同一个对象)。

用烂了的例子,注意常量池:

1
2
3
4
5
6
7
8
9
10
11
12
String str1 = "Fucking Scala";
String str2 = new String("Fucking Scala");
String str3 = new String("Fucking Scala");
String str4 = "Fucking Scala";
System.out.println(str1 == str2); // false
System.out.println(str2 == str3); // false
System.out.println(str2.equals(str3)); // true
System.out.println(str1 == str4); // true
str4 = "Fuck again!";
String str5 = "Fuck again!";
System.out.println(str1 == str4); // false
System.out.println(str4 == str5); // true

hashCode 方法

如果重写了equals方法,则一定要重写hashCode方法

重写 hashCode 方法的原则如下:

  • 在程序执行期间,只要equals方法的比较操作用到的信息没有被修改,那么对这同一个对象调用多次,hashCode方法必须始终如一地返回同一个整数
  • 如果两个对象通过equals方法比较得到的结果是相等的,那么对这两个对象进行hashCode得到的值应该相同
  • 两个不同的对象,hashCode的结果可能是相同的,这就是哈希表中的冲突。为了保证哈希表的效率,哈希算法应尽可能的避免冲突

关于相应的哈希算法,一个简单的算法如下:

  • 永远不要让哈希算法返回一个常值,这时哈希表将退化成链表,查找时间复杂度也从 $O(1)$ 退化到 $O(N)$
  • 如果参数是boolean型,计算(f ? 1 : 0)
  • 如果参数是byte, char, short或者int型,计算(int) f
  • 如果参数是long型,计算(int) (f ^ (f >>> 32))
  • 如果参数是float型,计算Float.floatToIntBits(f)
  • 如果参数是double型,计算Double.doubleToLongBits(f)得到long类型的值,再根据公式计算出相应的hash值
  • 如果参数是Object型,那么应计算其有用的成员变量的hash值,并按照下面的公式计算最终的hash值
  • 如果参数是个数组,那么把数组中的每个值都当做单独的值,分别按照上面的方法单独计算hash值,最后按照下面的公式计算最终的hash值

组合公式:result = 31 * result + c

比如,String 类的 hashCode 方法如下(JDK 1.8):

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

举个自定义类的 hashCode 例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Baz {
private int id;
private String name;
private double weight;
private float height;
private String note;
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Baz baz = (Baz) o;
if (id != baz.id) return false;
if (Double.compare(baz.weight, weight) != 0) return false;
if (Float.compare(baz.height, height) != 0) return false;
if (name != null ? !name.equals(baz.name) : baz.name != null) return false;
return !(note != null ? !note.equals(baz.note) : baz.note != null);
}
@Override
public int hashCode() {
int result;
long temp;
result = id;
result = 31 * result + (name != null ? name.hashCode() : 0);
temp = Double.doubleToLongBits(weight);
result = 31 * result + (int) (temp ^ (temp >>> 32));
result = 31 * result + (height != +0.0f ? Float.floatToIntBits(height) : 0);
result = 31 * result + (note != null ? note.hashCode() : 0);
return result;
}
}

想找到一个不冲突的哈希算法不是非常容易,具体的属于数据结构部分知识,这里就不再赘述了。


其他语言

C++

C++不像Java那样所有的类都继承一个共同的根基类,因此在写自定义的类时,需要自己写这两个方法。
在C++里,一般通过重载==运算符来实现判断两对象等价的逻辑,而实现计算散列值的函数则需要特化std::hash模板结构体,并且重载()运算符。

如果用不到散列数据结构的话,则无需定义对应的散列函数。

【2015-10 Update】C++ 示例可见 C++ STL之哈希表 | unordered_map


参考资料

  • The Java Language Specification, Java SE 8 Edition
  • Effective Java (2nd Edition)
文章目录
  1. 1. equals方法
    1. 1.1. 重写规则
    2. 1.2. 老生常谈的equals和==
  2. 2. hashCode 方法
  3. 3. 其他语言
    1. 3.1. C++
  4. 4. 参考资料