什么是实现__hash __（）的正确和好方法？

Question

什么是实施__hash__()的正确和好方法？

我在说的函数返回一个哈希码，然后用来插入对象到哈希表又名字典。

由于__hash__()返回一个整数，用于将对象“装箱”到散列表我假设返回的整数的值应该为公共数据均匀分布（以最小化冲突）。 获取此类值的最佳做法是什么？碰撞是一个问题吗？ 在我的情况下，我有一个小类，它充当一个容器类，它包含一些整数，一些浮点数和一个字符串。

Answer 1

实现__hash__()的简单而正确的方法是使用关键元组。这不会是一个专门的哈希值作为快，但是如果你需要，那么你或许应该实现C.

类型下面是一个使用密钥散列和平等的例子：

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()) 

此外，documentation of __hash__有更多信息，这在某些特定情况下可能很有价值。

Answer 2

取决于您返回的散列值的大小。这很简单的逻辑，如果你需要返回一个基于四个32位整数散列的32位整数，你会得到冲突。

我喜欢位操作。像，下面的C伪代码：

int a; 
int b; 
int c; 
int d; 
int hash = (a & 0xF000F000) | (b & 0x0F000F00) | (c & 0x00F000F0 | (d & 0x000F000F); 

这样的系统可以为彩车工作过，如果你只是把他们作为自己的位值而不是实际代表浮点值，也许更好。

对于字符串，我很少/不知道。

Answer 3

我可以尝试回答你的问题的第二部分。

碰撞可能不是哈希码本身，而是哈希码映射到集合中的索引。例如，你的散列函数可以返回从1到10000的随机值，但是如果你的散列表只有32个条目，你会在插入时发生冲突。

此外，我认为冲突将由内部集合来解决，并且有许多方法可以解决冲突。最简单的（也是最差的）是，如果在索引i处插入一个条目，则向我加1，直到找到一个空的点并插入为止。检索然后以相同的方式工作。这会导致对某些条目的检索效率低下，因为您可能有一个条目需要遍历整个集合才能找到！

其他冲突解决方法通过在插入项目以扩散事件时移动散列表中的条目来减少检索时间。这会增加插入时间，但假设您阅读的内容比插入内容更多。还有一些方法可以尝试并分支出不同的碰撞条目，从而使条目能够聚集在一个特定的点上。另外，如果您需要调整集合的大小，您需要重新提供一切或使用动态哈希方法。

总之，根据你使用的散列码你可能必须实现你自己的冲突解决方法。如果你没有将它们存储在一个集合中，那么你可能会用一个散列函数，它只是在很大范围内生成散列码。如果是这样，你可以确定你的容器比需要的大（当然越大越好），这取决于你的记忆问题。

这里有一些链接，如果你有兴趣更多：

coalesced hashing on wikipedia

维基百科也有各种冲突解决方法summary：

此外，“File Organization And Processing”的撒普涵盖碰撞的很多解决方法广泛。 IMO是哈希算法的一个很好的参考。

Answer 4

微软研究院的Paul Larson研究了各种散列函数。他告诉我，

for c in some_string: 
    hash = 101 * hash + ord(c) 

工作出奇的很好的各种各样的字符串。我发现类似的多项式技术适用于计算不同子域的散列。

Answer 5

约翰·米利金提出一个类似的解决方案：

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)) 

这种解决方案的问题是，hash(A(a, b, c)) == hash((a, b, c))。换句话说，散列与其关键成员的元组相冲突。也许这在实践中经常不重要？

的Python documentation on __hash__建议使用类似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))来捕获被哈希值的顺序。如果要组合的值不能重新排列（例如，如果它们具有不同的类型，因此_a的值永远不会被分配给_b或_c等），则可以移除该最终的^ hash(...)。