파이썬 내장 딕셔너리는 어떻게 구현되었나요?

파이썬 내장 사전 유형이 어떻게 구현되었는지 아는 사람이 있나요? 내 이해로는 해시 테이블과 같은 것이지만, 확실한 답변을 찾지 못했습니다.

답변 1

여기는 제가 Python 딕셔너리에 대해 모은 것이 모두 포함된 내용입니다(아마 누구도 원하지 않을 정도로 많은 정보가 있을 것입니다. 그러나 답변은 포괄적입니다).

파이썬 딕셔너리는 해시 테이블로 구현됩니다.

해시 테이블은 해시 충돌을 허용하여야 합니다. 즉, 두 개 이상의 다른 키가 동일한 해시 값을 갖더라도, 해당 테이블의 구현은 키와 값 쌍을 명확하게 삽입하고 검색할 수 있는 전략을 가져야 합니다.

파이썬 dict은 해시 충돌을 해결하기 위해 열린 주소 방식을 사용합니다 (아래 설명) (참조 dictobject.c:296-297).

파이썬 해시 테이블은 인덱스를 통해 빠른 조회가 가능한 연속적인 메모리 블록(배열과 비슷한 구조)입니다.

테이블의 각 슬롯은 하나의 항목만 저장할 수 있습니다. 이것은 중요합니다.

테이블의 각 항목은 사실상 세 가지 값의 조합입니다: <해시, 키, 값>. 이는 C 구조체로 구현됩니다 (참조: dictobject.h:51-56).

아래 그림은 파이썬 해시 테이블의 논리적인 표현입니다. 그림에서 왼쪽의 0, 1, ..., i, ...는 해시 테이블의 슬롯 인덱스로서 그림 설명용이며, 당연히 테이블과 함께 저장되지 않습니다.

# Logical model of Python Hash table

-+-----------------+

0| |

-+-----------------+

1| ... |

-+-----------------+

.| ... |

-+-----------------+

i| ... |

-+-----------------+

.| ... |

-+-----------------+

n| ... |

-+-----------------+

새로운 딕셔너리가 초기화될 때 8개의 슬롯으로 시작합니다. (dictobject.h:49 라벨 참조)

테이블에 항목을 추가할 때, 우리는 키의 해시를 기반으로하는 # $ @ & @@ * ^ $ &와 같은 몇 가지 슬롯에서 시작합니다. CPython은 초반에 # $ * $ &&#! $ & (여기서 # $$ # & @ # ^ $ &지만, 그것은 정말 중요하지 않습니다)를 사용합니다. 단지 초기 슬롯 # $ @ & @@ * ^ $ &가 키의 해시에 따라 확인된다는 것을 기억하세요.

만약 그 슬롯이 비어있다면, 항목은 슬롯에 추가됩니다 (항목이란 # $$ !! ^ @ ^ $ &를 의미합니다). 하지만 그 슬롯이 이미 차 있는 경우는 어떻게 될까요?! 아마도 해시 충돌이 발생했기 때문입니다!

만약 슬롯이 이미 차있다면, CPython (그리고 심지어 PyPy도)는 현재 삽입하려는 항목의 해시 값과 키의 해시값 및 키 값과 (비교한다는 말은 (== 비교가 아닌 is 비교가 아닙니다) 슬롯의 항목의 해시 값과 키 값을 각각 비교합니다. 둘 다 일치하는 경우, 이미 존재하는 항목으로 간주하고 다음에 삽입할 항목으로 이동합니다. 해시 값이나 키 중 하나라도 일치하지 않으면 프로빙을 시작합니다.

탐사(probing)란 빈 슬롯을 찾기 위해 슬롯을 하나씩 검색하는 것을 의미합니다. 기술적으로는 우리는 한 번에 한 개씩 가면서 첫 번째 사용 가능한 슬롯을 사용할 수 있습니다(즉, 선형 탐사). 하지만 아름답게 설명된 댓글(참조: dictobject.c:33-126)에서 설명한 이유 때문에 CPython에서는 무작위 탐사(random probing)를 사용합니다. 무작위 탐사에서는 다음 슬롯이 의사 무작위로 선택됩니다. 항목은 첫 번째 빈 슬롯에 추가됩니다. 이 토론에서 다음 슬롯을 선택하는 실제 알고리즘은 실제로 중요하지 않습니다(프로빙(probing)용 알고리즘은 dictobject.c:33-126를 참조하십시오). 중요한 것은 슬롯이 첫 번째 빈 슬롯이 발견될 때까지 탐사된다는 것입니다.

조회 작업도 마찬가지로 시작 슬롯 i에서 시작하며(i는 키의 해시에 따라 달라집니다). 해시와 키 모두 슬롯의 항목과 일치하지 않는 경우 조사를 시작하고 일치하는 슬롯을 찾을 때까지 조사합니다. 모든 슬롯을 사용하면 실패를 보고합니다.

그런데, dict은 2/3정도 차면 크기가 조정됩니다. 이렇게 함으로써 룩업 속도가 느려지는 것을 방지할 수 있습니다. (자세한 내용은 dictobject.h:64-65을 참조하십시오)

참고: 저는 사전(Dictionary)의 구현에 대해 파이썬 설명서를 찾아보았습니다. 이유는 사전(Dictionary)에서 여러 항목이 동일한 해시 값(hash values)을 가질 수 있는 점에 대해 궁금한 것이었습니다. 이 질문과 관련된 논문을 포스팅하려고 이 문구를 약간 수정하여 여기에 올립니다.

답변 2

파이썬의 내장 사전은 어떻게 구현되었을까? 파이썬은 내부적으로 해시 테이블을 사용하여 사전을 구현한다. 해시 테이블은 각 항목을 고유한 키로 식별하고 이를 사용하여 값을 검색하는 데 사용된다. 이것은 사전의 키-값 쌍을 빠르게 검색하는 데 유용하다.

해시 함수는 각 키에 대해 해시 코드를 생성하며 이 코드를 사용하여 각 항목이 해시 테이블의 적절한 위치에 저장된다. 이것은 빠른 검색을 위해 O(1) 접근 시간을 제공한다. 그러나 다른 해시 코드가 동일한 위치에 배치되면 충돌이 발생한다. 이 문제를 처리하기 위해 파이썬은 개별 체이닝과 같은 충돌 처리 방법을 사용한다. 여러 해시 코드가 동일한 위치에 저장되면, 바로 가기 목록을 사용하여 해당 위치에 연결된 모든 항목을 순회하고 올바른 키를 가진 항목을 찾을 때까지 검색한다.

또한 파이썬 사전은 키는 반드시 변경 불가능한 객체이며, 해시 가능해야 한다는 규칙을 따른다. 이는 각 키에 대한 일관된 해시 코드를 보장하며, 이전에 저장된 항목을 찾을 때 올바른 위치와 일치하는지 확인한다.

파이썬의 내장 사전은 간단하면서도 효율적인 방식으로 데이터를 저장하고 검색하는 데 사용된다. 따라서 파이썬에서 사전은 매우 강력한 도구이며 프로그래밍에서 대부분의 작업에서 유용하게 사용될 수 있다.