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

介绍

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

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

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

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

1
2

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 方法应该是什么样的呢？写一个反面例子很容易。例如，以下方法是合法的，但是不应该被使用：

1
2
3

// 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 变量，如下所示：

      1

      result = 31 * result + c;

  • 3、返回 result 变量。

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

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

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

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

1
2
3
4
5
6
7
8

// 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 的散列算法：

1
2
3
4
5

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// 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 方法来计算对象的哈希码，例如：

1
2
3
4

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

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

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

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

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

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

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

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

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

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

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