objective-c - cocoa 。对象相等和散列澄清

Question

我目前正在研究 cocoa 系列，我的研究已经带到了 Mike Ash 的 post关于对象相等和散列。

以下是该帖子的摘录:

Because of the semantics of hash, if you override isEqual: then you must override hash. If you don't, then you risk having two objects which are equal but which don't have the same hash. If you use these objects in a dictionary, set, or something else which uses a hash table, then hilarity will ensue.

不幸的是，作者没有进一步详细说明将会发生什么搞笑的事情，而且我的好奇心不允许我在不尝试深入挖掘的情况下就离开它。所以问题是:如果我有两个具有不同哈希值的相等对象，并且我将这些对象放入一个集合中，到底会发生什么？我会遇到什么样的问题？

Answer 1

答案就在 Mike 的帖子的这一部分

A hash table is basically a big array with special indexing. Objects are placed into an array with an index that corresponds to their hash. The hash is essentially a pseudorandom number generated from the object's properties. The idea is to make the index random enough to make it unlikely for two objects to have the same hash, but have it be fully reproducible. When an object is inserted, the hash is used to determine where it goes. When an object is looked up, its hash is used to determine where to look.

In more formal terms, the hash of an object is defined such that two objects have an identical hash if they are equal. Note that the reverse is not true, and can't be: two objects can have an identical hash and not be equal. You want to try to avoid this as much as possible, because when two unequal objects have the same hash (called a collision) then the hash table has to take special measures to handle this, which is slow. However, it's provably impossible to avoid it completely.

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

需要明确的是，这可能不会发生。它可能对某些对象工作正常，但对另一些对象则失败。关键是，如果您不实现这两种方法，您将不知道会发生什么。