在python中生成可哈希的整数列表

Question

我有一个整数列表，我想用作python字典中的键。我正在缓存将一个int列表作为输入的函数的结果。我当前的解决方案：

list_of_ints = [1,20,3,4]
key = str(sorted(list_of_ints))[1:-1].replace(' ','')

生成密钥'1,3,4,20'。似乎应该有一种更快/更漂亮/更pythonic的方式来做到这一点。

Answer 1

只需使用元组作为键。元组是不可变且可哈希的，因此它们可用作字典键。

list_of_ints = [1, 20, 3, 4]
# tuple(list_of_ints) == (1, 20, 3, 4)

some_dict = {tuple(list_of_ints): "some value", ...}

[值得注意的是，他们确实关心顺序，因此[1, 20, 3, 4]不会产生与[1, 3, 20, 4]相同的值

您甚至可以创建一个为您执行此操作的容器。

class MyDict(dict):
    def __getitem__(self, key):
        key = tuple(sorted(key))
        return super().__getitem__(key)
    # similar for pop, get, setdefault, update....

>>> d = MyDict()
>>> d[1,2,3] = 4
>>> d[3,2,1]
4

不要尝试自己序列化它。如果这样做，请不要使用字符串操作-这太难看了。如果您确实因内存不足而饥饿，或者您有成千上万的此类记录，则可以通过序列化来节省微不足道的空间，例如：

def my_serialize(key_nums: list):
    key_nums = sorted(key_nums)
    base = max(key_nums)
    sum_ = 0
    for power, num in enumerate(key_nums):
        sum_ += base**power * num
    return sum_

应该为您提供一个唯一的（非常大！）整数来存储，该整数将在内存中小于元组。如果可以避免，请不要这样做-它非常不透明。

---

在您提到的注释中，键中将没有重复的值，因此frozenset绝对是您想要的。

d = {}
list_of_ints = [1, 20, 3, 4]
d[frozenset(list_of_ints)] = "some value"

frozenset对象是不可变的可哈希frozenset类对象。它们与订单无关，并且忽略重复项。

Answer 2

您也可以创建可哈希列表。

set