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

파이썬 사전이 해시 테이블의 예입니까?

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

해결법

1. ==============================

   1.예, 해시 매핑 또는 해시 테이블입니다. Tim Peters가 쓴 Python의 dict 구현에 대한 설명을 읽을 수 있습니다.

   예, 해시 매핑 또는 해시 테이블입니다. 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
   

   해시 테이블에 대한 자세한 내용을 보거나 파이썬에서 구현 된 방법과 그 방법이 구현 된 이유를 확인할 수 있습니다.

2. ==============================

   2.hash ()에 대한 테이블 검색보다는 파이썬 사전에 더 많은 것이 있어야합니다. 짐승 같은 실험으로이 해시 충돌을 발견했습니다.

   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)에서의 충돌과 같은 이야기입니다.)

3. ==============================

   3.예. 내부적으로 그것은 Z / 2 (소스)에 대한 원시 다항식을 기반으로하는 열린 해싱으로 구현됩니다.

   예. 내부적으로 그것은 Z / 2 (소스)에 대한 원시 다항식을 기반으로하는 열린 해싱으로 구현됩니다.

4. ==============================

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

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

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

from https://stackoverflow.com/questions/114830/is-a-python-dictionary-an-example-of-a-hash-table by cc-by-sa and MIT license