在Python中使整数列表可哈希化

Question

我有一个整数列表，我想在Python字典中将其用作键。我正在缓存从接受整数列表作为输入的函数(s)返回的结果。我的当前解决方案：

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

生成键'1,3,4,20'。似乎应该有一种更快/更漂亮/更Pythonic的方法来做这个。

- I.P. Freeley

---

如果列表中没有重复元素，你可以使用frozenset作为键值（参考链接：https://dev59.com/R14b5IYBdhLWcg3w5VP9）。 - Chris Martin

这是 为什么不能在Python中使用列表作为字典键？- Stack Overflow 的副本，但在这种情况下，您希望“列表”是无序的，因此冻结集更适合。 - user202729

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对象是不可变的、可哈希的类似于set的对象。它们不考虑顺序并忽略重复项。

- Adam Smith

---

我想我应该补充一下，整数的顺序并不重要，所以我认为我仍然希望在其中加入排序，但是这样写起来更简洁：key=tuple(sorted(list_of_ints)) - I.P. Freeley

“容器”如果不考虑顺序，最好实现为frozenset(...)而不是tuple(sorted(...))。话虽如此，您的容器仍然缺少许多方法——.pop、.get、.setdefault和可能还有其他我暂时想不起来的方法... - mgilson

@mgilson 说得好，但我不想砍掉大量的代码，所以我会在答案中写一条注释。 - Adam Smith

@AdamSmith -- 啊，这是个好观点。我没想到。叹气 那就是N-LogN了…… - mgilson

是的，我不应该有重复值，所以我认为frozenset就是我要找的答案。 - I.P. Freeley

Answer 2

你也可以创建可哈希的列表。

from collections import Iterable

class hash_list(list): 
    def __init__(self, *args): 
        if len(args) == 1 and isinstance(args[0], Iterable): 
            args = args[0] 
        super().__init__(args) 
         
    def __hash__(self): 
        return hash(e for e in self)

现在这个功能可以使用：

hash(hash_list(1, 2, 3))

或者

hash(hash_list([1, 2, 3]))

- Mark Mishyn

---

可能是一个愚蠢的问题，但如果你要将类型更改为生成器，为什么不直接使用元组？ - Sujal Singh

@SujalSingh 有时候你需要可变且可哈希的序列。 - Mark Mishyn