改变字典的散列函数

Question

根据这个，我们知道两个不同的字典，例如dict_1和dict_2，使用完全相同的散列函数。

有什么办法可以改变字典使用的哈希函数吗？_{否定的答案也接受！}

Answer 1

您不能更改散列函数 - 字典将调用 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

如果这实际上对您的原始 problem/question 有任何帮助，我怀疑，但似乎自定义 array/list-based 数据结构可能是答案。还是不行。

Answer 2

这是列表列表顶部的 "hash table"，其中每个散列 table 对象都与特定的散列函数相关联。

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))

您的应用程序的其余部分仍然可以看到存储桶的基础列表。您的应用程序可能需要将额外的元数据与每个存储桶相关联，但这就像为存储桶列表的元素而不是普通列表定义新的 class 一样简单。

Answer 3

我认为您想要的是一种创建 存储桶 的方法。基于此，我建议使用 collections.defaultdict 和 set 初始值设定项作为 "bucket"（不过取决于您使用它的目的）。

这是一个示例：

#!/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'])

两个字符串在此处相同的桶中结束非常可能相同。我通过使用反向函数并使用字符串创建了哈希冲突，它作为值反向。

请注意，集合将使用完全比较，但应该非常快。

不要在不耗尽集合的情况下散列太多值。

改变字典的散列函数

Alter the hash function of a dictionary

python

hash

dictionary

python-2.7

locality-sensitive-hash