Pythonで不変の辞書をハッシュする

Question

短いバージョン：順序付けされていない項目の辞書として実装されたマルチセットに最適なハッシュアルゴリズムは何ですか？

私は不変マルチセット（他の言語ではバッグまたはマルチセットです：数学的なセットのように、各要素の複数を保持できる点を除いて）を辞書として実装しています。相対

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

は、アイテムの完全なタプルを作成する大量のメモリを占有します（：Python hashable dicts、ハッシュ関数ので、同じよう推奨しています。私はここでアドバイスと、同様の標準ライブラリのクラスcollections.Counterのサブクラスを作成しました例えば、ジェネレータを使用して）、ハッシュはアプリケーションのメモリを大量に消費する部分で発生します。さらに重要なのは、私の辞書キー（マルチセット要素）はおそらく注文可能ではないということです。

私はこのアルゴリズムを使用して考えている：私は使用して図

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

ビット単位のXORは、タプルのハッシュとは異なり、ハッシュ値のために重要ではありません順序を意味しますか？私は、データのタプルの順不同のストリームにPythonタプル・ハッシング・アロッグを半実装することができます。 https://github.com/jonashaag/cpython/blob/master/Include/tupleobject.h（「hash」という単語のページ内の検索）を参照してください。 - しかし、私はそれを読むのに十分なCをほとんど知っていません。

思考？提案？ありがとう。

---

（ 私はマルチセットをハッシュしようといじりよ、なぜあなたは迷っている場合：。私の問題のための入力データが多重集合の集合であり、マルチセットの各セットの中に、各マルチセットは一意である必要があります私は私はデッドラインで作業していますが、私は経験豊富なコーダーではありませんので、可能な限り新しいアルゴリズムを発明しないようにしたいと思っています。 set()が、物事はハッシュ可能でなければなりません。）私はコメントから収集した何

---

@marcinと@senderleはどちらも同じ答えを出しました：use hash(frozenset(self.items()))。これはitems() "views" are set-likeのため意味があります。 @marcinが最初でしたが、私は@ senderleにチェックマークを付けました。なぜなら、さまざまな解決策のための大きな実行時間についての良い研究のためです。 @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 

Answer 1

辞書は不変なので、あなたは辞書が作成されたときにハッシュを作成し、それを直接返すことができます。このコードに基づいて、さらにコメントや提案を歓迎している - これは私がすべてを実装しています方法です。私の提案はitems（3+で、iteritemsは2.7）からfrozensetを作成し、ハッシュし、そのハッシュを保存することです。私は、ソートされた項目のタプルに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は、（アイテムをソートする必要はありません明示的な例を提供するために、

初期ハッシュはO（n）時間ではなくO（n）時間で完了するはずです。これは、frozenset_hashおよびset_nextの実装から見ることができます。

Answer 2

hash(sorted(hash(x) for x in self.items()))とお考えですか？そうすれば、整数をソートするだけでリストを作成する必要はありません。

要素ハッシュを一緒にxorすることもできますが、率直に言って私はうまくいくわけではありません（多くの衝突がありますか？）。衝突について言えば、__eq__メソッドを実装する必要はありませんか？

また、私の答えhereと同様に、hash(frozenset(self.items()))と同様です。