search

理解 equals() 和 hashCode()

在基于哈希实现的容器里，如果想使用某个类，不仅需要定义它的 hashode() 方法，还需要定义 equals() 方法。这两个方法一起使用，才能实现对哈希容器的正确查找。

hashtag
经典的 equals()

当创建一个新类时，它会自动继承 Object 类。如果该类没有重写 equals() 方法，它会使用 Object 类中的 equals() 方法。该方法默认比较内存地址，所以只有比较的是同一个对象时，它才会返回 true。这个默认实现是“最具辨别力”的。

public class DefaultComparison {
    private int i, j ,k;
    DefaultComparison(int i, int j, int k) {
        this.i = i;
        this.j = j;
        this.k = k;
    }
    public static void main(String[] args) {
        DefaultComparison a = new DefaultComparison(1, 2, 3),
                b = new DefaultComparison(1, 2, 3);
        System.out.println(a == a);
        System.out.println(a == b);
    }
}
/* output
true 
false */

通常我们希望放宽该限制，如果两个对象类型相同且字段值也相等，就认为这两个对象相等。但可能存在我们不想包含在 equals() 中进行比较的字段，这就属于类设计过程的一部分了。

一个适当的 equals() 方法需满足以下 5 个条件：

  1. 自反性：对于任意的 x，调用 x.equals(x) 应该返回 true。

  2. 对称性：对于任意的 x 和y，当且仅当 y.equals(x) 返回 true 时，x.equals(y) 返回 true。

  3. 传递性：对于任意的 x, y 和 z，如果 x.equals(y) 和 y.equals(z) 都返回 true，那么 x.equals(z) 也应该返回 true。

  4. 一致性：对于任意的 x 和 y，如果对象中用于相等性比较的信息没有被修改过，那么多次调用 x.equals(y) 应该始终返回 true 或 false。

  5. 对于任意非空 x，调用 x.equals(null) 应该返回 false。

下面是满足这些条件的一系列测试，可以确定自身与比较对象（这里称为 rval）是否相等。

  1. 如果 rval 为 null，则两个对象不相等。

  2. 如果 rval 为 this 对象，则两个对象相等。

  3. 如果 rval 不是 this 对象所属的类或子类，则两个对象不相等。

  4. 如果以上测试都通过，接下来就需要确定 rval 中哪些字段是重要的（并且是一致的），然后对它们进行比较。

Java 7 引入了 Objects 类来帮助完成上述流程，可以帮助我们编写出更好的 equals() 方法。

下面示例对不同版本的 Equality 类进行了比较。为了避免代码冗余，这里将使用工厂方法设计模式来构建示例。EqualityFactory 接口提供了 make() 方法来创建 Equality 对象，这样不同的 EqualityFactory 就可以创建不同的 Equality 子类型了：

现在将定义一个 Equality 类，它包含三个字段（在比较时我们认为所有这些字段都很重要），还有一个满足了上述四项检查的 equals() 方法。构造器会打印类的名称，以确保程序执行的是我们想要的测试：

testAll() 方法比较了想要比较的所有不同类型的对象。它使用工厂方法来创建 Equality 对象。

在 main() 中，可以看到调用 testAll() 方法非常简单。EqualityFactory 接口中只有一个方法，所以可以使用 lambda 表达式来实现 make() 方法。

不过上面 equals() 方法太冗长，可以简化为经典形式。可以看到：

  1. 使用了 instanceof 进行检查之后，就不必再检查是否为 null。

  2. 与 this 进行比较是多余的。只要能正确编写 equals() 方法，自我比较肯定不会有问题。

&& 操作符可以进行短路比较，它在第一次遇到失败时就会退出并返回 false。因此，用 && 操作符将这些检查连接起来，实现的 equals() 方法会更简洁：

对于 SuccinctEquality 类，基类构造器会在子类构造器之前调用。输出显示我们仍然得到了正确的结果。可以判断短路的确发生了，否则在 equals() 的比较列表更下方部分进行强制类型转换时，null 测试和“不同类型”测试都会抛出异常。

当使用另一个类来组合新类时，Object.equals() 更能发挥作用：

注意这里对 super.equals() 的调用——不需要重复造轮子。（而且也不总是能够访问基类的所有必要字段）

子类型之间的相等性

继承的特性告诉我们，两个不同子类型的对象在向上强制转型后可以是“相同的”。假设现在有一个 Animal 对象的集合，这个集合只能接受 Animal 的子类型一一本例中为 Dog 和 Pig。每个 Animal 都有一个 name 和一个 size，以及一个唯一的内部 id。

Objects 类提供了 equals() 和 hashCode() 的经典形式定义来供我们使用。

可以通过 Objects 类来定义经典形式的 equals() 和 hashCode() 方法，但本例中我们只在基类 Animal 中定义它们，并且这两个方法都不包含唯一的 id。从 equals() 的角度来看，这意味着我们只关心某物是否是 Animal，而不在乎它是否是特定类型的 Animal。

如果只考虑类型，有时从基类型的角度出发来理解类是有道理的，这也是里氏代换原则的基础。这段代码就非常符合该原则，因为和基类相比，子类型并没有添加任何额外的功能（方法）。子类型仅在行为上不同，但在接口上并没有什么不同（这当然不是一般情况）。

但是当我们提供具有相同数据的两种不同类型的对象时，如果将它们都放进 HashSet<Animal> 中，结果只有一个对象添加成功。这里强调了 equals() 不是一个完美的数学概念，而是（至少部分是）一个机制上的概念。如果想让类型在哈希数据结构中正常工作，那么 hashCode() 和 equals() 方法必须同时定义。

在这里，Dog 和 Pig 都哈希到了 HashSet 中同一个桶中。此时，HashSet 会回退到使用 equals() 方法来区分对象，但是本例中 equals() 也认为它们相等。HashSet 不会添加 Pig 对象，因为已经有一个相同的对象。

即使对象的其他方面都相同，还是可以通过给它们强制添加唯一性来使示例正常工作。本例中，每个 Animal 已经有了一个唯一的 id，因此可以取消 equals() 中 [1]行的注释，或者取消 hashCode() 中 [2] 行的注释。在经典形式中一般会两者都执行，这样就可以在这两个操作中包含所有“不变”的字段（“不变”意味着 equals() 和 hashCode() 在哈希数据结构里存储和检索时不会产生不同的值，加引号是因为必须自行评估某个字段是否会被修改）。

注意，在自己实现的 hashCode() 方法中，如果只涉及单个字段，需使用 Objects.hashCode() 方法。如果有多个字段，使用 Objects.hash() 方法。

也可以遵循标准形式：在子类中定义 equals() 方法（但仍然不包括这个唯一 id）:

注意这里的 hashCode() 是相同的，但因为对象不再相同，所以都出现在 HashSet 中。此外，super.equals() 意味着我们不需要访问基类中的私有字段。

这个问题的一种解读方式是，Java 分离了可替代性与 equals() 和 hashCode() 的定义。我们仍然可以将 Dog 和 Pig 放入 Set<Animal> 中，而不去理会 equals() 和 hashCode() 是如何定义的。但是在定义这些方法时如果不想着哈希结构，这些对象在哈希数据结构中就不会表现正常。不幸的是，equals() 并不仅仅与 hashCode() 结合使用。当你试图避免为特定类定义它时，会使事情变得复杂，这也是应该遵循经典形式的原因。而使情况更加复杂的是，有些时候你只需要实现这两个方法中的一个。

hashtag
哈希和哈希码

在集合章节中，使用了预定义的类来作为 HashMap 的键。这样之所以有效，是因为预定义的类实现了所有必要的功能，这使得它可以作为键来正常工作。

如果想用自定义的类作为 HashMap 的键，一个经常会犯的错误是，忘记实现必要的功能。例如，考虑一个天气预测系统，它用 Groundhog 对象去关联匹配 Prediction 对象。这看起来很简单一一使用 Groundhog 作为键，Prediction 作为值：

每个 Groundhog 都有一个标识号，因此如果想要在 HashMap 中查找某个 Prediction 的时候，可以这样表示：“请给我与 Groundhog #3 关联的 Prediction。”Prediction 通过随机生成一个布尔值来选择天气情况。detectSpring() 方法使用反射来实例化，并且接收 Groundhog 类或其子类作为参数。该特性稍后会派上用场，我们会继承一种新类型的 Groundhog 来解决这里演示的问题。

HashMap 中存储了 Groundhog 及其对应的 Prediction。遍历 HashMap 后的输出显示了它已经被填充。然后用编号 Groundhog #3 作为键去查询相应的预测结果（这个结果肯定是在 Map 中的）。

但是这里我们并没有找到值为 #3 的键。问题在于 Groundhog 自动继承了 Object 类，并且调用了 Object 的 hashCode() 方法为每个对象生成哈希码。默认情况下，该方法使用对象的内存地址。因此，Groundhog(3) 的第一个实例的哈希码，与用于查询的第二个实例的哈希码并不相同。

我们需要重写 hashCode() 方法，但这还不够，还需要重写 Object 的 equals() 方法，这是因为 HashMap 使用了 equals() 方法来判定你的键和列表中的其他键是否相等。

默认的 Object.equals() 方法比较对象的内存地址，而两个 Groundhog(3) 对象的内存地址显然不相等。因此，想要让自定义的类作为 HashMap 的键，就必须重写 hashCode() 和 equals() 这两个方法，下面这个方案就解决了 Groundhog 的问题：

Groundhog2.hashCode() 方法返回了 Groundhog 的编号作为哈希值。在本例，调用方需要确保 Groundhog 编号的唯一性。hashCode() 方法并没有被要求一定要返回唯一的标识，但是 equals() 方法必须严格判断两个对象是否相等。这里的 equals() 方法基于 Groundhog 的编号，所以如果两个 Groundhog 对象的编号相同，它们就不能同时作为键保存在 HashMap 中。

hashtag
理解 hashCode()

前面的示例只是正确解决问题的开始。它表明，如果作为键的对象没有重写 hashCode() 和 equals() 方法，那么哈希数据结构（比如 HashSet、HashMap、LinkedHashset 和 LinkedHashMap）就可能无法正确地处理键。而如果想要很好地解决这个问题，就必须了解哈希数据结构的内部原理。

首先，考虑一下使用哈希背后的动机：用一个对象去查找另一个对象。但你也可以使用 TreeMap 来完成此操作，甚至可以实现一个自己的 Map。与哈希实现相反，下面的例子使用了一对 ArrayList 来实现一个 Map。与集合主题章节中的 AssociateArray.java 不同的是，它完整地实现了 Map 接口，因此也包含了 entrySet() 方法：

put() 方法将键和值放在相应的 ArrayList 中。与 Map 接口一样，它返回了旧键，如果找不到相应的键，则返回 null。

根据 Map 的规范，如果要查找的键不在 SlowMap 中，get() 方法就会返回 null。如果键存在，它会被用来查找对应的数字索引值（这个值表示它在列表 keys 中的位置），然后再以这个数字值为索引，在列表 values 中查找对应的值。注意，get() 方法的参数 key 是 Object 类型，而不是 K 类型（如 AssociateArray.java）。这是因为 Java 语言在发展了很长时间后才引入泛型一一如果泛型是该语言的原始特性，那么 get() 就可以指定其参数的类型了。（具体原因可参考 Gilad Bracha 关于泛型的文章"Converting Legacy Code to Use Generics"，以及 HashMap 的作者 Josh Bloch 相关的演讲"Advanced Topics in Programming Languages: Java Puzzlers"）（补充想法：get() 方法必须覆盖所有实现类中的方法，使用 Object 类型作为参数可以避免某些情况下导致的类型不匹配问题。）

SlowMap 的字符串表示形式是由 AbstractMap 中定义的 toString() 方法自动生成的。

在 main() 中，先加载了一个 SlowMap，然后打印了它的内容。还调用了 get() 方法，验证了它的有效性。

Map.entrySet() 会生成一组 Map.Entry 对象。但 Map.Entry 只是一个接口，它所描述结构依赖于具体实现，因此要实现自己的 Map 类型，还必须实现 Map.Entry:

equals() 方法遵循了前面的要求。Objects 类提供了一个类似的方法来帮助创建 hashCode() 方法：Objects.hash()。在定义 hashCode() 时，如果涉及多个字段就使用该方法。如果只涉及单个字段，请改用 Objects.hashCode()。

这个简单的解决方案可以通过 main() 中的小测试，但它不是一个正确的实现，因为它创建了键和值的副本。entrySet() 的正确实现需要提供一个 Map 的视图，而不是一个副本，并且这个视图允许我们修改原始的 Map（副本则不行）。

hashtag
用哈希提高速度

SlowMap.java 表明创建一种新类型的 Map 不难，但是正如其名，并不快，所以如果有其他选择，我们就不会用它。它的问题出现在查找过程中：键没有按任何特定的顺序来保存，所以只能使用简单的线性搜索，而线性搜索是最慢的查找方式。

之所以用哈希就是为了提高速度，因为通过哈希来查找值的速度非常快。由于瓶颈在于键的查找速度，因此一种解决方案是保证键是有序的，然后使用 Collections.binarySearch() 来执行查找。

哈希则更进一步，它通过一种可以快速定位的方式来存储键。存储一组元素的最快结构是数组，因此数组用来表示键的信息（注意是“键的信息”，而不是键本身）。但因为数组不能调整大小，所以就遇到一个问题：我们想在 Map 中存储不确定数量的值，而键的数量被数组大小所固定，那该怎么办呢？

这里的数组并不保存键。我们会根据键对象来生成一个数，然后通过这个数来索引数组。这个数就是哈希码（hash code），它可以通过 Object 中定义的 hashCode() 方法（使用一个哈希函数）生成，也可以通过自己类里重写的 hashCode() 方法生成。

多个键可能生成相同的索引，即可能存在碰撞。

为了查找值，我们首先计算哈希码并使用它来索引数组。如果能保证没有冲突（值的数量固定的话是有可能的），你就会有一个完美的哈希函数，但这是特殊情况。（如 EnumMap 和 EnumSet，因为 Enum 定义了固定数量的实例）在一般情况下，冲突由外部的链表来处理。数组并不直接指向一个值，而是指向一个值的链表。我们通过 equals() 方法以线性方式在这些值中搜索（因此，equals() 对于哈希也是必不可少的）。这个搜索要慢很多，但是如果哈希函数足够好，每个槽中只会有几个值。这样就无须搜索整个链表，而是快速跳到一个槽里，然后在该槽中只需比较几个条目即可找到值。这就是 HashMap 能够进行快速查找的原因。

现在可以用哈希实现一个简单的 Map：

因为哈希表中的“槽”通常被称为桶(bucket)，所以示例中代表实际的表的数组被命名为 buckets。为了得到更均匀的分布，桶的数量通常是质数。注意它是一个 LinkedList 的数组，能自动为碰撞提供解决方案——每个新项都会被添加到特定桶里的 LinkedList 末尾。尽管 Java 不允许直接创建泛型数组，但可以对此类数组进行引用。示例中我们向上转型到一个这样的数组，这用起来会很方便，不需要在后面的代码里进行额外的转换。

质数实际上并不是哈希桶的理想大小，Java 中的哈希实现使用的大小是2的幕（经过了大量测试）。除法或余数是现代处理器上最慢的运算。如果哈希表的长度为2的幕，就可以使用掩码代替除法。get() 是迄今为止最常见的操作，因此计算成本的很大部分是 % 操作，而使用2的幕消除了这一点（但也可能影响一些 hashCode() 方法）。

在 put() 方法中，我们会在键上调用 hashCode() 方法，返回结果只能为正数。为了使结果数值在 buckets 数组中有效，我们将它与该数组的大小进行模运算。如果该位置为 null，则表示没有哈希到该位置的元素，因此需要先将刚刚哈希到该位置的对象保存到一个新的 LinkedList 里，然后将这个 LinkedList 保存到该位置。但正常情况下一般会查看列表是否有重复项，如果有，则将旧值放入 oldValue 中，然后用新值替换旧值。found 标志会跟踪是否找到了旧的键值对，如果没有，则将新的键值对附加到列表的末尾。

get() 方法计算 buckets 数组索引的方式与 put() 方法相同（这对于能否保证它们定位到同一位置很重要）。如果已经存在一个 LinkedList 对象，则会对它进行搜索来寻找匹配项。

这个特定的实现并没有进行性能调优，它仅用于演示哈希映射时所执行的操作。如果你查看 java.util.HashMap 的源代码，会看到一个经过调优的实现。此外，为了简单起见， SimpleHashMap 使用了与 SlowMap 相同的 entryset() 方法，它过于简单并且不适用于通用的 Map。

hashtag
重写 hashCode()

首先，我们无法控制用于索引存储桶数组的这个实际值的生成。它取决于这个特定 HashMap 的容量，而容量的变化取决于这个集合有多满，以及负载因子（load factor）的情况。因此，hashCode() 产生的值会被进一步处理以创建桶索引。（在 SimpleHashMap 中，只是以桶数组大小为模数进行了计算）

创建 hashCode() 方法时，要考虑的最重要因素是，无论何时调用 hashCode()，它每次都会为特定对象生成相同的值。因此，如果你的 hashCode() 依赖于对象中的可变数据，就必须让用户意识到更改数据会生成不同的键，因为它会生成不同的 hashCode。

另外，你可能不会根据唯一的对象信息来生成一个 hashCode一一特别值得一提的是，在 hashCode() 里使用 this 的值就不好，因为那样就不能在生成一个新键时，保证它与之前 put() 时用到的原始键值对的键相同。这也是在 SpringDetector.java 中出现的间题，因为 hashCode() 的默认实现就使用了对象的地址。因此，要使用对象中有意义的信息来标识对象。

在 String 类中可以看到这样的一个示例，字符串有一个特殊的特性——如果程序里有多个包含相同字符序列的字符串对象，那么这些字符串对象就都会映射到同一个内存地址上。因此，字符串"hello"的两个单独实例生成的 hashCode() 应该是相同的，如下所示:

String 类的 hashCode() 方法显然是基于字符串内容的。

因此，要使 hashCode() 有效，它必须既快速又有意义。也就是说，它必须根据对象的内容来生成值。记住这个值不需要是唯一的——我们应该倾向于速度而不是唯一性——但是对于 hashCode() 和 equals()，必须能确保它们定位到相同的对象。

hashCode() 会在桶索引生成之前进一步处理，因此它的取值范围并不重要，只需要保证它是 int 就可以了。

还有另一个因素：一个好的 hashCode() 应该保证值的均匀分布。如果值趋于聚集，那么 HashMap 或 HashSet 在某些区域的负载就会更重，并且速度也没有均匀分布的哈希函数那么快。

"Effective Java Programming Language Guide" 一书中，给出了比较好的 hashCode() 的基本准则：

  1. 把一个非零常数，如 17，保存在一个叫 result 的变量中。

  2. 对于对象中的每个重要字段 f（即 equals() 方法会考虑的每个字段），计算出该字 段的 int 类型的哈希码 c，具体如下表所示。

  3. 组合上面计算出的哈希码：result = 37 * result + c。

  4. 返回 result 值。

  5. 观察得到的 hashCode()，确保相等的实例具有相同的哈希码。

字段类型
计算公式

boolean

c = (f ? 0 : 1)

byte, char, short, or int

c = (int)f

long

c = (int)(f ^ (f >>> 32))

float

c = Float.floatToIntBits(f);

double

long l = Double.doubleToLongBits(f); c = (int)(l ^ (l >>> 32))

Object, 其中比较时调用的是这个字段自身的 equals()

c = f.hashCode()

Array

应用以上规则到每一个元素中

下面是一个遵循了这些准则的示例。请注意，实际编码时并不需要这样一一相反，使用 Objects.hash() 对多个字段进行哈希（如本例中），或使用 Objects.hashCode() 对单个字段进行哈希即可。

CountedString 包含了一个字符串和一个id，id 表示包含相同字符串的 CountedString 对象的数量。我们通过在构造器中遍历存储了所有字符串的静态 ArrayList 来完成计数。

hashCode() 和 equals() 都基于两个字段来生成结果。如果仅基于字符串或单独的 id，就会重复匹配不同的值。

在 main() 中，我们使用相同的字符串来创建多个 CountedString 对象，这样就可以看到，由于计数 id 的存在，重复项也能生成唯一值。我们打印了 HashMap，这样就可以看到它在内部是如何存储的（没有可辨别的顺序）。我们还单独查找了每个键，来证实查找机制是能正常工作的。

第二个实例，使用了反射章节在 reflection.pets 库中定义的基类 Individual 类。

这里我们将合理地使用 Objects.hash()，而不是手动创建 hashCode() 方法：

compareTo() 方法中的比较逻辑是有层次结构的：首先按实际类型来排序，然后按 name（如果有的话）排序，最后如果还没有结果的话就按创建顺序来排序。下面的示例展示了其工作机制：

所有的宠物都有名字，因此它们首先按类型排序，然后在同一类型中按名称排序。

hashtag
HashMap 调优

可以对 HashMap 进行手动调优，来提高它在特定应用程序里的性能。在 HashMap 调优时，一些术语如下。

  • 容量：哈希表中桶的数量

  • 初始容量：创建哈希表时桶的数量。HashMap 和 HashSet 都提供了允许指定初始容量的构造器。

  • 大小：哈希表中当前的条目数

  • 负载因子：大小/容量。负载因子为0表示哈希表为空，0.5表示哈希表半满，以此类推。轻负载的哈希表很少发生冲突，因此最适合插入和查找（但会减慢迭代器的遍历过程，因为稀疏分布）。HashMap 和 Hashset 都提供了允许指定负载因子的构造器。当达到这个负载因子时，集合会自动增加容量（桶的数量），方法是将其直接加倍，并将现有对象重新分配到新的桶里 这称为再哈希（rehashing）.

HashMap 默认的负载因子是 0.75（即它直到哈希表的四分之三已满才会再哈希）。这 以乎是一个在时间和空间上比较好的权衡。更高的负载因子会减少哈希表所需的空间，但会增加查找成本，而这很重要，因为我们大部分时间所做的工作就是查找（包括 get() 和 put()）。

如果你知道目己将在一个 HashMap 中存储大量数据，可以适当加大初始容量来创建它，这样就可以避免自动再哈希的开销。

作者认为，允许用户调整哈希表的大小和负载因子等实现细节是一个错误。用户不应该需要了解或关心这些底层细节，因为这些细节的调整可能会带来复杂性和潜在的性能问题。用户只需要提供预期的最大容量（即他们预计哈希表或其他数据结构需要容纳的元素数量）。具体的实现细节（如哈希表的大小和负载因子）应该由库或框架来处理，确保最佳性能。例如，Vector的 capacityIncrement 参数就是一个例子。这个参数决定了Vector在需要扩展容量时，每次增加的容量大小。如果用户设置了一个不合理的值，可能会导致序列添加操作的渐近成本从线性变为平方（即性能显著下降）。理想情况下，Vector的容量应该按指数级增长（如每次扩展时容量翻倍），以保持添加操作的平均时间复杂度为线性。如果用户设置了一个固定的小增量，那么每次添加元素都可能导致频繁的扩展操作，从而使序列添加操作的时间复杂度接近平方级。随着时间的推移，API设计者在这类问题上的决策变得更加明智。IdentityHashMap就是一个例子，它没有暴露任何底层的调优参数，用户只需使用它而不必担心内部实现细节。

上一页Javadoc下一页数据压缩