Make a list of ints hashable in python

Question

I have a lists of integers that I would like to use as keys in python dictionaries. I'm caching results from a function(s) that takes a list of ints as input. My current solution:

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

which generates the key '1,3,4,20'. Seems like there should be a faster/prettier/more-pythonic way to do this.

Solution 1

Just use a tuple as a key. Tuples are immutable and hashable, so they're useful as dictionary keys.

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

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

Notably they DO care about order, so [1, 20, 3, 4] won't produce the same value as [1, 3, 20, 4]

You could even create a container that does this for you.

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

Don't try to serialize it yourself. If you do, don't use string manipulation -- it's too ugly. If you are sincerely memory starved or you have hundreds of thousands of these records, you could save insignificant space by serializing like:

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_

which should give you a unique (incredibly large!) integer to store that will be smaller in memory than the tuple. Don't do this if you can avoid it -- it's very opaque.

---

In the comments you mention you will not have duplicate values in the key, so frozenset is definitely what you're looking for.

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

frozenset objects are immutable hashable set-like objects. They are order-agnostic and ignore duplicates.

Solution 2

You also can create hashable list.

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)

And now this works:

hash(hash_list(1, 2, 3))

or

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

Comments

[I.P. Freeley]

I guess I should add that the order of the ints doesn't matter, so I think I still want the sorted in there, but: key=tuple(sorted(list_of_ints)) is a lot prettier.

[Adam Smith]

@I.P.Freeley are there always 4 ints?

[I.P. Freeley]

No, variable length.

[Peter Wood]

The order of the function parameters doesn't matter? How strange.

[Tom Dalton]

It's pretty common - e.g. sum(), multiply()

[mgilson]

The "container" that is order agnostic would probably be better if implemented as a frozenset(...) rather than tuple(sorted(...)). With that said, your container is still missing a bunch of methods -- .pop, .get, .setdefault and probably others that I'm not remembering at the moment. . .

[Adam Smith]

@mgilson fair point, but I don't feel like hacking away a ton of code so I'll just write a note in the answer.

[Adam Smith]

@mgilson frozenset only works if (1, 2, 3) is identical to (1, 2, 3, 3) which seems like a stretch

[mgilson]

@AdamSmith -- Ahh, that's a good point. I didn't think of that. sigh N-LogN it is then . . .

[I.P. Freeley]

Yes, I should not have repeat values, so I think frozenset is the answer I'm looking for.

[Sujal Singh]

Might be a stupid question but If you are changing the type to a generator why not just use a tuple?

[Mark Mishyn]

@SujalSingh sometimes you need mutable and at the same time hashable sequence.