Python 사전은 해시 테이블의 예입니까?

Question

Python의 기본 데이터 구조 중 하나는 사전입니다. 이를 통해 모든 유형의 "값"을 찾기 위해 "키"를 기록할 수 있습니다.내부적으로 해시 테이블로 구현됩니까?그렇지 않다면 무엇입니까?

Answer 1

예, 해시 매핑 또는 해시 테이블입니다.Tim Peters가 작성한 Python의 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

당신은 할 수 있습니다 해시 테이블에 대해 자세히 읽어보세요. 또는 Python에서 어떻게 구현되었는지 확인하세요. 그리고 왜 그렇게 구현되었는지.

Answer 2

Python 사전에는 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()가 다른 해시를 사용할 수도 있습니다.

(그런데 이것은 Python 2.7.10의 경우입니다.Python 3.4.3 및 3.5.0에서 충돌이 발생하는 동일한 이야기 hash(1.1) == hash(214748749.8).)

Answer 3

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

Answer 4

nosklo의 설명을 확장하려면 다음을 수행하십시오.

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