实现__hash__()的正确和好的方法是什么?

我说的是一个函数,它返回一个哈希码,然后用来将对象插入哈希表,也就是字典。

由于__hash__()返回一个整数,并用于将对象“装箱”到哈希表中,我假设返回的整数的值应该为公共数据均匀分布(以减少冲突)。 获得这些值的良好实践是什么?碰撞是个问题吗? 在我的例子中,我有一个小类,它作为一个容器类,包含一些int,一些浮点和字符串。


当前回答

John Millikin提出了一个类似的解决方案:

class A(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, self._b, self._c))

这个解决方案的问题是哈希(A(A, b, c)) ==哈希((A, b, c))。换句话说,哈希值与其关键成员的元组的哈希值发生碰撞。也许在实践中这并不重要?

更新:Python文档现在建议像上面的例子一样使用元组。注意,文档声明

唯一需要的属性是比较相等的对象具有相同的哈希值

请注意,相反的情况并非如此。比较不相等的对象可能具有相同的哈希值。这样的散列碰撞不会导致一个对象在用作dict键或set元素时替换另一个对象,只要对象之间的比较不相等。

过时的/糟糕的解决方案

__hash__的Python文档建议使用类似XOR的东西组合子组件的哈希值,这给了我们这样的结果:

class B(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __eq__(self, othr):
        if isinstance(othr, type(self)):
            return ((self._a, self._b, self._c) ==
                    (othr._a, othr._b, othr._c))
        return NotImplemented

    def __hash__(self):
        return (hash(self._a) ^ hash(self._b) ^ hash(self._c) ^
                hash((self._a, self._b, self._c)))

更新:正如blackknight所指出的,改变a、b和c的顺序可能会导致问题。我添加了一个额外的^ hash((self。_a,自我。_b, self._c))来捕获被散列的值的顺序。如果组合的值不能重新排列(例如,如果它们具有不同的类型,因此_a的值将永远不会被分配给_b或_c,等等),则可以删除最后的^哈希(…)。

其他回答

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

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

此外,我认为冲突将由集合内部解决,并且有许多解决冲突的方法。最简单的(也是最糟糕的)是,给定一个要在索引i插入的条目,将1加到i,直到找到一个空点并在那里插入。检索也以同样的方式工作。这将导致对某些条目的低效检索,因为您可能有一个条目需要遍历整个集合才能找到!

其他冲突解决方法通过在插入项以展开内容时移动哈希表中的条目来减少检索时间。这增加了插入时间,但假设读取的时间比插入的时间多。还有一些方法可以尝试将不同的碰撞条目分支出来,以便将条目聚集在一个特定的点上。

此外,如果您需要调整集合的大小,则需要重新散列所有内容或使用动态散列方法。

简而言之,根据您使用哈希代码的目的,您可能必须实现自己的冲突解决方法。如果你不把它们存储在一个集合中,你可能会使用一个哈希函数,它只生成一个非常大的范围内的哈希码。如果是这样,您可以确保您的容器比它需要的更大(当然越大越好),这取决于您的内存问题。

如果你感兴趣,这里有一些链接:

维基百科上的联合哈希

维基百科也总结了各种冲突解决方法:

此外,Tharp的“文件组织和处理”广泛地涵盖了许多冲突解决方法。在我看来,这是哈希算法的一个很好的参考。

programiz网站上有一个关于何时以及如何实现__hash__函数的很好的解释:

只是一个截图来提供一个概述: 检索(2019-12-13)

至于该方法的个人实现,上面提到的站点提供了一个与millerdev的答案相匹配的示例。

class Person:
def __init__(self, age, name):
    self.age = age
    self.name = name

def __eq__(self, other):
    return self.age == other.age and self.name == other.name

def __hash__(self):
    print('The hash is:')
    return hash((self.age, self.name))

person = Person(23, 'Adam')
print(hash(person))

微软研究院的Paul Larson研究了各种各样的哈希函数。他告诉我

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

工作令人惊讶的好,各种各样的字符串。我发现类似的多项式技术可以很好地计算不同子字段的散列。

@dataclass(frozen=true) (Python 3.7)

这个很棒的新特性,除其他优点外,自动为你定义__hash__和__eq__方法,使其在dicts和set中正常工作:

dataclass_cheat.py

from dataclasses import dataclass, FrozenInstanceError

@dataclass(frozen=True)
class MyClass1:
    n: int
    s: str

@dataclass(frozen=True)
class MyClass2:
    n: int
    my_class_1: MyClass1

d = {}
d[MyClass1(n=1, s='a')] = 1
d[MyClass1(n=2, s='a')] = 2
d[MyClass1(n=2, s='b')] = 3
d[MyClass2(n=1, my_class_1=MyClass1(n=1, s='a'))] = 4
d[MyClass2(n=2, my_class_1=MyClass1(n=1, s='a'))] = 5
d[MyClass2(n=2, my_class_1=MyClass1(n=2, s='a'))] = 6

assert d[MyClass1(n=1, s='a')] == 1
assert d[MyClass1(n=2, s='a')] == 2
assert d[MyClass1(n=2, s='b')] == 3
assert d[MyClass2(n=1, my_class_1=MyClass1(n=1, s='a'))] == 4
assert d[MyClass2(n=2, my_class_1=MyClass1(n=1, s='a'))] == 5
assert d[MyClass2(n=2, my_class_1=MyClass1(n=2, s='a'))] == 6

# Due to `frozen=True`
o = MyClass1(n=1, s='a')
try:
    o.n = 2
except FrozenInstanceError as e:
    pass
else:
    raise 'error'

正如我们在这个例子中看到的,哈希值是基于对象的内容计算的,而不仅仅是基于实例的地址。这就是为什么会有这样的事情:

d = {}
d[MyClass1(n=1, s='a')] = 1
assert d[MyClass1(n=1, s='a')] == 1

即使第二个MyClass1(n=1, s='a')是一个与第一个完全不同的实例,具有不同的地址,也可以工作。

frozen=True是强制的,否则类是不可哈希的,否则用户可能会在容器用作键后修改对象而无意中使容器不一致。更多文档:https://docs.python.org/3/library/dataclasses.html

在Python 3.10.7, Ubuntu 22.10上测试。

实现__hash__()的一个简单、正确的方法是使用键元组。它不会像专用散列那样快,但如果你需要,那么你可能应该在C中实现该类型。

下面是一个使用键进行哈希和相等的例子:

class A:
    def __key(self):
        return (self.attr_a, self.attr_b, self.attr_c)

    def __hash__(self):
        return hash(self.__key())

    def __eq__(self, other):
        if isinstance(other, A):
            return self.__key() == other.__key()
        return NotImplemented

此外,__hash__的文档有更多信息,在某些特定情况下可能很有价值。