Поскольку списки являются изменяемыми, ключи dict (и set члены) должны быть хешируемыми, а хеширование изменяемых объектов - плохая идея, поскольку хеш-значения должны вычисляться на основе атрибутов экземпляра. .
В этом ответе я приведу несколько конкретных примеров, надеюсь, добавляя ценность поверх существующих ответов. Каждое понимание относится и к элементам структуры данных set.
Пример 1 : хэширование изменяемого объекта, где значение хеш-функции основано на изменяемой характеристике объекта.
>>> class stupidlist(list):
... def __hash__(self):
... return len(self)
...
>>> stupid = stupidlist([1, 2, 3])
>>> d = {stupid: 0}
>>> stupid.append(4)
>>> stupid
[1, 2, 3, 4]
>>> d
{[1, 2, 3, 4]: 0}
>>> stupid in d
False
>>> stupid in d.keys()
False
>>> stupid in list(d.keys())
True
После мутации stupid его больше нельзя найти в диктовке, поскольку хэш изменился. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Стр. 101
Пример 2 : ... но почему не просто постоянное хеш-значение?
>>> class stupidlist2(list):
... def __hash__(self):
... return id(self)
...
>>> stupidA = stupidlist2([1, 2, 3])
>>> stupidB = stupidlist2([1, 2, 3])
>>>
>>> stupidA == stupidB
True
>>> stupidA in {stupidB: 0}
False
Это тоже не очень хорошая идея, потому что одинаковые объекты должны хешироваться одинаково, так что вы можете найти их в dict или set.
Пример 3 : ... хорошо, а как насчет постоянных хэшей во всех случаях?!
>>> class stupidlist3(list):
... def __hash__(self):
... return 1
...
>>> stupidC = stupidlist3([1, 2, 3])
>>> stupidD = stupidlist3([1, 2, 3])
>>> stupidE = stupidlist3([1, 2, 3, 4])
>>>
>>> stupidC in {stupidD: 0}
True
>>> stupidC in {stupidE: 0}
False
>>> d = {stupidC: 0}
>>> stupidC.append(5)
>>> stupidC in d
True
Кажется, что все работает так, как ожидалось, но подумайте о том, что происходит: когда все экземпляры вашего класса выдают одно и то же значение хеш-функции, у вас будет коллизия хэшей, если в ключе dict или присутствует более двух экземпляров в качестве ключей в set.
Для нахождения правильного экземпляра с помощью my_dict[key] или key in my_dict (или item in my_set) необходимо выполнить столько проверок на равенство, сколько имеется экземпляров stupidlist3 в ключах диктовки (в худшем случае). На этом этапе цель словаря - поиск O (1) - полностью побеждена. Это демонстрируется в следующие моменты времени (сделано с IPython).
Некоторые сроки для примера 3
>>> lists_list = [[i] for i in range(1000)]
>>> stupidlists_set = {stupidlist3([i]) for i in range(1000)}
>>> tuples_set = {(i,) for i in range(1000)}
>>> l = [999]
>>> s = stupidlist3([999])
>>> t = (999,)
>>>
>>> %timeit l in lists_list
25.5 µs ± 442 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> %timeit s in stupidlists_set
38.5 µs ± 61.2 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> %timeit t in tuples_set
77.6 ns ± 1.5 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
Как вы можете видеть, тест членства в нашем stupidlists_set даже медленнее, чем линейное сканирование по всему lists_list, в то время как у вас есть ожидаемое сверхбыстрое время поиска (коэффициент 500) в наборе без нагрузок хэша столкновения.
TL; DR: вы можете использовать tuple(yourlist) как dict ключи, потому что кортежи являются неизменяемыми и хэшируемыми.