딕셔너리를 직접 사용하지 않아도 파이썬 내부에서 매우 많이 사용되고 있다. 모듈 네임스페이스, 클래스나 인스턴스 속성, 함수의 키워드 인수에도 딕셔너리가 쓰이고 __builtins__.__dict__에는 내장함수명이 딕셔너리로 저장되어있다. 집합도 딕셔너리로 구현되어있다. 딕셔너리가 많이 쓰이는 만큼 파이썬은 해시 테이블 엔진을 통해 딕셔너리를 신경써서 최적화하였다.
중요 키워드
해시가능, 집합, 딕셔너리, frozenset, __hash__, __eq__, collections.abc.Mapping, collections.abc.MutableMapping
dict, defaultdict, OrderedDict, get, setdefault, update
default_factory, __missing__
ChainMap, Counter, UserDict
types.MappingProxyType
set, frozenset, Set, MutableSet
덜 중요한 키워드
unicodedata, dis모듈, BUILD_SET 바이트 코드
참고자료
http://bit.ly/1K4qjwE
http://bit.ly/1Vm7E4q
http://bit.ly/1Vm7I4c
http://bit.ly/1JHVi2E
http://bit.ly/1FEOPPB
어떤 객체가 딕셔너리인지 아닌지 확인할 때 type이 dict인지 확인하지 말고 isinstance를 통해 collections.abc.Mapping의 자손인지 확인하자. 다른 구현으로 만들어진 딕셔너리는 dict가 아닐 수 있기 때문이다.
딕셔너리의 키로 쓰거나 집합에 넣으려면 해시가능해야 한다. 해시가능이란 __hash__함수를 통해 변하지 않고 다르다고 생각되는 인스턴스끼리는 다른 고유의 값인 해시값을 생성할 수 있어야 하고, __eq__함수를 통해 비교할 수 있는 객체를 말한다. 사용자 정의 클래스는 기본적으로 id를 통해 해시값을 생성하기 때문에 해시가능하다. 내장 불변 시퀀스는 거의 모두 해시 가능이다. list는 해시 불가능, frozenset은 해시가능하다. 컨테이너의 경우 가지고있는 원소가 모두 해시가능이어야 자신도 해시가능이기 때문에 튜플은 모든 원소가 해시가능이면 그 튜플도 해시가능, 그렇지 않으면 해시 불가능이다.
딕셔너리는 {}, zip, kwargs, 튜플로 이뤄진 리스트로 생성할 수 있고 다른 딕셔너리로 생성할 수도 있다.
딕셔너리도 지능형 리스트처럼 지능형 딕셔너리로 생성할 수도 있다.
매핑에는 dict, defaultdict, OrderedDict가 있는데 공통으로 있는 메서드 중 update함수는 다른 매핑으로 자신의 항목을 업데이트 시킨다. 이 때 매핑이 아닌 키, 값이 짝지어진 시퀀스로도 가능하다. 대부분의 매핑을 받는 인자는 그 인자가 매핑이 아닐 경우 매핑을 만들 수 있는 시퀀스인지도 확인하여 만들 수 있다면 만들어서 적용하는 논리를 가진다.
__getitem__은 매핑에서 특정 키가 있으면 키에 대응되는 값을 가져온다. 만약 키가 없으면 오류가 발생한다. get함수를 통해 키가 없는 경우 디폴트 값이 반환되도록 설정할 수 있다. setdefault함수를 통해 키가 없는 경우 디폴트 값을 대입하고 반환되도록 설정할 수 있다. 매핑의 값으로 가변객체가 있는 경우 get을 사용하면 가변객체를 대입하는 비효율적인 코드가 될 수 있기 때문에 이 경우 setdefault를 사용한다.
매번 기본값을 처리할 때 setdefault를 사용하면 번거로우니 없는 키에 대해 특별히 처리해주는 매핑인 defaultdict가 있다. defaultdict는 생성자에서 콜러블 객체를 받아 default_factory에 저장해두는데, __getitem__이 호출되었을 때 키를 찾을 수 없을 경우 default_factory를 실행시켜 기본 값으로 설정한다. 오직 __getitem__이 실행되었을 때만 default_factory가 실행될 수 있는 것이어서 get함수나 setdefault함수는 default_factory를 실행하지 않는다.
사용자 정의 매핑으로 구현할 수도 있다. dict, MutableMapping등 매핑 자료형은 __missing__함수를 제공하는데, __getitem__에서 키를 찾을 수 없는 경우 실행된다. __missing__함수를 구현하면서 []연산자를 사용하여 __getitem__이 호출되게 될 수도 있는데 이 경우 순환적으로 재귀가 일어나지 않도록 유의하자. 일관성있게 작동하기 위해 get함수와 __contains__함수도 구현해야 한다. __contains__함수에서는 입력된 키가 매핑에 있는지 확인해야하는데 key in self와 같은 방식으로 구현할 경우 자기 자신의 __contains__함수를 호출하는 무한 재귀가 일어나기 때문에 key in self.keys()로 구현해야 한다. keys함수는 매핑의 키로 이루어진 집합과 같은 구조의 뷰를 가져오는 함수이다. 집합은 존재 유무를 판단하는데 특화되어있다.
collections.OrderedDict는 키를 삽입한 순서를 유지하는 매핑이다. 반복할 때 순서대로 항목을 순회한다. popitem함수를 통해 마지막에 삽입한 항목을 꺼낼 수도 있고 last=True인자를 함께 넘겨주어 처음에 삽입한 항목을 꺼낼 수도 있다.
collections.ChainMap은 여러 매핑을 묶어 관리한다. __contains__나 __getitem__등에서 키를 검색할 때 여러 매핑 중 하나에서라도 키가 발견되면 성공한다. ChainMap을 생성하고 나서도 묶은 매핑에 변화가 있으면 그대로 반영된다.
collections.Counter는 기본값이 0인 defaultdict이고, 멀티셋과 같이 키가 추가되면 수량을 세서 값으로 저장시킨다. elements나 most_common같은 유용한 함수가 구현되어있다.
collections.UserDict는 사용자 정의 매핑을 만들 때 상속해서 구현하라고 만들어놓은 매핑이다.
내장형은 상속하기 까다롭기 때문에 매핑을 사용자 정의형으로 만들고 싶을 땐 UserDict를 상속해야한다. UserDict는 MutableMapping을 상속하기 때문에 매핑의 모든 기능을 사용할 수 있다. 또한 UserDict는 매핑의 항목을 저장하는 dict형의 data라는 property를 가지고 있기 때문에 앞서 dict를 상속했을 때 무한 재귀의 방지를 위해 key in self.keys()와 같이 짜야 한다는 등의 문제를 고려할 필요가 없다.
또한 dict를 상속했을 때 __getitem__을 구현하면 통일성을 위해 get도 구현했어야 했던 것과 달리 UserDict를 상속하면 __getitem__을 구현하면 get은 그대로 상속받아 사용해도 된다. 또한 update 함수를 __init__ 내에서 사용해도 된다. update함수 내부에서는 __setitem__이 호출된다.
불변 시퀀스는 있지만 불변 매핑은 없다. 하지만 types.MappingProxyType을 통해 매핑의 읽기 전용 뷰를 얻을 수 있는데 원본 매핑을 가리고 MappingProxyType을 통과시킨 객체를 바깥에 제공하여 원본 매핑을 읽기만 하고 쓰기를 못하게 막을 수 있다.
집합은 set과 frozenset이 있다. set은 해시 불가능, frozenset은 해시가능이고 집합에 들어가려면 해시가능이어야 한다. 집합은 중복을 제거하므로 두 시퀀스의 공통 항목을 찾고 싶을 때 집합으로 바꿔 &연산자를 이용하는 방식으로 활용할 수 있다. set은 {1, 2, 3}과 같이 리터럴로 생성할 수 있고 set([1, 2, 3])과 같이 생성자를 사용할 수도 있다. 리터럴로 생성하는 것이 더 빠르고 가독성이 좋다. (dis모듈로 확인해보자) frozenset은 리터럴 표기가 없다.
지능형 리스트, 지능형 딕셔너리처럼 지능형 집합도 있다.
집합에 적용되는 수학적 연산이 모두 지원된다. 합집합, 교집합, 차집합, 대칭차집합을 구할 수 있고 부분집합, 진부분집합, 상위집합, 진상위집합인지 확인할 수 있다.
dict는 해시테이블로 구현되어있다. 해시테이블의 키는 해시가능이어야 한다. 해시가능의 조건은 아래와 같다.
1. 객체 수명주기동안 언제나 같은 고유의 값을 반환하는 __hash__함수가 구현되어있다.
2. __eq__를 통해 동치성을 확인할 수 있다.
3. a == b가 참이면 hash(a) == hash(b)도 참이다.
dict를 구현하는 해시테이블은 여러 개의 버킷으로 만들어져있다. 각 버킷의 크기는 동일하여 즉시 접근할 수 있고 각 버킷은 키와 값에 대한 참조로 이뤄져있다. dict에 항목을 접근하는 과정은 아래와 같다.
1. 키를 해싱하여 최하위 비트 n자리를 가지고 버킷에 접근한다. 버킷의 수에 따라 n의 값이 달라진다.
2. 접근한 버킷이 비어있는지 확인하여 비어있다면 그 버킷이 키와 값을 가리키도록 한다. 이때 해시된 키의 최하위 비트 n자리 외의 나머지 부분을 버킷에 저장해놓는다.
3. 접근한 버킷이 비어있지 않다면 해시된 키의 n자리 외의 나머지 부분을, 버킷이 비어있을 때 저장되었던 해시된 키의 나머지 부분과 비교하여 일치하는지 확인하여, 일치한다면 이전에 같은 키로 항목이 추가가 되었었던 것이고, 일치하지 않다면 해시 충돌이 일어난 것이다.
4. 해시 충돌이 일어났다면 해시된 키를 다시 해시하여 새로운 버킷을 찾는다.
일반적으로 해시 충돌은 평균적으로 1에서 2회 사이로 일어나기 때문에 매우 빠르게 항목을 찾을 수 있다. 그래서 in연산자를 통해 n개의 원소 중 특정 원소가 존재하는지 검색하는 과정을 1000회 수행한다 할 때 n을 1000에서 10000000으로 늘린 경우 dict에서는 겨우 1.67배 시간이 늘었지만 list에서는 순차적으로 순회하면서 존재 여부를 찾기 때문에 거의 만 배에 가까운 9279배의 시간이 걸렸다.
해시테이블의 빈 버킷이 적을 수록 해시 충돌이 많이 일어나므로 검색이 느려지기 때문에 보통 해시테이블의 전체 버킷 중 1/3이 비어있지 않다면 더 많은 버킷을 할당하여 새로운 해시테이블로 복사시킨다.
사용자 정의형에서는 기본적으로 id를 해시값으로 사용하고 모든 객체끼리 서로 다르다고 판단해주기 때문에 해시가능이다. 하지만 __eq__함수를 직접 구현한다면 해시가능 조건의 3번에 의해 반드시 적절하게 __hash__함수도 구현해야한다. 사용자 정의형을 해시가능 객체로 만들고 싶지 않다면 __hash__안에서 unhashable type: MyClass와 같은 type error를 발생시키도록 하여야 한다. __hash__함수를 구현하지 않는다면 dict에 키로 사용자 정의형을 넣을 경우 제대로 작동하지 않는다.
이러한 해시테이블의 성질에 의해 dict는 다음과 같은 성질을 가진다.
1. 키 객체는 반드시 해시가능이어야 한다.
2. 메모리 오버헤드가 크다.
3. 키 검색이 아주 빠르다.
4. 키 순서는 삽입순서에 따라 달라진다.
5. 항목을 추가하면 기존 키의 순서가 달라질 수 있다.
4번은 해시 충돌 때문에 그런 것이고 5번은 더 많은 버킷을 할당해 복사될 때 삽입순서가 달라질 수 있기 때문에 4번에 의해 그런 것이다. 이러한 성질 때문에 키를 순회하는 도중에 항목을 수정, 추가, 제거해서는 안된다.
set과 frozenset도 해시테이블로 똑같이 구현되어있기 때문에 모든 성질이 동일하다. set이 파이썬에 도입되기 전에는 dict에 임의의 값을 넣어 사용하기도 하였다.
str, bytes, datetime의 해싱에는 무작위 salt value가 관여한다. 이 값은 파이썬 프로세스가 실행되는 동안은 동일하게 유지되지만 새로 실행하면 달라지는 값으로, DOS공격을 피하기 위한 보안장치로 사용된다.
