[python] 파이썬 사전은 해시 테이블의 예입니까?

PYTHON / 글쓴이

파이썬의 기본 데이터 구조 중 하나는 사전이며, 어떤 유형의 “값”을 찾기 위해 “키”를 기록 할 수 있습니다. 내부적으로 해시 테이블로 구현 되었습니까? 그렇지 않다면 무엇입니까?

답변

예, 해시 매핑 또는 해시 테이블입니다. , 팀 피터스 (Tim Peters)에 의해 기록 된대로, 파이썬의 DICT 구현에 대한 설명을 읽을 수 있습니다 여기에 .

그렇기 때문에리스트처럼 ‘해시 불가능’을 dict 키로 사용할 수없는 이유는 다음과 같습니다.

>>> a = {}
>>> b = ['some', 'list']
>>> hash(b)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: list objects are unhashable
>>> a[b] = 'some'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: list objects are unhashable

당신은 할 수 해시 테이블에 대한 자세한 내용 이나 이 파이썬으로 구현되었는지를 확인 하고 이 방법이 있음을 구현하는 이유 .

답변

hash ()의 테이블 조회보다 파이썬 사전에 더 많은 것이 있어야합니다. 무차별 실험 으로이 해시 충돌을 발견했습니다 .

>>> hash(1.1)
2040142438
>>> hash(4504.1)
2040142438

그러나 그것은 사전을 깨뜨리지 않습니다.

>>> d = { 1.1: 'a', 4504.1: 'b' }
>>> d[1.1]
'a'
>>> d[4504.1]
'b'

위생 점검:

>>> for k,v in d.items(): print(hash(k))
2040142438
2040142438

아마도 사전 키 사이의 충돌을 피하는 hash () 이외의 다른 조회 수준이있을 수 있습니다. 또는 dict ()는 다른 해시를 사용합니다.

(이것은 파이썬 2.7.10에서입니다. 파이썬 3.4.3과 3.5.0에서 같은 이야기가 충돌 hash(1.1) == hash(214748749.8)합니다.)

답변

예. 내부적으로 Z / 2 ( source )를 통한 원시 다항식을 기반으로하는 개방 해싱으로 구현됩니다 .

답변

nosklo의 설명을 확장하려면 :

a = {}
b = ['some', 'list']
a[b] = 'some' # this won't work
a[tuple(b)] = 'some' # this will, same as a['some', 'list']

답변