Почему я не могу использовать список в качестве ключа dict в Python?

Я немного смущен тем, что можно / нельзя использовать в качестве ключа для Python dict.

dicked = {}
dicked[None] = 'foo'     # None ok
dicked[(1,3)] = 'baz'    # tuple ok
import sys
dicked[sys] = 'bar'      # wow, even a module is ok !
dicked[(1,[3])] = 'qux'  # oops, not allowed

Итак, кортеж - это неизменяемый тип, но если я спрячу в него список, то он не может быть ключом ... не мог бы я так же легко скрыть список внутри модуля?

У меня было смутное представление о том, что ключ должен быть «хешируемым», но я просто собираюсь признать свое незнание технических деталей; Я не знаю, что здесь происходит на самом деле. Что бы пошло не так, если бы вы попытались использовать списки в качестве ключей, с хешем, скажем, в качестве места в памяти?

В вики Python есть хорошая статья по этой теме: Почему списки не могут быть ключами словаря . Как объясняется там:

Что бы пошло не так, если бы вы попытались использовать списки в качестве ключей, с хешем, скажем, в качестве места в памяти?

Это можно сделать, не нарушая никаких требований, но это приводит к неожиданному поведению. Списки обычно обрабатываются так, как если бы их значение было получено из значений их содержимого, например, при проверке (несоответствия) равенства. Многие, по понятным причинам, ожидали бы, что вы можете использовать любой список [1, 2]для получения одного и того же ключа, в то время как вам нужно будет оставить один и тот же объект списка. Но поиск по значению прерывается, как только список, используемый в качестве ключа, изменяется, а для поиска по идентификатору требуется, чтобы вы держали точно такой же список - что не требуется для любой другой общей операции со списком (по крайней мере, я не могу вспомнить ).

Другие объекты, такие как модули object, в любом случае делают гораздо большую работу из своей идентичности объекта (когда в последний раз вы вызывали два разных объекта модуля sys?), И все равно сравниваются с этим. Поэтому менее удивительно - или даже ожидалось - то, что они, при использовании в качестве ключей dict, в этом случае также сравниваются по идентичности.

Почему я не могу использовать список в качестве ключа dict в Python?

>>> d = {repr([1,2,3]): 'value'}
{'[1, 2, 3]': 'value'}

(для всех, кто сталкивается с этим вопросом и ищет способ его обойти)

как объясняют другие здесь, вы действительно не можете. Однако вы можете использовать его строковое представление, если действительно хотите использовать свой список.

Только что обнаружил, что вы можете преобразовать List в кортеж, а затем использовать его в качестве ключей.

d = {tuple([1,2,3]): 'value'}

Проблема в том, что кортежи неизменяемы, а списки - нет. Рассмотрим следующие

d = {}
li = [1,2,3]
d[li] = 5
li.append(4)

Что должно d[li] вернуть? Это тот же список? Как насчет d[[1,2,3]]? У него те же значения, но это другой список?

В конечном счете, удовлетворительного ответа нет. Например, если работает только исходный ключ, то, если у вас нет ссылки на этот ключ, вы больше никогда не сможете получить доступ к значению. С любым другим разрешенным ключом вы можете создать ключ без ссылки на оригинал.

Если оба моих предложения работают, значит, у вас очень разные ключи, которые возвращают одно и то же значение, что более чем удивительно. Если работает только исходное содержимое, то ваш ключ быстро испортится, поскольку списки создаются для изменения.

Вот ответ http://wiki.python.org/moin/DictionaryKeys

Что бы пошло не так, если бы вы попытались использовать списки в качестве ключей, с хешем, скажем, в качестве места в памяти?

Поиск разных списков с одинаковым содержимым даст разные результаты, даже если сравнение списков с одинаковым содержимым укажет на их эквивалент.

А как насчет использования литерала списка в поиске по словарю?

Поскольку списки изменяемы, 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он больше не может быть найден в dict, потому что хеш изменился. Только линейное сканирование по списку ключей dict находитstupid .

Пример 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]or key in my_dict(или item in my_set) необходимо выполнить столько проверок равенства, сколько экземпляров stupidlist3в ключах dict (в худшем случае). На этом этапе цель словаря - поиск 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ключей, потому что кортежи неизменяемы и хешируются.

Ваш тент можно найти здесь:

Почему списки не могут быть ключами словаря

Новички в Python часто задаются вопросом, почему, хотя язык включает в себя как кортеж, так и тип списка, кортежи можно использовать в качестве ключей словаря, а списки - нет. Это было преднамеренное дизайнерское решение, и его лучше всего объяснить, сначала поняв, как работают словари Python.

Источник и дополнительная информация: http://wiki.python.org/moin/DictionaryKeys

Простой ответ на ваш вопрос заключается в том, что список классов не реализует хэш метода, который требуется для любого объекта, который желает использовать в качестве ключа в словаре. Однако причина, по которой хеш не реализован так же, как, скажем, в классе кортежей (на основе содержимого контейнера), заключается в том, что список является изменяемым, поэтому редактирование списка потребует пересчета хеша, что может означать список в теперь находится не в том сегменте в подчиненной хеш-таблице. Обратите внимание: поскольку вы не можете изменить кортеж (неизменяемый), он не сталкивается с этой проблемой.

В качестве примечания, фактическая реализация поиска диктобъектов основана на алгоритме D из Knuth Vol. 3, п. 6.4. Если у вас есть эта книга, ее стоит прочитать, кроме того, если вы действительно очень заинтересованы, вы можете взглянуть на комментарии разработчиков по поводу фактической реализации dictobject здесь. Он очень подробно описывает, как именно это работает. Существует также лекция на Python о реализации словарей, которая может вас заинтересовать. В течение первых нескольких минут они проходят через определение ключа и того, что такое хэш.

Согласно документации Python 2.7.2:

Объект является хешируемым, если у него есть хеш-значение, которое никогда не меняется в течение его времени существования (ему нужен метод hash ()), и его можно сравнивать с другими объектами (ему нужен метод eq () или cmp ()). Хэшируемые объекты, которые сравнивают равные, должны иметь одинаковое хеш-значение.

Hashability делает объект пригодным для использования в качестве ключа словаря и члена набора, поскольку эти структуры данных используют хеш-значение внутри.

Все неизменяемые встроенные объекты Python являются хешируемыми, а изменяемые контейнеры (например, списки или словари) - нет. Объекты, которые являются экземплярами определенных пользователем классов, по умолчанию хешируются; все они сравниваются неравно, и их хеш-значение - это их id ().

Кортеж неизменен в том смысле, что вы не можете добавлять, удалять или заменять его элементы, но сами элементы могут быть изменяемыми. Хеш-значение списка зависит от хеш-значений его элементов, поэтому оно изменяется при изменении элементов.

Использование идентификаторов для хэшей списков означало бы, что все списки сравниваются по-разному, что было бы удивительно и неудобно.

Словарь - это HashMap, в котором хранится карта ваших ключей, значение, преобразованное в новый хешированный ключ, и сопоставление значений.

что-то вроде (псевдо-код):

{key : val}  
hash(key) = val

Если вам интересно, какие из доступных опций можно использовать в качестве ключа для вашего словаря. затем

все, что является хешируемым (может быть преобразовано в хэш и содержать статическое значение, т.е. неизменяемое, чтобы создать хешированный ключ, как указано выше), имеет право, но поскольку список или набор объектов могут изменяться на ходу, поэтому хэш (ключ) также должен варьироваться, чтобы синхронизироваться с вашим списком или набором.

Можешь попробовать :

hash(<your key here>)

Если он работает нормально, его можно использовать в качестве ключа для вашего словаря или преобразовать во что-то хешируемое.

Коротко :

1. Преобразуйте этот список в tuple(<your list>).
2. Преобразуйте этот список в str(<your list>).

dictключи должны быть хешируемыми. Списки изменяемы и не предоставляют допустимого метода хеширования .