[python] 파이썬의 내장 사전은 어떻게 구현됩니까?

파이썬의 내장 사전은 어떻게 구현됩니까?

짧은 과정은 다음과 같습니다.

• 그것들은 해시 테이블입니다. (파이썬 구현의 세부 사항은 아래를 참조하십시오.)
• Python 3.6부터 새로운 레이아웃 및 알고리즘으로 만듭니다.
  • 키 삽입 순서
  • 적은 공간을 차지하고
  • 사실상 비용이 들지 않습니다.
• 다른 최적화는 공유 키를 지시 할 때 공간을 절약합니다 (특별한 경우).

정렬 된 측면은 Python 3.6 (비공식적 인 기회를 제공하기 위해) 비공식적이지만 Python 3.7 에서는 공식적입니다 .

파이썬의 사전은 해시 테이블입니다

오랫동안 이처럼 정확하게 작동했습니다. 파이썬은 8 개의 빈 행을 미리 할당하고 해시를 사용하여 키-값 쌍을 고정 할 위치를 결정합니다. 예를 들어, 키의 해시가 001로 종료되면 1 (예 : 2 번째) 인덱스에 고정됩니다 (아래 예와 같이).

   <hash>       <key>    <value>
     null        null    null
...010001    ffeb678c    633241c4 # addresses of the keys and values
     null        null    null
      ...         ...    ...

각 행은 64 비트 아키텍처에서 24 바이트, 32 비트에서 12 바이트를 차지합니다. (열 머리글은 여기서 우리의 목적을위한 레이블 일 뿐이며 실제로 메모리에는 존재하지 않습니다.)

해시가 기존 키의 해시와 동일하게 종료 된 경우 이는 충돌이며 키-값 쌍을 다른 위치에 고정시킵니다.

5 개의 키-값이 저장된 후 다른 키-값 쌍을 추가 할 때 해시 충돌 가능성이 너무 커서 사전 크기가 두 배가됩니다. 64 비트 프로세스에서 크기 조정 전에는 72 바이트가 비어 있고 10 개의 빈 행으로 인해 240 바이트가 낭비됩니다.

이 작업에는 많은 공간이 필요하지만 조회 시간은 상당히 일정합니다. 키 비교 알고리즘은 해시를 계산하고 예상 위치로 이동하여 키의 ID를 비교하는 것입니다. 키가 동일한 객체 인 경우 동일합니다. 만약 그들이 다음, 해시 값을 비교하지 않으면 되지 같은, 그들은 동일한 아니에요. 그렇지 않으면 마지막으로 키가 같은지 비교하고, 같으면 값을 반환합니다. 평등에 대한 최종 비교는 상당히 느릴 수 있지만, 초기 검사는 일반적으로 최종 비교를 단축하여 조회를 매우 빠르게 만듭니다.

충돌로 인해 속도가 느려지고 공격자는 이론적으로 해시 충돌을 사용하여 서비스 거부 공격을 수행 할 수 있으므로 해시 함수의 초기화를 무작위 화하여 새로운 각 Python 프로세스에 대해 서로 다른 해시를 계산합니다.

위에서 설명한 낭비되는 공간으로 인해 사전을 삽입하여 정렬하는 흥미로운 새 기능을 사용하여 사전 구현을 수정했습니다.

새로운 소형 해시 테이블

대신 삽입 인덱스에 대한 배열을 미리 할당하여 시작합니다.

첫 번째 키-값 쌍이 두 번째 슬롯에 들어가므로 다음과 같이 색인을 생성합니다.

[null, 0, null, null, null, null, null, null]

그리고 우리 테이블은 삽입 순서로 채워집니다.

   <hash>       <key>    <value>
...010001    ffeb678c    633241c4
      ...         ...    ...

따라서 키를 찾을 때 해시를 사용하여 예상 위치를 확인한 다음 (이 경우 배열의 인덱스 1로 바로 이동) 해시 테이블에서 해당 인덱스로 이동합니다 (예 : 인덱스 0 )에서 키가 동일한 지 확인하고 (앞에서 설명한 것과 동일한 알고리즘을 사용하여) 해당하는 경우 값을 반환합니다.

우리는 일정한 검색 시간을 유지하고 경우에 따라 약간의 속도 손실과 다른 경우에는 이익을 얻습니다. 기존 구현에 비해 많은 공간을 절약하고 삽입 순서를 유지한다는 단점이 있습니다. 낭비되는 유일한 공간은 인덱스 배열의 널 바이트입니다.

Raymond Hettinger 는 2012 년 12 월 에 python-dev 에서 이것을 소개했습니다 . 마침내 Python 3.6 에서 CPython에 들어갔습니다 . 삽입 순서는 3.6의 구현 세부 사항으로 간주되어 다른 Python 구현에서 따라 잡을 수 있습니다.

공유 키

공간을 절약하기위한 또 다른 최적화는 키를 공유하는 구현입니다. 따라서 모든 공간을 차지하는 중복 사전을 사용하는 대신 공유 키 및 키 해시를 재사용하는 사전이 있습니다. 다음과 같이 생각할 수 있습니다.

     hash         key    dict_0    dict_1    dict_2...
...010001    ffeb678c    633241c4  fffad420  ...
      ...         ...    ...       ...       ...

64 비트 시스템의 경우 추가 사전 당 키당 최대 16 바이트를 절약 할 수 있습니다.

커스텀 객체 및 대안을위한 공유 키

이 공유 키 사전은 사용자 정의 객체에 사용하기위한 것 __dict__입니다. 이 동작을 수행하려면 __dict__다음 객체를 인스턴스화하기 전에 채우기 를 완료해야한다고 생각 합니다 ( PEP 412 참조 ). 이 방법은 당신은 귀하의 모든 속성을 지정해야합니다 __init__또는 __new__다른 당신은 당신의 공간을 절약 할 수하지 않을 수 있습니다.

그러나 __init__실행 시점에 모든 속성을 알고 있다면 __slots__객체를 제공 하고 __dict__전혀 생성되지 않았거나 (부모가 사용할 수없는 경우) __dict__보장하거나 예상 속성이 허용되도록 보장 할 수도 있습니다. 어쨌든 슬롯에 저장됩니다. 에 대한 자세한 내용은 __slots__, 여기 내 대답을 참조하십시오 .

또한보십시오:

• PEP 509 -dict에 개인 버전 추가
• PEP 468-**kwargs 함수 의 순서를 유지합니다 .
• PEP 520-클래스 속성 정의 순서 유지
• PyCon 2010 : The Might Dictionary -Brandon Rhodes
• PyCon 2017 : Dictionary Even Mightier -Brandon Rhodes
• PyCon 2017 : 현대 파이썬 사전 12 가지 훌륭한 아이디어의 합류 -Raymond Hettinger
• dictobject.c -C에서 CPython의 실제 dict 구현

---

답변