Python Dictionary 내부 구조 (+HashTable)

hwstar·2024년 7월 6일

Python

목록 보기

1/2

Python 프로그래밍에서 가장 자주 사용되는 자료 구조 중 하나는 바로 딕셔너리이다.
딕셔너리는 키-값 쌍을 저장하고, 키를 이용해 빠르게 값을 검색할 수 있다.

이러한 딕셔너리의 효율성은 해시 테이블이라는 강력한 자료 구조 덕분이다.

해시 테이블은 데이터의 저장과 검색을 빠르게 처리하기 위해 사용되는 자료 구조이다.
해시 테이블은 키를 해시 함수에 입력하여 고유한 해시 값을 생성하고, 이 해시 값을 이용해 데이터를 배열의 특정 위치에 저장한다.

Python 딕셔너리는 내부적으로 배열과 연결된 여러 개의 버킷(bucket)으로 구성된다.
각 버킷은 특정 해시 값을 가지며, 이 해시 값은 키를 해시 함수에 적용한 결과이다.

초기 크기는 8개의 버킷으로 초기화 된다.

해시 테이블에서는 서로 다른 두 키가 같은 해시 값을 가질 때 충돌이 발생하는데

Python 딕셔너리는 충돌을 해결하기 위해 개방 주소법(open addressing)을 사용한다.
개방 주소법은 충돌이 발생한 경우 해시 테이블 내에서 다른 빈 버킷을 찾아 저장하는 방법이다.

해시 테이블 내에서 다른 빈 버킷을 찾는 과정을 ‘프로빙(probing)’이라고 한다.
Python에서는 빈 버킷을 찾기 위해서 ‘Perturbation Shift Probing’ 이라는 고유 알고리즘을 사용한다.

간단하게 말하면 mod 연산 + 비트 연산으로 다이나믹하게 이동하면서 다음 빈 버킷의 위치를 찾는다.

(체이닝(chaining) 충돌 처리 기법을 사용하지 않은 이유는 링크드 리스트를 만들때 큰 오버헤드가 요구되기 때문이라고 적혀있긴하다.. 파이썬은 모든게 객체로 이루어져 있어서 그럴만도 하다. 여담으로 JAVA는 체이닝 기법을 사용한다.)

삽입: 키-값 쌍을 삽입할 때 해시 값을 계산하여 인덱스를 찾고, 해당 인덱스의 버킷이 비어 있으면 키-값 쌍을 저장한다. 비어 있지 않으면 프로빙 하여 빈 버킷에 저장한다.
검색: 키로 값을 검색할 때 해시 값을 계산하여 인덱스를 찾고, 해당 인덱스의 버킷에 키가 같으면 값을 반환합니다. 키가 다르면 다음 버킷을 확인한다.

개방 주소법을 충돌 처리 방법으로 하면서 해시 테이블의 크기를 유연하게 늘리지 못하는 단점이 있었다.
이때 해시 테이블에 일정 수준 이상으로 차게되면 성능이 급격이 저하되는 문제가 발생한다.

Python에서는 이러한 문제를 해결하기 위해 버킷의 2/3을 초과하여 채워지면, 새로운 더 큰 배열을 할당하고 기존 데이터를 새 배열로 재배치한다.

이렇게 재해싱과정을 거치게 되면 버킷이 많아져서 해시 충돌의 가능성이 줄어들게 된다.
충돌이 적어지면 해시 테이블의 속도가 개선될 수 있는것이다.

공식 문서에 나와있는 표이다.
최악의 시간 복잡도는 해시 함수가 key를 고르게 분배하지 못했을 경우이다.

Python 딕셔너리는 해시 테이블을 사용하여 키-값 쌍을 효율적으로 관리하는 데이터 구조이다.
데이터의 빠른 검색과 삽입을 가능하게 하기 위해 Python에서는 어떤 방식을 채택하여 내부적으로 처리하는지 알 수 있었다.

참고 자료