19

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.

I.P. Freeley
  • 885
  • 1
  • 9
  • 19
  • 2
    If the lists don't have duplicate elements, you can [use `frozenset` keys](https://stackoverflow.com/questions/28566797/is-it-safe-to-use-frozen-set-as-dict-key). – Chris Martin Jan 26 '16 at 00:18
  • Duplicate of [Why can't I use a list as a dict key in python? - Stack Overflow](https://stackoverflow.com/questions/7257588/why-cant-i-use-a-list-as-a-dict-key-in-python) -- except that in this case you like the "list" to be unordered, so a frozen set is more suited. – user202729 May 23 '19 at 07:42

2 Answers2

24

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.

Adam Smith
  • 52,157
  • 12
  • 73
  • 112
5

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]))
Mark Mishyn
  • 3,921
  • 2
  • 28
  • 30