Почему я не могу использовать список в качестве ключа 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
Таким образом, кортеж является неизменяемым типом, но если я спрятал список внутри него, то это не может быть ключ... не мог ли я так же легко спрятать список внутри модуля?
У меня было какое-то смутное представление о том, что ключ должен быть "хэшируемым", но я просто собираюсь признать свое собственное незнание технических деталей; Я не знаю, что на самом деле здесь происходит. Что бы пошло не так, если бы вы попытались использовать списки в качестве ключей с хешем, скажем, как место их памяти?
9 ответов
В викитоне Python есть хорошая статья на эту тему: почему списки не могут быть словарями. Как объяснено там:
Что бы пошло не так, если бы вы попытались использовать списки в качестве ключей с хешем, скажем, как место их памяти?
Это можно сделать, не нарушая никаких требований, но это приводит к неожиданному поведению. Списки обычно обрабатываются так, как если бы их значение было получено из значений их содержимого, например, при проверке (не) равенства. Многие, понятно, ожидают, что вы можете использовать любой список [1, 2] чтобы получить тот же ключ, где вы должны держать точно такой же объект списка. Но поиск по значению прерывается, как только список, используемый в качестве ключа, изменяется, а для поиска по идентификатору требуется, чтобы вы держали в точности один и тот же список - что не требуется для любой другой обычной операции со списком (по крайней мере, я не могу придумать)).
Другие объекты, такие как модули и object в любом случае, сделайте намного больше из их идентичности объекта (когда в последний раз у вас было два отдельных объекта модуля, называемых sys?), и все равно сравниваются. Поэтому менее удивительно - или даже ожидаемо - что они, когда используются в качестве ключей, в этом случае также сравниваются по идентичности.
Почему я не могу использовать список в качестве ключа dict в python?
>>> d = {repr([1,2,3]): 'value'}
{'[1, 2, 3]': 'value'}
(для любого, кто сталкивается с этим вопросом, ищет способ обойти это)
как объяснили здесь другие, на самом деле вы не можете. Однако вы можете вместо этого использовать его строковое представление, если вы действительно хотите использовать свой список.
Только что вы можете изменить список в кортеж, а затем использовать его в качестве ключей.
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 members) должны быть хешируемыми, а хеширование изменяемых объектов - плохая идея, поскольку хеш-значения должны вычисляться на основе атрибутов экземпляра.
В этом ответе я приведу несколько конкретных примеров, надеюсь, добавляя ценность поверх существующих ответов. Каждое понимание относится к элементам 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, это не может быть найдено в диктовке больше, потому что хэш изменился. Только линейное сканирование по списку ключей диктата находит 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 в ключах дикта (в худшем случае). На данный момент цель словаря - поиск 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 ключи, потому что кортежи неизменны и хэшируемы.
Простой ответ на ваш вопрос заключается в том, что в списке классов не реализован хэш метода, который требуется для любого объекта, который хочет использовать в качестве ключа в словаре. Однако причина, по которой хеш не реализован так же, как, скажем, в классе кортежей (основанном на содержимом контейнера), заключается в том, что список является изменяемым, поэтому редактирование списка потребует пересчета хеша, что может означать, что список в теперь находится не в том ведре в подчиненной хэш-таблице. Обратите внимание, что, поскольку вы не можете изменить кортеж (неизменяемый), он не сталкивается с этой проблемой.
В качестве примечания, фактическая реализация поиска диктобъектов основана на алгоритме D от Knuth Vol. 3, гл. 6.4. Если вам доступна эта книга, ее стоит прочитать, кроме того, если вы действительно, действительно заинтересованы, вы можете взглянуть на комментарии разработчиков по фактической реализации dictobject здесь. В нем подробно рассказывается, как именно это работает. Существует также лекция по питону о реализации словарей, которые могут вас заинтересовать. Они проходят определение ключа и что такое хеш в первые несколько минут.
Ваш awnser можно найти здесь:
Почему списки не могут быть словарями
Новички в Python часто задаются вопросом, почему, хотя язык включает в себя как кортеж, так и тип списка, кортежи можно использовать в качестве ключей словаря, а списки - нет. Это было преднамеренное дизайнерское решение, и лучше всего объяснить его первым пониманием работы словарей Python.
Источник и дополнительная информация: http://wiki.python.org/moin/DictionaryKeys
Словарь - это HashMap, в котором хранится карта ваших ключей, значение, преобразованное в новый хешированный ключ, и сопоставление значений.
что-то вроде (псевдокод):
{key : val}
hash(key) = val
Если вам интересно, какие из доступных опций можно использовать в качестве ключа для вашего словаря. потом
все, что является хешируемым (может быть преобразовано в хэш и содержать статическое значение, т.е. неизменяемое, чтобы создать хешированный ключ, как указано выше), имеет право, но поскольку список или набор объектов могут изменяться на ходу, поэтому хэш (ключ) также должен варьироваться, чтобы синхронизироваться с вашим списком или набором.
Ты можешь попробовать:
hash(<your key here>)
Если он работает нормально, его можно использовать в качестве ключа для вашего словаря или преобразовать во что-то хешируемое.
Коротко:
- Преобразуйте этот список в
tuple(<your list>). - Преобразуйте этот список в
str(<your list>).
Согласно документации Python 2.7.2:
Объект является хешируемым, если у него есть хеш-значение, которое никогда не изменяется в течение времени его существования (ему нужен метод hash()), и его можно сравнить с другими объектами (ему нужен метод eq() или cmp()). Хэшируемые объекты, которые сравниваются равными, должны иметь одинаковое хеш-значение.
Hashability делает объект пригодным для использования в качестве ключа словаря и члена набора, потому что эти структуры данных используют значение хеша внутри.
Все неизменяемые встроенные объекты Python являются хэшируемыми, в то время как нет изменяемых контейнеров (таких как списки или словари). Объекты, которые являются экземплярами пользовательских классов, по умолчанию являются хэшируемыми; все они сравниваются неравно, и их хеш-значение является их id().
Кортеж является неизменным в том смысле, что вы не можете добавлять, удалять или заменять его элементы, но сами элементы могут быть изменяемыми. Значение хеш-функции списка зависит от хеш-значений его элементов, поэтому оно изменяется при изменении элементов.
Использование идентификаторов для хэшей списков будет означать, что все списки сравниваются по-разному, что было бы удивительно и неудобно.
dictключи должны быть хешируемыми. Списки изменяемы и не предоставляют допустимого метода хеширования.