Dict in Python

파이썬에서 기본으로 제공해 주는 내부 자료구조인 dict가 어떻게 구현되었는지 간단하게 알아보자

 

* 구체적인 구현은 파이썬 인터프리터, 버전마다 달라질 수 있다. 

해시테이블 동작방식

파이썬에서 dict는 해시테이블로 이루어져있다.

* 해시테이블에 대해서 잘 모른다면 여기를 참고하는 걸 추천한다.

 

기본적으로 해시테이블을 구현하고 동작하는 데 필요한 3가지 요소가 있다.

hash function

어떤 함수를 이용해서 key 값을 slot 에 분배할 것인가?

 

collision resolution method(충돌 해결 방식)

서로 다른 두 key가 같은 hash(key) 값을 가질 때 발생하는 collision을 어떻게 해결할 것인가?

 

 

크게 open addressing 방식과 chaining 방식으로 나눌 수 있다.

 - open addressing

비어있는 다른 slot을 탐색하는 방식

linear probing(한 칸씩 이동하며 탐색), quadratic probing(제곱 간격으로 이동하며 탐색) 등이 있다.

 

 - chaining

slot에 해당하는 연결리스트에 추가하는 방식

 

resize 기준

해시테이블이 어느 기준 이상으로 채워질 때 확장될 것인가?

 

Dict in Python

그렇다면 파이썬에서 hash function, collision resolution method, resize는 어떻게 이뤄질까?

 

resize 규칙 

파이썬에서는 초기 해시테이블의 크기는 8로 지정한다. 이후, 전체의 2/3개 이상의 슬롯이 채워지면 해시테이블을 2배로 resize한다. 이 규칙을 amortized time analysis라고 하는데, 이 규칙대로라면 해시테이블에는 항상 전체의 1/3 이상이 비워져 있게 된다. 이에 따라 set(insertion), remove, search 주요 연산이 평균 O(1) 시간 내 수행가능하다.

 

hash function

파이썬에서 hash function 값은 hash(key)%size으로 구한다.

 

collision resolution method

파이썬에서는 새로운 open addressing 방식을 사용하는데, 이를 pseudo code로 나타내면 다음과 같다.

perturb = hash(key) # slot의 cluster을 방지하기 위해 사용하는 변수
i = hash(key) % size
while H[i] is not empty :
	if H[i].key == key :
    		# found
    # i = (i + 1) % size # linear probing method
    i = (5 * i + 1 + perturb) % size #slot의 갯수가 2^k라면 모든 slot을 방문할 수 있음
    perturb = perturb >> 5 # perturb을 2^5으로 나누기
# empty slot is found

---

본 포스팅은 신찬수 교수님의 유튜브 강의를 요약하여 작성되었습니다. 

https://youtu.be/kZjbFWt1cFo