[Python] 파이썬 해시 테이블 구현 방식 - 개별 체이닝?, 오픈 어드레싱?

해시란?

해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다.

충돌

아무리 좋은 해시 함수라도 밑의 그림과 같이 충돌은 발생하게 된다.

이 그림에서 윤아와 서현은 해시 값이 2로 같은 값이 되어 충돌이 발생했다. 이처럼 충돌이 발생할 경우 어떤 식으로 처리하게 되는지 살펴보자.

개별 체이닝

입력 값을 밑의 표와 같이 정해보자. 해시는 키를 해싱한 결과며, '윤아'와 '서현'을 해싱한 결과는 충돌한다고 가정한다.

이 표를 개별 체이닝(Separate Chaining) 방식으로 구현하면 밑의 그림과 같다.

해시 테이블의 기본 방식이기도 한 개별 체이닝은 충돌 발생 시 이 그림과 같이 연결 리스트로 연결하는 방식이다. 충돌이 발생한 '윤아'와 '서현'은 '윤아'의 다음 아이템이 '서현'인 형태로 서로 연결 리스트로 연결되었다. 이처럼 기본적인 자료구조와 임의로 정한 간단한 알고리즘만 있으면 되므로, 개별 체이닝 방식은 인기가 높다. 원래 해시 테이블 구종의 원형이기도 하며 가장 전통적인 방식으로, 흔히 해시 테이블이라고 하면 바로 이 방식을 말한다.

오픈 어드레싱

오픈 어드레싱(Open Addressing) 방식은 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식이다. 사실상 무한정 젖아할 수 있는 체이닝 방식과 달리, 오픈 어드레싱 방식은 전체 슬롯의 개수 이상은 저장할 수 없다. 충돌이 일어나면 테이블 공간 내에서 탐사를 통해 빈 공간을 찾아 해결하며, 이 때문에 개별 체이닝 방식과 달리, 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다.

오픈 어드레싱으로 표현하면 위의 그림과 같다. 여러 가지 오픈 어드레싱 방식 중에서 가장 간단한 방힉인 선형 탐사 방식은 충돌이 발생할 경우 해당 위치부터 순차적으로 탐사를 하나씩 진행한다. 선형 탐사 방식은 구현 방법이 간단하면서도, 의외로 전체적인 성능이 좋은 편이기도 하다.

언어별 해시 테이블 구현 방식

리스트와 함께 파이썬에서 가장 흔하게 쓰이는 자료형인 딕셔너리는 해시 테이블로 구현되어 있다. 그렇다면 과연 파이썬의 해시 테이블은 충돌 시 어떤 방식을 사용할까? 정답부터 말하자면 오픈 어드레싱 방식으로 구현되어 있다. CPython 구현에는 다음과 같은 주석이 적혀 있다.

체이닝 시 malloc으로 메모리를 할당하는 오버헤드가 높아 오픈 어드레싱을 택했다.

연결 리스트를 만들기 위해서는 추가 메모리 할당이 필요하고, 추가 메모리 할당은 상대적으로 느린 작업이기 때문에 택하지 않았다고 기술했다.

위의 그림에서 오픈 어드레싱의 한 방식인 선형 탐사 방식은 일반적으로 체이닝에 비해 성능이 더 좋다. 그러나 슬롯의 80% 이상이 차게 되면 급격한 성능 저하가 일어나며, 체이닝과 달리 전체 슬롯의 전체 개수 이상, 즉 로드 펙터 1 이상은 저장할 수 없다. 빈 공간을 탐사하는 선형 탐사 방식은 공간이 찰수록 탐사에 점점 더 오랜 시간이 걸리며, 가득 차게 될 경우 더 이상 빈 공간을 찾을 수 없기 떄문이다. 따라서 최근의 루비나 파이썬 같은 모던 언어들은 오픈 어드레싱 방식을 택해 성능을 높이는 대신, 로드 펙터를 작게 잡아 성능 저하 문제를 해결한다. 파이썬의 로드 펙터는 0.66으로 자바보다 작으며 루비는 0.5로 훨씬 더 작다.

출처

파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]