什么是实现__hash __（）的正确和好方法？
什么是实现__hash__()的正确和好方法？
我正在讨论的函数返回一个哈希码，然后用来插入哈希表又名字典的对象。
作为__hash__()返回一个整数，并用于“binning”对象到哈希表中我假设返回的整数值应该为公共数据均匀分布（以最小化冲突）。 获得这种价值的好习惯是什么？ 碰撞是一个问题吗？ 在我的情况下，我有一个小class，充当一个容器类，持有一些整数，一些浮点数和一个string。
实现__hash__()的简单，正确的方法是使用关键元组。 它不会像专门的散列一样快，但是如果你需要的话，那么你可能应该在C中实现types。
以下是使用密钥进行哈希和相等的示例：
class A(object): def __key(self): return (self.attr_a, self.attr_b, self.attr_c) def __eq__(x, y): return x.__key() == y.__key() def __hash__(self): return hash(self.__key())
另外， __hash__的文档有更多的信息，这在某些特定情况下可能是有价值的。
微软研究院的Paul Larson研究了各种散列函数。 他告诉我
for c in some_string: hash = 101 * hash + ord(c)
对于各种各样的string，出人意料地工作得很好。 我发现类似的多项式技术适用于计算不同子域的散列。
John Millikin提出了一个类似于这样的解决scheme：
class A(object): def __init__(self, a, b, c): self._a = a self._b = b self._c = c def __eq__(self, othr): return ((self._a, self._b, self._c) == (othr._a, othr._b, othr._c)) def __hash__(self): return hash((self._a, self._b, self._c))
这个解决scheme的问题是hash(A(a, b, c)) == hash((a, b, c)) 。 换句话说，哈希与其关键成员的元组相冲突。 也许这在实践中经常不重要？
__hash__上的Python文档build议使用类似XOR的子组件的哈希值，这给了我们这个：
class B(object): def __init__(self, a, b, c): self._a = a self._b = b self._c = c def __eq__(self, othr): return (isinstance(othr, type(self)) and (self._a, self._b, self._c) == (othr._a, othr._b, othr._c)) def __hash__(self): return (hash(self._a) ^ hash(self._b) ^ hash(self._c) ^ hash((self._a, self._b, self._c)))
奖金：更加强大的__eq__被扔在那里为好措施。
更新：正如Blckknght指出的那样，更改a，b和c的顺序可能会导致问题。 我添加了一个额外的^ hash((self._a, self._b, self._c))来捕获被哈希值的顺序。 如果组合的值不能被重新排列（例如，如果它们具有不同的types，因此_a的值永远不会被分配给_b或_c等），则最后的^ hash(...)可以被移除。
我可以尝试回答你的问题的第二部分。
碰撞可能不是来自哈希码本身，而是将哈希码映射到集合中的索引。 所以例如你的散列函数可以返回从1到10000的随机值，但是如果你的散列表只有32个条目，你将在插入时得到冲突。
另外，我认为碰撞可以由内部的集合来解决，并且有很多方法来解决冲突。 最简单的（也是最糟糕的）是给定一个条目插入索引i，给我加1，直到find一个空的地方并插入。 检索然后以相同的方式工作。 这会导致一些条目的检索效率低下，因为您可能需要遍历整个集合的条目来查找！
其他冲突解决方法通过在插入项目时散列表中的条目来减less检索时间。 这会增加插入时间，但是假设您阅读的内容比插入内容更多。 也有尝试和分支不同的碰撞条目的方法，以便在一个特定点聚集入口。
另外，如果您需要调整集合的大小，您将需要重新刷新所有内容或使用dynamic哈希方法。
总之，根据你使用的散列码你可能不得不实现你自己的冲突解决方法。 如果你没有把它们存储在一个集合中，你可能会放弃一个散列函数，它只是在很大的范围内生成散列码。 如果是这样，你可以确保你的容器比需要的更大（当然越大越好），这取决于你的记忆问题。
这里有一些链接，如果你更感兴趣：
在维基百科上合并哈希
维基百科也有各种冲突解决方法的总结 ：
此外，Tharp的“ 文件组织和处理 ”广泛地涵盖了许多碰撞解决方法。 国际海事组织是散列algorithm的一个很好的参考。
取决于你返回的散列值的大小。 这很简单的逻辑，如果你需要返回一个基于四个32位整数散列的32位整数，你会得到冲突。
我会倾向于位操作。 就像下面的C伪码：
int a; int b; int c; int d; int hash = (a & 0xF000F000) | (b & 0x0F000F00) | (c & 0x00F000F0 | (d & 0x000F000F);
这样的系统也可以用于漂浮，如果你只是把它们作为它们的位值，而不是实际上代表浮点值，那么也许更好。
对于string，我有点不知道。
