[파이썬 알고리즘 인터뷰] 11장 해시 테이블

해시 테이블의 핵심은 해시 함수다. 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다. 해시 테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다. 덕분에 데이터 양에 관계 없이 빠른 성능을 기대할 수 있다는 장점이 있다. 해시 함수에서 무엇보다 중요한 것은 충돌을 최소화하는 것이다. 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것은 해싱이라 하며, 해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 기법 중 하나다.

 

충돌 처리 방법

• 개별 체이닝 : 충돌 발생 시 연결 리스트로 연결하는 방식
• 오픈 어드레싱 : 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식 (전체 슬롯의 개수 이상 저장할 수 없고, 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다고 보장할 수 없는 것이 특징)
  • 선형 탐사 : 충돌이 발생할 경우 해당 위치부터 순차적으로 탐사를 진행한다. 이때 해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치게 된다는 단점이 있다. 연속된 데이터 그룹이 생기는 현상을 클러스터링이라고 하며, 클러스터링 현상은 탐사 시간을 오래 걸리게 하고 전체적으로 해싱 효율을 덜어뜨리는 원인이 된다.

 

파이썬에서는 딕셔너리 자료형으로 해시 테이블이 구현되어 있다. 충돌이 발생했을 때는 개별 체이닝이 아닌 오픈 어드레싱 방식을 사용한다. 체이닝을 사용하지 않는 이유는 연결 리스트를 만들기 위해서는 추가 메모리 할당이 필요하고, 추가 메모리 할당은 상대적으로 느린 작업이기 때문이다. 오픈 어드레싱의 한 방식인 선형 탐사 방식은 일반적으로 체이닝에 비해 성능이 더 좋지만 슬롯이 80% 이상 차게 될 경우 급격한 성능 저하가 발생한다. 공간이 찰수록 탐사 시간이 더 오래 걸리며, 가득 찰 경우 더 이상 빈 공간을 찾을 수 없기 때문이다. 따라서 최근 루비나 파이썬 같은 모던 언어들은 오픈 어드레싱 방식을 택해 성능을 높이는 대신 로드 팩터를 작게 잡아 성능 저하 문제를 해결한다.

 

각 언어별 해시 테이블 구현

• C++ : 개별 체이닝
• Java : 개별 체이닝
• Python : 오픈 어드레싱

 

collections.defaultdict

key 값이 존재하지 않을 경우 default 값을 리턴해주는 함수로, 키가 존재하는지 여부를 판별하지 않아도 된다.  collections.defaultdict(default_factory, key=value,...)는 default_factory 와 key1=value1,key2=value2,...,keyn=valuen 를 인자로 받는데, default_factory 는 defaultdict의 초기값을 지정하는 인자이다. default_factory에는 list, int, set 등 메소드 형태의 값이 들어간다. int 함수를 넘기게 되면 int()는 0을 리턴한다.

from collections import defaultdict

counter = defaultdict(int)

 

collections.Counter

원소의 개수를 세주며 key 값이 존재하지 않을 경우 KeyError가 아닌 0을 출력해주기 때문에 에러에 대한 예외 처리를 하지 않아도 된다.