忽略顺序的集合哈希函数

Question

我正在使用hash()函数来获取包含两个整数和两个字符串的对象的哈希值。我有一个字典用来存储这些对象。我的流程是：如果该对象的哈希值存在，则更新，否则插入新的对象。

问题在于，在创建对象时，我不知道对象变量的顺序，而且我希望无论这些变量的顺序如何，都将对象视为相同。

是否有替代hash()函数的函数，它不考虑变量的顺序？

#Consequently what I want is:
hash((int1,str1,int2,str2)) == hash((int2,str2,int1,str1)) 

- 20-roso

---

你能否贴出一小段代码以更清晰地说明你在做什么？我的第一个想法是对这两个整数进行排序，但我无法确定这是否适用于你的实现。 - synchronizer

你可以随时对输入进行排序：hash(tuple(sorted((1, 2))))。 - Tom Lynch

@TomLynch 我展示了一个玩具例子，在我的代码中还有字符串，所以排序很困难。 - 20-roso

也许你应该修改问题，因为现在它强烈暗示你只期望那里有整数。 - Eleshar

@Eleshar 刚刚更新了。 - 20-roso

Answer 1

你可以使用frozenset而不是元组：

>>> hash(frozenset([1, 2, 'a', 'b']))
1190978740469805404
>>>
>>> hash(frozenset([1, 'a', 2, 'b']))
1190978740469805404
>>>
>>> hash(frozenset(['a', 2, 'b', 1]))
1190978740469805404

然而，从可迭代对象中去除重复项存在一个微妙的问题：

>>> hash(frozenset([1,2,1])) == hash(frozenset([1,2,2]))
True

您可以通过使用collections.Counter从可迭代对象创建计数器，并在计数器的条目上调用frozenset，从而保留每个项在原始可迭代对象中的计数。

>>> from collections import Counter
>>>
>>> hash(frozenset(Counter([1,2,1]).items())) 
-307001354391131208
>>> hash(frozenset(Counter([1,1,2]).items()))
-307001354391131208
>>> 
>>> hash(frozenset(Counter([1,2,1]).items())) == hash(frozenset(Counter([1,2,2]).items()))
False

- Moses Koledoye

---

它之所以有效，是因为每个集合中的元素数量相同，因此即使存在重复项也没有关系。 - Jean-François Fabre

@Jean-FrançoisFabre 感谢您的观察，这揭示了一个 bug :) - Moses Koledoye

虽然这不是 OP 问题的错误。 - Jean-François Fabre

FrozenMultiset() 也可以解决这个重复问题 https://pypi.python.org/pypi/multiset - Chris_Rands

@Chris_Rands 不错！collections.Counter对象是一个多重集合。我猜他们的FrozenMultiset实现下面有某种计数器。我认为你可以将链接和一些片段组成一个答案。 - Moses Koledoye

Answer 2

通常这种情况下，如果您能够发布一些示例代码，会对问题的解决非常有帮助，但我假设您已经有了类似以下的代码：

class Foo():
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __hash__(self):
        return hash((self.x, self.y))

你在对一个元组进行哈希操作，这个操作会考虑元素的顺序。如果你不想考虑整数的顺序，请使用frozenset：

    def __hash__(self):
        return hash(frozenset([self.x, self.y]))

- ymbirtt

---

@Jean-FrançoisFabre 哎呀！我是指冻结集合。 - ymbirtt

考虑到关于包括字符串的评论，我认为这是正确的答案！定义一个类，并使用它来指定您想要的哈希方法。 - aghast

@ymbirtt 刚刚点了个赞，谢谢你的努力。很抱歉没有使用字符串造成的混淆。 - 20-roso

Answer 3

如果数值的范围不是太大，可以将它们相加，这样顺序就可以被忽略，但会增加2个哈希值具有相同值的可能性。

def hash_list(items):
    value = 0
    for item in items:
        value+= hash(item)
    return value

hash_list(['a', 'b', 'c'])
>>> 8409777985338339540
hash_list(['b', 'a', 'c'])
>>> 8409777985338339540

- Markbarian