python - 辞書のハッシュ関数を変更する

Question

この質問に続いて、2 つの異なる辞書がまったく同じハッシュ関数を使用してdict_1いることがわかります。dict_2

辞書で使用されるハッシュ関数を変更する方法はありますか? _{マイナス回答もOK！}

Answer 1

ハッシュ関数を変更することはできません.dictはhash挿入するはずのキーを呼び出します.それだけです.

ただし、キーをラップして別__hash__の__eq__メソッドを提供できます。

class MyHash(object):
     def __init__(self, v):
         self._v = v

     def __hash__(self):
         return hash(self._v) * -1

     def __eq__(self, other):
         return self._v == other._v

これが実際にあなたの元の問題/質問に何か役立つとは思えませんが、カスタム配列/リストベースのデータ構造が答えかもしれません。か否か。

Answer 2

リストのリストの上に「ハッシュ テーブル」があり、各ハッシュ テーブル オブジェクトが特定のハッシュ関数に関連付けられています。

class HashTable(object):
    def __init__(self, hash_function, size=256):
        self.hash_function = hash_function
        self.buckets = [list() for i in range(size)]
        self.size = size

    def __getitem__(self, key):
        hash_value = self.hash_function(key) % self.size
        bucket = self.buckets[hash_value]
        for stored_key, stored_value in bucket:
            if stored_key == key:
                return stored_value
        raise KeyError(key)


    def __setitem__(self, key, value):
        hash_value = self.hash_function(key) % self.size
        bucket = self.buckets[hash_value]
        i = 0
        found = False
        for stored_key, stored_value in bucket:
            if stored_key == key:
                 found = True
                 break
            i += 1
        if found:
            bucket[i] = (key, value)
        else:
            bucket.append((key, value))

アプリケーションの残りの部分は、引き続きバケットの基になるリストを表示できます。アプリケーションでは、各バケットに関連付ける追加のメタデータが必要になる場合がありますが、それは単純なリストではなく、バケット リストの要素に対して新しいクラスを定義するのと同じくらい簡単です。

Answer 3

あなたが望むのは、バケットを作成する方法だと思います。これに基づいてcollections.defaultdict、setイニシャライザを「バケット」として使用することをお勧めします（ただし、使用目的によって異なります）。

以下にサンプルを示します。

#!/usr/bin/env python

from collections import defaultdict
from itertools import combinations

d = defaultdict(set)

strs = ["str", "abc", "rts"]
for s in strs:
    d[hash(s)].add(s)
    d[hash(''.join(reversed(s)))].add(s)

for combination in combinations(d.values(), r=2):
    matches = combination[0] & combination[1]
    if len(matches) > 1:
        print matches

# output: set(['str', 'rts'])

ここで同じバケットに入る 2 つの文字列は、同じである可能性が非常に高くなります。reverse 関数を使用し、文字列を使用してハッシュ衝突を作成しましたが、値として逆になっています。

セットは完全な比較を使用しますが、非常に高速に実行する必要があることに注意してください。

セットを空にすることなく、あまりにも多くの値をハッシュしないでください。