簡短版本：對於實現爲無序項目字典的多重集合，最佳散列算法是什麼？在Python中散列一個不可變的字典

我試圖散列一個不可變的multiset（這是一個袋子或multiset在其他語言：像一個數學集，但它可以容納多於一個的每個元素）實現爲一個字典。我創建了標準庫類collections.Counter的子類，類似的建議在這裏：相對

class FrozenCounter(collections.Counter): 
    # ... 
    def __hash__(self): 
     return hash(tuple(sorted(self.items())))

創建項目的完整元組佔用了大量的內存（：Python hashable dicts，其中建議哈希函數像這樣比如說，使用一個發生器），哈希將發生在我的應用程序的一個非常佔用內存的部分。更重要的是，我的字典鍵（multiset元素）可能不會是可訂購的。

我想用這個算法：

def __hash__(self): 
    return functools.reduce(lambda a, b: a^b, self.items(), 0)

我想使用按位異或意味着以便在不同的元組的哈希散列值不要緊？我想我可以在我的數據元組的無序流上半執行Python元組哈希算法。請參閱https://github.com/jonashaag/cpython/blob/master/Include/tupleobject.h（在頁面中搜索單詞'hash'） - 但我幾乎不知道C足夠閱讀它。

想法？建議？謝謝。

（ 如果你想知道爲什麼我有試圖哈希多集瞎搞：我的問題輸入數據是一組多集，並且每一組多集的範圍內，每多集必須是唯一的我。在最後期限之前工作，我不是一個有經驗的編碼員，所以我想避免在可能的情況下發明新的算法。看起來像確保我擁有一些獨特的Pythonic方法似乎是把它們放在一個 set()，但事情一定要哈希的。）

我已經從註釋收集

@marcin和@senderle都給出了幾乎相同的答案：使用hash(frozenset(self.items()))。這是有道理的，因爲items() "views" are set-like。 @marcin是第一個，但是我把複選標記給@senderle，因爲對不同解決方案的大O運行時間進行了很好的研究。 @marcin也讓我想起include an __eq__ method - 但是從dict繼承的那個將會工作得很好。這是我如何實現一切 - 在此基礎上進一步代碼的意見和建議，歡迎：

class FrozenCounter(collections.Counter): 
    # Edit: A previous version of this code included a __slots__ definition. 
    # But, from the Python documentation: "When inheriting from a class without 
    # __slots__, the __dict__ attribute of that class will always be accessible, 
    # so a __slots__ definition in the subclass is meaningless." 
    # http://docs.python.org/py3k/reference/datamodel.html#notes-on-using-slots 
    # ... 
    def __hash__(self): 
     "Implements hash(self) -> int" 
     if not hasattr(self, '_hash'): 
      self._hash = hash(frozenset(self.items())) 
     return self._hash

來源

2012-04-06 wkschwartz

任何可哈希的對象都是可訂購的。如果它是可散列的，那麼它總是產生相同的散列，所以在散列上排序。 – senderle 2012-04-06 15:33:17

你是否確保'tuple'佔用大量內存？它只是一個指向字典中每個項目的「指針」，而不是它的副本，它被創建。 – agf 2012-04-06 15:51:42

查看http://www.cs.toronto.edu/~tijmen/programming/immutableDictionaries.html – wkschwartz 2012-04-06 16:55:45

由於字典是不可改變的，您可以創建哈希創建字典時，直接返回。我的建議是從items（2.7中的3+; iteritems）創建一個frozenset，對其進行散列並存儲散列。

爲了提供一個明顯的例子：

>>>> frozenset(Counter([1, 1, 1, 2, 3, 3, 4]).iteritems()) 
frozenset([(3, 2), (1, 3), (4, 1), (2, 1)]) 
>>>> hash(frozenset(Counter([1, 1, 1, 2, 3, 3, 4]).iteritems())) 
-3071743570178645657 
>>>> hash(frozenset(Counter([1, 1, 1, 2, 3, 4]).iteritems())) 
-6559486438209652990

爲了澄清我爲什麼喜歡frozenset來排序項的元組：一個frozenset沒有對項目進行排序（因爲它們穩定地通過哈希值來排序在內存中），所以初始散列應該在O（n）時間內完成，而不是在O（n log n）時間內完成。這可以從frozenset_hash和set_next的實現中看出。

來源

2012-04-06 15:37:47 senderle

您考慮過hash(sorted(hash(x) for x in self.items()))嗎？這樣，你只是整理整數，而不必建立一個列表。

你也可以將元素哈希函數放在一起，但坦率地說，我不會很好地工作（你會有很多碰撞？）。說到碰撞，你不需要執行__eq__方法嗎？

或者，類似於我的回答here,hash(frozenset(self.items()))。

來源

2012-04-06 15:39:14 Marcin

在Python中散列一個不可變的字典

我已經從註釋收集

回答

相關問題