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

103

Я немного смущен тем, что можно / нельзя использовать в качестве ключа для 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

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

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

вим
источник
1
Вот хорошее обсуждение: stackoverflow.com/questions/2671211/…
Эрнан
50
Получил смешок от имени вашей переменной.
kindall

Ответы:

35

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

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

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

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


источник
32

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

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

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

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

Реми
источник
6
Извините, я не совсем понимаю вашу точку зрения. Это ничем не отличается от использования строковых литералов в качестве ключей.
wim
12
Правда; Я только что видел так много ответов, которые фактически объясняют, почему вы не можете использовать списки с точки зрения `` ключ должен быть хешируемым '', что настолько верно, что я хотел предложить способ обойти это, на случай, если кто-то (новый) будет его искать ...
Реми
5
Почему бы просто не преобразовать список в кортеж? Зачем преобразовывать его в строку? Если вы используете кортеж, он будет правильно работать с классами, у которых есть собственный метод сравнения __eq__. Но если вы конвертируете их в строки, все сравнивается по строковому представлению.
Аран-Фей
хороший момент @ Аран-Фей. Просто убедитесь, что любой элемент в кортеже сам по себе хешируется. например, tuple ([[1,2], [2,3]]) в качестве ключа не будет работать, потому что элементы кортежа все еще являются списками.
Реми
19

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

d = {tuple([1,2,3]): 'value'}
Нингронг Йе
источник
работал как шарм!
Табз
16

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

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

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

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

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

Эрик Уилсон
источник
Да, это тот же список, поэтому я ожидал, d[li]что останусь. 5. В d[[1,2,3]]качестве ключа будет ссылаться на другой объект списка, так что это будет KeyError. Я пока не вижу никаких проблем ... кроме того, что если позволить ключу собирать мусор, это может сделать некоторые значения dict недоступными. Но это практическая проблема, а не логическая проблема ..
wim
@wim: d[list(li)]наличие KeyError - часть проблемы. Почти каждый другой прецеденте , liбудет неотличим от нового списка с одинаковым содержимым. Это работает, но многим это противоречит интуиции. Кроме того, когда в последний раз вам действительно приходилось использовать список в качестве ключа dict? Единственный вариант использования, который я могу себе представить, - это когда вы все равно хешируете все по идентичности, и в этом случае вы должны просто делать это, вместо того, чтобы полагаться на идентичность __hash__и __eq__быть на ее основе.
@delnan Проблема просто в том, что из-за таких сложностей он будет не очень полезен? или есть какая-то причина, по которой он действительно может сломать диктовку?
wim
1
@wim: Последний. Как указано в моем ответе, это на самом деле не нарушает требований к ключам dict, но, вероятно, создаст больше проблем, чем решит.
1
@delnan - вы хотели сказать «бывший»
Джейсон
9

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

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

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

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

bpgergo
источник
4

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

Timgeb
источник
>>> x = (1,2,3321321321321,) >>> id (x) 139936535758888 >>> z = (1,2,3321321321321,) >>> id (z) 139936535760544 >>> id ((1, 2,3321321321321,)) 139936535810768 Эти 3 имеют одинаковые значения кортежа, но разные идентификаторы. Значит, словарь с ключом x не будет иметь значения для ключа z?
Ашвани
@ Ашвани ты пробовал?
timgeb
Да, он работает, как ожидалось. Я сомневаюсь, что все кортежи с одинаковыми значениями имеют разные идентификаторы. Так на каком основании рассчитывается этот хеш?
Ашвани
@Ashwani Хеш xи zто же самое. Если что-то неясно, задайте новый вопрос.
timgeb
1
@ Ашвани hash(x)и hash(z).
timgeb
3

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

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

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

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

AKjsd89
источник
1

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

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

Бен Райт
источник
-1

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

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

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

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

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

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

Никола Мусатти
источник
1
Это не ответ на вопрос, не так ли? hash = idне нарушает инвариант в конце первого абзаца, вопрос в том, почему так не делается.
@delnan: Я добавил последний абзац, чтобы уточнить.
Никола Мусатти
-1

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

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

{key : val}  
hash(key) = val

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

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

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

hash(<your key here>)

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


Коротко :

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

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

Вирадж Дханушка
источник