3.9 dict와 set의 내부 구조

Remarks

이 글은 전문가를 위한 파이썬(Fluent Python)을 정리한 자료입니다.

3.9 dict와 set의 내부 구조

파이썬이 해시 테이블을 이용해서 딕셔너리와 집합을 구현하는 방식을 알면, 그들의 장단점을 이해하는 데 도움이 된다.

3.9.1 성능 실험

found = 0
for n in needles:
  if n in haystack:
    found += 1

haystack의 크기가 10,000배 들어나더라도 dict를 사용하여 구현한 경우, 2배도 안 되는 시간이 소요된다. 그러나 list로 구현한 경우, 소요시간이 선형에 가깝게 증가한다.(9,278.9배)

3.9.2 딕셔너리 안의 해시 테이블

해시 테이블
1. 해시 테이블은 희소 배열(sparse array)로서 각 항목을 bucket이라고 부른다.
2. 각 bucket에는 키에 대한 참조와 항목의 값에 대한 참조가 들어간다.
3. 모든 bucket의 크기는 동일하므로 offset을 계산해서 각 bucket에 바로 접근할 수 있다.
4. 해시 테이블 안에 항목을 넣을 때, 먼저 항목 키의 해시값(hash())을 계산한다.
해시
1. 두 객체가 동일하면 이 값들의 해시값도 동일해야 한다.
  즉, $\forall a,b (a = b) → (hash(a) = hash(b))$

3.9.2.1 해시 테이블 알고리즘

Goal: my_dict[search_key]의 값을 가져오기

1
2
3
4
5
6
7
8
9
10
__hash__(search_key)를 호출하여 search_key의 해시값 가져오기
해시값의 최하위 비트를 해시 테이블 안의 bucket에 대한 offset으로 사용 (사용하는 비트 수는 현재 테이블 크기에 따라 달라짐)
while bucket이 비어 있지 않음
  bucket에 들어 있는 항목쌍(found_key: found_value) 가져오기
  if search_key != found_key,
    해시의 다른 부분을 이용하여 해시 테이블의 다른 위치를 찾는다
    continue
  else,
    return found_value
KeyError 발생

항목을 추가: 빈 bucket을 찾으면 새로운 항목을 추가
항목을 갱신: 동일한 키의 bucket을 찾으면 값을 갱신

항목을 추가할 시, 해시 테이블에 항목이 너무 많다고 판단되면 더 큰 공간을 가진 새로운 위치에 해시 테이블을 다시 만든다.
해시 테이블이 커지면 더 많은 해시 비트를 offset으로 사용하며, 더 많은 비트를 사용할수록 충돌률은 낮아진다.
dict안에 수백만 개의 항목이 있어도 한 번 검색할 때마다 발생하는 평균 충돌 횟수는 1에서 2 사이다.

3.9.3 dict 작동 방식에 의한 영향

키 객체는 반드시 해시 가능해야 한다
다음 요구사항을 만족하는 객체는 해시 가능하다. 1) 객체의 수명 주기 동안 언제나 동일한 값을 반환하는 __hash__()를 제공
2) __eq__()를 통해 동치성을 판단할 수 있다
3) a == b가 참이면, hash(a) == hash(b)도 반드시 참이어야 한다.
dict의 메모리 오버헤드가 크다
- 많은 양의 레코드를 처리하는 경우에는, dict를 사용하는 경우보다, tuple이나 namedtuple의 list에 저장하는 것이 좋다.
- 사용자 정의 자료형의 경우, __slots__을 사용하여 객체 속성 저장소를 dict에서 tuple로 변경할 수 있다.
- 최적화는 유지보수성이 희생되는 제단이다.
키 검색이 아주 빠르다
dict는 속도를 위해 공간을 포기하여, 1천만 개의 항목을 가진 dict에서 키 2백만 개를 검색하는 데 채 1초도 걸리지 않는다.
키 순서는 삽입 순서에 따라 달라진다
딕셔너리에 항목을 추가하면 기존 키의 순서가 변경될 수 있다
항목을 추가할 때마다 파이썬 인터프리터는 해시 테이블 크기를 늘릴지 판단하기 때문에, 딕셔너리를 반복하는 동안 딕셔너리의 내용을 변경하는 것은 좋지 않은 방법이다.

PREVIOUSEtc