파이썬에서 목록을 dict 키로 사용할 수없는 이유는 무엇입니까?

파이썬에서 목록을 dict 키로 사용할 수없는 이유는 무엇입니까?

---

파이썬 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 위키의 주제에 대한 좋은 기사가 있습니다. Why Lists Ca n't Be Dictionary Keys . 거기에 설명 된대로 :

해시를 메모리 위치로 사용하여 목록을 키로 사용하려고하면 어떻게 될까요?

실제로 요구 사항을 위반하지 않고 수행 할 수 있지만 예기치 않은 동작이 발생합니다. 목록은 일반적으로 (in-) equality를 확인할 때와 같이 해당 값이 콘텐츠의 값에서 파생 된 것처럼 처리됩니다. 많은 사람들은-당연히-당신이 [1, 2]정확히 같은 목록 객체를 유지해야하는 동일한 키를 얻기 위해 어떤 목록 을 사용할 수 있다고 기대 합니다. 그러나 키로 사용 된 목록이 수정 되 자마자 값별 조회가 중단되고, ID로 조회하려면 정확히 동일한 목록을 유지해야합니다. 다른 일반적인 목록 작업에는 필요하지 않습니다 (적어도 생각할 수있는 항목은 없습니다). ).

모듈과 같은 다른 객체 object는 어쨌든 객체 ID에서 훨씬 더 큰 거래를하고 (마지막으로 sys? 라고 불리는 두 개의 별개의 모듈 객체가 있었을 때 ) 어쨌든 비교됩니다. 따라서 딕셔너리 키로 사용될 때 그 경우에도 ID로 비교된다는 것은 놀랍지 않거나 예상치 못한 일입니다.

---

파이썬에서 목록을 dict 키로 사용할 수없는 이유는 무엇입니까?

>>> d = {repr([1,2,3]): 'value'}
{'[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

해시를 메모리 위치로 사용하여 목록을 키로 사용하려고하면 어떻게 될까요?

동일한 내용의 다른 목록을 검색하면 동일한 내용의 목록을 비교하면 동일한 것으로 표시 되더라도 다른 결과가 생성됩니다.

사전 조회에서 목록 리터럴을 사용하는 것은 어떻습니까?

---

List를 튜플로 변경 한 다음 키로 사용할 수 있습니다.

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

---

awnser는 여기에서 찾을 수 있습니다.

목록이 사전 키가 될 수없는 이유

Python을 처음 접하는 사람들은 언어에 튜플과 목록 유형이 모두 포함되어 있지만 튜플은 사전 키로 사용할 수있는 반면 목록은 사용할 수없는 이유가 궁금합니다. 이것은 의도적 인 디자인 결정이었고, 파이썬 사전이 어떻게 작동하는지 먼저 이해함으로써 가장 잘 설명 될 수 있습니다.

출처 및 추가 정보 : http://wiki.python.org/moin/DictionaryKeys

---

귀하의 질문에 대한 간단한 대답은 클래스 목록이 사전에서 키로 사용하려는 객체에 필요한 메서드 해시 를 구현하지 않는다는 것 입니다. 그러나 해시 가 동일한 방식으로 구현되지 않는 이유 는 (컨테이너의 내용을 기반으로 한) 튜플 클래스가 목록이 변경 가능하기 때문에 목록을 편집하려면 해시를 다시 계산해야합니다. 이제 기본 해시 테이블 내의 잘못된 버킷에 있습니다. 튜플 (불변)을 수정할 수 없기 때문에이 문제가 발생하지 않습니다.

참고로, dictobjects 조회의 실제 구현은 Knuth Vol.의 알고리즘 D를 기반으로합니다. 3, Sec. 6.4. 그 책을 사용할 수 있다면 읽어 볼 가치가있을 것입니다. 또한 정말로 관심이 있다면 여기에서 dictobject 의 실제 구현 에 대한 개발자 의견을 살펴볼 수 있습니다. 정확히 어떻게 작동하는지 자세히 설명합니다. 여러분이 관심을 가질만한 사전 구현에 대한 파이썬 강의 도 있습니다. 그들은 키의 정의와 처음 몇 분 동안 해시가 무엇인지 살펴 봅니다.

---

목록은 변경 가능하기 때문에 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

mutating 후에 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

That's not a good idea as well because equal objects should hash identically such that you can find them in a dict or set.

Example 3: ... ok, what about constant hashes across all instances?!

>>> 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

Things seem to work as expected, but think about what's happening: when all instances of your class produce the same hash value, you will have a hash collision whenever there are more than two instances as keys in a dict or present in a set.

Finding the right instance with my_dict[key] or key in my_dict (or item in my_set) needs to perform as many equality checks as there are instances of stupidlist3 in the dict's keys (in the worst case). At this point, the purpose of the dictionary - O(1) lookup - is completely defeated. This is demonstrated in the following timings (done with IPython).

Some Timings for Example 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)

As you can see, the membership test in our stupidlists_set is even slower than a linear scan over the whole lists_list, while you have the expected super fast lookup time (factor 500) in a set without loads of hash collisions.

---

TL; DR: you can use tuple(yourlist) as dict keys, because tuples are immutable and hashable.

---

According to the Python 2.7.2 documentation:

An object is hashable if it has a hash value which never changes during its lifetime (it needs a hash() method), and can be compared to other objects (it needs an eq() or cmp() method). Hashable objects which compare equal must have the same hash value.

Hashability makes an object usable as a dictionary key and a set member, because these data structures use the hash value internally.

All of Python’s immutable built-in objects are hashable, while no mutable containers (such as lists or dictionaries) are. Objects which are instances of user-defined classes are hashable by default; they all compare unequal, and their hash value is their id().

A tuple is immutable in the sense that you cannot add, remove or replace its elements, but the elements themselves may be mutable. List's hash value depends on the hash values of its elements, and so it changes when you change the elements.

Using id's for list hashes would imply that all lists compare differently, which would be surprising and inconvenient.

참고URL : https://stackoverflow.com/questions/7257588/why-cant-i-use-a-list-as-a-dict-key-in-python