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

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

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

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

Ответ 4

Здесь ответ http://wiki.python.org/moin/DictionaryKeys

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

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

Как использовать литерал списка в поиске словаря?

Ответ 5

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

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

Ответ 6

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

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

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

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

Ответ 7

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

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

Ответ 8

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

Ответ 9

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

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

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

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

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

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