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

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

---

누구나 파이썬의 내장 사전 유형이 어떻게 구현되는지 알고 있습니까? 내 이해는 일종의 해시 테이블이지만 어떤 종류의 결정적인 대답도 찾을 수 없었습니다.

---

다음은 내가 만들 수 있었던 Python dicts에 대한 모든 것입니다 (아마도 다른 사람이 알고 싶어하는 것보다 많지만 대답은 포괄적입니다).

• 파이썬 사전은 해시 테이블 로 구현됩니다 .
• 해시 테이블은 해시 충돌을 허용해야합니다. 즉 두 개의 개별 키에 동일한 해시 값이 있더라도 테이블 구현에는 키와 값 쌍을 명확하게 삽입하고 검색하는 전략이 있어야합니다.
• 파이썬 dict은 개방 주소 지정 을 사용 하여 해시 충돌을 해결합니다 (아래 설명 참조) ( dictobject.c : 296-297 참조 ).
• 파이썬 해시 테이블은 연속적인 메모리 블록입니다 (배열과 같은 종류이므로 O(1)색인 으로 조회 할 수 있습니다 ).
• 테이블의 각 슬롯은 하나의 항목 만 저장할 수 있습니다. 이건 중요하다.
• 테이블의 각 항목 은 실제로 <hash, key, value> 의 세 값의 조합입니다 . 이것은 C 구조체로 구현됩니다 ( dictobject.h : 51-56 참조 ).

• 아래 그림은 Python 해시 테이블의 논리적 표현입니다. 아래 그림 0, 1, ..., i, ...에서 왼쪽은 해시 테이블 의 슬롯 인덱스입니다 (그들은 단지 설명을위한 것이며 테이블과 함께 저장되지 않습니다!).

  # Logical model of Python Hash table
  -+-----------------+
  0| <hash|key|value>|
  -+-----------------+
  1|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  i|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  n|      ...        |
  -+-----------------+
  

• 새로운 dict가 초기화되면 8 개의 슬롯으로 시작 합니다 . ( dictobject.h : 49 참조 )

• 테이블에 항목을 추가 할 때 i키의 해시를 기반으로하는 일부 슬롯으로 시작 합니다. CPython은 처음에 i = hash(key) & mask(where mask = PyDictMINSIZE - 1이지만 실제로 중요하지는 않습니다)를 사용합니다. 확인되는 초기 슬롯 () 은 키 i의 해시 에 따라 다릅니다 .
• 해당 슬롯이 비어 있으면 항목이 슬롯에 추가됩니다 (항목별로 <hash|key|value>). 그러나 그 슬롯이 점령되면 어떻습니까!? 다른 항목의 해시가 동일하기 때문에 (해시 충돌!)
• 슬롯이 점유되면 CPython (및 PyPy)은 삽입 할 현재 항목의 해시 및 키 ( dictobject.c) 와 슬롯의 항목 의 해시 및 키 ( ==비교가 아닌 is비교를 비교 하여 비교)를 비교합니다. : 337,344-345 ). 경우 모두 일치, 다음은 항목이 이미 생각하고 포기하고 다음 항목에 이동 삽입 할 수 있습니다. 해시 또는 키가 일치하지 않으면 검사를 시작합니다 .
• 프로빙은 빈 슬롯을 찾기 위해 슬롯별로 슬롯을 검색한다는 의미입니다. 기술적으로 우리는 하나씩 하나씩 가서 i+1, i+2, ...사용 가능한 첫 번째 것을 사용할 수 있습니다 (선형 프로빙). 그러나 주석에서 아름답게 설명 된 이유로 ( dictobject.c : 33-126 참조 ) CPython은 랜덤 프로빙을 사용합니다 . 랜덤 프로빙에서는 다음 슬롯이 의사 랜덤 순서로 선택됩니다. 항목이 첫 번째 빈 슬롯에 추가됩니다. 이 토론에서 다음 슬롯을 선택하는 데 사용되는 실제 알고리즘은 실제로 중요하지 않습니다 ( 탐색 알고리즘 은 dictobject.c : 33-126 참조 ). 중요한 것은 첫 번째 빈 슬롯이 발견 될 때까지 슬롯이 프로브되는 것입니다.
• 조회에서도 마찬가지입니다. 초기 슬롯 i로 시작합니다 (여기서 i는 키의 해시에 의존합니다). 해시와 키가 모두 슬롯의 항목과 일치하지 않으면 일치하는 슬롯을 찾을 때까지 프로빙을 시작합니다. 모든 슬롯이 소진되면 실패를보고합니다.
• BTW dict는 3 분의 2가 가득 찬 경우 크기가 조정됩니다. 이렇게하면 조회 속도가 느려지지 않습니다. ( dictobject.h : 64-65 참조 )

참고 : dict의 여러 항목이 동일한 해시 값을 가질 수있는 방법에 대한 내 자신의 질문 에 대한 응답으로 Python Dict 구현에 대한 연구를 수행했습니다 . 모든 연구가이 질문과도 관련이 있기 때문에 약간 편집 된 버전의 답변을 게시했습니다.

---

파이썬 사전은 개방 주소 지정을 사용합니다 ( 아름다운 코드 내부 참조 )

NB! 개방형 주소 지정 , 일명 폐쇄 형 해싱 은 Wikipedia에서 언급 한 바와 같이 반대되는 개방형 해싱 과 혼동해서는 안됩니다 !

개방형 주소 지정은 dict에서 배열 슬롯을 사용하고 dict에서 오브젝트의 기본 위치를 가져 오면 오브젝트의 해시 값이 일부 재생되는 "섭동"체계를 사용하여 동일한 배열의 다른 인덱스에서 오브젝트 스팟을 찾습니다. .

---

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

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

• 그것들은 해시 테이블입니다. (파이썬 구현의 세부 사항은 아래를 참조하십시오.)
• 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 구현

참고 URL : https://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented