1

我目前正在研究 Cocoa 集合，并且我的研究带来了 Mike Ash关于对象相等和散列的帖子。

这是该帖子的摘录：

由于 hash 的语义，如果你覆盖 isEqual: 那么你必须覆盖 hash。如果你不这样做，那么你就有可能拥有两个相等但没有相同哈希的对象。如果你在字典、集合或其他使用哈希表的东西中使用这些对象，那么就会引起欢闹。

不幸的是，作者没有进一步详细说明会发生什么欢闹，我的好奇心并没有让我离开它而不试图更深入地挖掘。所以问题是：如果我有两个具有不同哈希值的相等对象并将这些对象放入一个集合中，究竟会发生什么？我会遇到什么样的问题？

4

2 回答 2

5

答案在 Mike 的帖子中

哈希表基本上是一个带有特殊索引的大数组。对象被放入一个数组中，其索引与其哈希相对应。哈希本质上是从对象的属性生成的伪随机数。这个想法是使索引足够随机，以使两个对象不太可能具有相同的散列，但要使其完全可重现。当一个对象被插入时，哈希用于确定它的去向。查找对象时，其哈希值用于确定查找位置。

在更正式的术语中，对象的散列被定义为，如果两个对象相等，则它们具有相同的散列。请注意，反过来是不正确的，也不可能是：两个对象可以具有相同的哈希值并且不相等。你要尽量避免这种情况，因为当两个不相等的对象具有相同的哈希（称为冲突）时，哈希表必须采取特殊措施来处理这种情况，这很慢。然而，事实证明，完全避免它是不可能的。

这意味着您将拥有两个声称相等的对象。您将第一个添加为具有某些值的字典中的键。然后，您尝试使用另一个对象作为键来提取该值。它不起作用。它应该，因为你的对象是平等的。但是最初的哈希查找失败了。

需要明确的是，这可能不会发生。它可能对某些对象有效，而对其他对象则失败。关键是，如果你不实现这两种方法，你不知道会发生什么。

于 2013-04-13T09:03:38.230 回答
0

抛开想知道“为什么”的愿望，你应该看看苹果的文档。

http://developer.apple.com/library/mac/#documentation/Cocoa/Reference/Foundation/Protocols/NSObject_Protocol/Reference/NSObject.html%23//apple_ref/occ/intfm/NSObject/isKindOfClass：

If two objects are equal, they must have the same hash value.

从学术角度来看，所有其他讨论都很有趣，但从根本上说，无论您是否同意 Apple 的规则，如果您想使用 Foundation 框架，都必须遵守它们。

Mike 和上面的海报所说的似乎是真实的，对于当前的 NSDictionary 化身 - 不能保证相同的实现将在未来的版本中保持不变。然而，无论苹果用什么替代它，它（可能）都会保留所有相同的保证和限制。

于 2013-04-13T23:59:50.740 回答