《Effective Java 3》笔记11：当覆盖 equals 方法时，总要覆盖 hashCode 方法

本文是《Effective Java 3》第三章《对象的通用方法》的学习笔记：当覆盖 equals 方法时，总要覆盖 hashCode 方法。

介绍

在覆盖了 equals 方法的类中，必须覆盖 hashCode 方法。 如果你没有这样做，该类将违反 hashCode 方法的一般约定，这将阻止该类在 HashMap 和 HashSet 等集合中正常运行。以下是根据 Object 规范修改的约定：

应用程序执行期间对对象重复调用 hashCode 方法时，它必须一致地返回相同的值，前提是不对 equals 方法中用于比较的信息进行修改。这个值不需要在应用程序的不同执行之间保持一致。
如果根据 equals(Object) 方法判断出两个对象是相等的，那么在两个对象上调用 hashCode 方法必须产生相同的整数结果。

如果根据 equals(Object) 方法判断出两个对象不相等，则不需要在每个对象上调用 hashCode 方法时必须产生不同的结果。但是，程序员应该知道，为不相等的对象生成不同的结果可能会提高散列表的性能。

当你无法覆盖 hashCode 方法时，将违反第二个关键条款：相等的对象必须具有相等的散列码。 根据类的 equals 方法，两个不同的实例在逻辑上可能是相等的，但是对于对象的 hashCode 方法来说，它们只是两个没有共同之处的对象。因此，Object 的 hashCode 方法返回两个看似随机的数字，而不是约定要求的两个相等的数字。例如：

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

此时，你可能期望 m.get(new PhoneNumber(707, 867,5309)) 返回「Jenny」，但是它返回 null。注意，这里涉及到两个 PhoneNumber 实例：一个用于插入到 HashMap 中，另一个相等的实例（被试图）用于检索。由于 PhoneNumber 类未能覆盖 hashCode 方法，导致两个相等的实例具有不相等的散列码，这违反了 hashCode 方法约定。因此，get 方法查找电话号码的散列桶可能会与 put 方法存储电话号码的散列桶不同。即使这两个实例碰巧分配在同一个散列桶上，get 方法几乎肯定会返回 null，因为 HashMap 有一个优化，它缓存每个条目相关联的散列码，如果散列码不匹配，就不会检查对象是否相等。

解决这个问题就像为 PhoneNumber 编写一个正确的 hashCode 方法一样简单。那么 hashCode 方法应该是什么样的呢？写一个反面例子很容易。例如，以下方法是合法的，但是不应该被使用：

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

它是合法的，因为它确保了相等的对象具有相同的散列码。同时它也很糟糕，因为它使每个对象都有相同的散列码。因此，每个对象都分配到同一个桶中，散列表退化为链表。这样，原本应该在线性阶 O(n) 运行的程序将在平方阶 O(n^2) 运行。对于大型散列表，这是工作和不工作的区别。

一个好的散列算法倾向于为不相等的实例生成不相等的散列码。这正是 hashCode 方法约定第三部分的含义。理想情况下，一个散列算法应该在所有 int 值上均匀合理分布所有不相等实例集合。实现这个理想是很困难的。幸运的是，实现一个类似的并不太难。这里有一个简单的方式：

1、声明一个名为 result 的 int 变量，并将其初始化为对象中第一个重要字段的散列码 c，如步骤 2.a 中计算的那样。（回想一下 Item-10 中的重要字段会对比较产生影响）
2、对象中剩余的重要字段 f，执行以下操作：
- 为字段计算一个整数散列码 c：
  - 如果字段是基本数据类型，计算 Type.hashCode(f)，其中 type 是与 f 类型对应的包装类。
  - 如果字段是对象引用，并且该类的 equals 方法通过递归调用 equals 方法来比较字段，则递归调用字段上的 hashCode 方法。如果需要更复杂的比较，则为该字段计算一个「canonical representation」，并在 canonical representation 上调用 hashCode 方法。如果字段的值为空，则使用 0（或其他常数，但 0 是惯用的）。
  - 如果字段是一个数组，则将其每个重要元素都视为一个单独的字段。也就是说，通过递归地应用这些规则计算每个重要元素的散列码，并将每个步骤 2.b 的值组合起来。如果数组中没有重要元素，则使用常量，最好不是 0。如果所有元素都很重要，那么使用 Arrays.hashCode。
- 将步骤 2.a 中计算的散列码 c 合并到 result 变量，如下所示：
```
result = 31 * result + c;
```
3、返回 result 变量。

当你完成了 hashCode 方法的编写之后，问问自己现在相同的实例是否具有相同的散列码。编写单元测试来验证你的直觉（除非你使用 AutoValue 生成你的 equals 方法和 hashCode 方法，在这种情况下你可以安全地省略这些测试）。如果相同的实例有不相等的散列码，找出原因并修复问题。

可以从散列码计算中排除派生字段。换句话说，你可以忽略任何可以从包含的字段计算其值的字段。你必须排除不用 equals 比较的任何字段，否则你可能会违反 hashCode 方法约定的第二个条款。

在步骤 2.b 中使用的乘法将使结果取决于字段的顺序，如果类有多个相似的字段，则会产生一个更好的散列算法。例如，如果字符串散列算法中省略了乘法，那么所有的字母顺序都有相同的散列码。选择 31 是因为它是奇素数。如果是偶数，乘法运算就会溢出，信息就会丢失，因为乘法运算等同于移位。使用素数的好处不太明显，但它是传统用法。31 有一个很好的特性，可以用移位和减法来代替乘法，从而在某些体系结构上获得更好的性能：31 * i == (i <<5) – i。现代虚拟机自动进行这种优化。

让我们将前面的方法应用到 PhoneNumber 类：

// Typical hashCode method
@Override
public int hashCode() {
    int result = Short.hashCode(areaCode);
    result = 31 * result + Short.hashCode(prefix);
    result = 31 * result + Short.hashCode(lineNum);
    return result;
}

因为这个方法返回一个简单的确定的计算结果，它的唯一输入是 PhoneNumber 实例中的三个重要字段，所以很明显，相等的 PhoneNumber 实例具有相等的散列码。实际上，这个方法是 PhoneNumber 的一个非常好的 hashCode 方法实现，与 Java 库中的 hashCode 方法实现相当。它很简单，速度也相当快，并且合理地将不相等的电话号码分散到不同的散列桶中。

虽然本条目中的方法产生了相当不错的散列算法，但它们并不是最先进的。它们的质量可与 Java 库的值类型中的散列算法相媲美，对于大多数用途来说都是足够的。如果你确实需要不太可能产生冲突的散列算法，请参阅 Guava 的 com.google.common.hash.Hashing [Guava]。

Objects 类有一个静态方法，它接受任意数量的对象并返回它们的散列码。这个名为 hash 的方法允许你编写只有一行代码的 hashCode 方法，这些方法的质量可以与本条目中提供的编写方法媲美。不幸的是，它们运行得更慢，因为它们需要创建数组来传递可变数量的参数，如果任何参数是原始类型的，则需要进行装箱和拆箱。推荐只在性能不重要的情况下使用这种散列算法。下面是使用这种技术编写的 PhoneNumber 的散列算法：

// One-line hashCode method - mediocre performance
@Override
public int hashCode() {
    return Objects.hash(lineNum, prefix, areaCode);
}

如果一个类是不可变的，并且计算散列码的成本非常高，那么你可以考虑在对象中缓存散列码，而不是在每次请求时重新计算它。如果你认为这种类型的大多数对象都将用作散列键，那么你应该在创建实例时计算散列码。否则，你可以选择在第一次调用 hashCode 方法时延迟初始化散列码。在一个延迟初始化的字段的情况下，需要注意以确保该类仍然是线程安全的。我们的 PhoneNumber 类不值得进行这种处理，但只是为了向你展示它是如何实现的，如下所示。注意，散列字段的初始值（在本例中为 0）不应该是通常创建的实例的散列码：

// hashCode method with lazily initialized cached hash code
private int hashCode; // Automatically initialized to 0
@Override
public int hashCode() {
    int result = hashCode;

    if (result == 0) {
        result = Short.hashCode(areaCode);
        result = 31 * result + Short.hashCode(prefix);
        result = 31 * result + Short.hashCode(lineNum);
        hashCode = result;
    }

    return result;
}

不要试图从散列码计算中排除重要字段，以提高性能。 虽然得到的散列算法可能运行得更快，但其糟糕的质量可能会将散列表的性能降低到无法使用的程度。特别是，散列算法可能会遇到大量实例，这些实例在你选择忽略的不同区域。如果发生这种情况，散列算法将把所有这些实例映射很少一部分散列码，使得原本应该在线性阶 O(n) 运行的程序将在平方阶 O(n^2) 运行。

这不仅仅是一个理论问题。在 Java 2 之前，字符串散列算法在字符串中，以第一个字符开始，最多使用 16 个字符。对于大量且分层次的集合（如 url），该函数完全展示了前面描述的病态行为。

不要为 hashCode 返回的值提供详细的规范，这样客户端就不能理所应当的依赖它。这（也）给了你更改它的余地。 Java 库中的许多类，例如 String 和 Integer，都将 hashCode 方法返回的确切值指定为实例值的函数。这不是一个好主意，而是一个我们不得不面对的错误：它阻碍了在未来版本中提高散列算法的能力。如果你保留了未指定的细节，并且在散列算法中发现了缺陷，或者发现了更好的散列算法，那么你可以在后续版本中更改它。

总之，每次覆盖 equals 方法时都必须覆盖 hashCode 方法，否则程序将无法正确运行。你的 hashCode 方法必须遵守 Object 中指定的通用约定，并且必须合理地将不相等的散列码分配给不相等的实例。这很容易实现，如果有点枯燥，可使用第 51 页的方法。AutoValue 框架提供了一种能很好的替代手动编写 equals 方法和 hashCode 方法的功能，IDE 也提供了这种功能。

总结

在《Effective Java 3》第三章《对象的通用方法》中，确实提到了一个重要的原则，即在覆盖equals方法时，总要覆盖hashCode方法。

这是因为，如果两个对象在equals方法中被认为是相等的，那么它们的hashCode方法也必须返回相同的值。这是因为在Java中，如果两个对象的hashCode不同，则它们将被认为是不同的对象，即使它们在equals方法中被认为是相等的。

因此，如果不覆盖hashCode方法，那么可能会导致在使用哈希表、哈希集合或哈希映射等数据结构时出现问题。这些数据结构通常使用hashCode方法来确定对象在数据结构中的位置，如果hashCode方法没有正确实现，那么可能会导致对象无法正确添加、删除或查找。

因此，当覆盖equals方法时，总要覆盖hashCode方法，并确保hashCode方法的实现与equals方法的实现一致。在实现hashCode方法时，通常需要考虑对象的所有属性，并根据属性的值计算一个哈希码，以保证不同的对象具有不同的哈希码，相同的对象具有相同的哈希码。

在Java中，可以使用Objects类的hash方法来计算对象的哈希码，例如：

@Override
public int hashCode() {
    return Objects.hash(property1, property2, ...);
}

其中，property1、property2等为对象的属性，可以根据实际情况进行调整。

总之，在覆盖equals方法时，总要覆盖hashCode方法，并确保hashCode方法的实现与equals方法的实现一致。这是Java编程中一个重要的原则，应该在实际编程中加以注意。

以下是一些在Java中实现hashCode时需要避免的常见错误：

不考虑所有相关字段：在实现hashCode时，需要考虑所有相关字段，这些字段对于对象的标识至关重要。如果省略了一个字段，那么可能会导致相等的对象具有不同的哈希码，这可能会在使用哈希表或哈希集合等数据结构时出现问题。
使用可变字段：如果对象具有可变字段，则不应将它们包含在hashCode计算中。这是因为对象的哈希码应该在其生命周期内保持不变，包含可变字段可能会导致哈希码发生变化，即使对象的标识保持不变。
分布不均匀：良好的hashCode实现应该生成在哈希表中均匀分布的哈希码。如果哈希码不均匀分布，可能会导致哈希表性能下降或冲突。
不使用质数：在计算hashCode时，常常使用质数来避免冲突。如果不使用质数，可能会导致更多的冲突和较差的性能。
使用默认实现：如果不重写hashCode，将使用Object类提供的默认实现，该实现只返回对象的内存地址。这可能对某些情况足够，但不能保证生成唯一的哈希码，可能会在使用哈希表或哈希集合等数据结构时出现问题。
与equals不一致：hashCode实现应该与equals实现保持一致，这意味着如果根据equals实现，两个对象相等，则它们应该具有相同的hashCode。如果未确保一致性，可能会在使用哈希表或哈希集合等数据结构时出现问题。
不缓存哈希码：计算对象的哈希码可能是一个昂贵的操作，因此通常需要在计算出哈希码后缓存它。如果不缓存哈希码，可能会导致性能问题，特别是在使用哈希表或哈希集合等数据结构时。

要确保hashCode分布均匀，可以采用以下方法：

使用所有相关字段：在计算hashCode时，需要使用所有相关字段，以确保所有字段都对生成的哈希码有贡献。如果省略字段，则可能会导致相等的对象具有不同的哈希码，从而影响哈希表或哈希集合等数据结构的性能。
选择适当的哈希函数：选择适当的哈希函数可以确保生成的哈希码分布均匀。例如，Java中的Objects类提供了一些哈希函数，例如hash、hashCombine等，可以根据需要选择适当的哈希函数。
使用质数：使用质数可以避免哈希冲突。在计算hashCode时，可以使用质数来计算不同字段的哈希码，然后将它们组合起来以生成最终的哈希码。
压缩哈希码：在生成哈希码后，可以将其压缩到哈希表的合法范围内，以确保哈希码分布均匀。例如，如果哈希表大小为2的n次方，可以通过将哈希码与2的n次方-1进行按位与运算来压缩哈希码，以确保哈希码在0到2的n次方-1之间均匀分布。
使用哈希码随机化：在生成哈希码后，可以对其进行随机化，以避免敌手攻击和哈希冲突。例如，可以使用一个随机数，将其与哈希码混合，以生成最终的哈希码。

哈希冲突是指不同的键（key）在哈希表中映射到相同的位置（索引）的情况。为了处理哈希冲突，可以采用以下几种方法：

开放地址法：开放地址法是一种常用的处理哈希冲突的方法，它的思想是在哈希表中寻找一个空槽，将冲突的键放入该槽中。常用的开放地址法包括线性探测、二次探测和双重散列等。
链地址法：链地址法是另一种常用的处理哈希冲突的方法，它的思想是将哈希表中同一个位置的所有键放在一个链表中。当发生哈希冲突时，只需要将冲突的键添加到链表的末尾即可。链地址法适用于存储大量数据的哈希表。
再哈希法：再哈希法是一种处理哈希冲突的方法，它的思想是使用另一个哈希函数来计算冲突键的哈希值。当发生哈希冲突时，使用另一个哈希函数重新计算哈希值，直到找到一个空槽插入键为止。
建立公共溢出区：建立公共溢出区是一种处理哈希冲突的方法，它的思想是在哈希表中保留一些位置，用于存储哈希冲突的键。当发生哈希冲突时，将冲突的键放入公共溢出区中，而不是在哈希表的其他位置中。

无论采用哪种方法，处理哈希冲突时需要考虑以下几个方面：

效率：处理哈希冲突的方法应该具有高效性，能够在不影响性能的情况下解决哈希冲突。
冲突解决度：处理哈希冲突的方法应该具有良好的冲突解决度，能够尽可能地减少哈希冲突的发生。
实现复杂度：处理哈希冲突的方法应该易于实现和维护。

介绍#

总结#

介绍

总结