자료구조 - 사전과 셋 (Dictionary, Set)

개요

셋과 사전은 삽입 순서를 제외하면 미리 정해진 순서로 정해지지는 않으나 (파이썬 3.7 부터 딕셔너리에 값을 추가한 순서가 보존됩니다) 특정 데이터를 고유하게 참조할 수 있는 별도 객체가 있을 때 매우 적합한 자료구조 입니다. 알다시피 참조 객체를 "키", 특정 데이터를 "값" 이라고 칭하며, 키는 해시가 가능하다면 (hashable) 어떤 타입이도 상관 없습니다. 사전과 셋은 거의 같지만 셋에는 값이 없고 유일한 키를 저장하는 자료구조입니다. 

---

해쉬가 가능한 타입이란 ?

해쉬가 가능한 타입은 __hash__ 매직 함수, 그리고 키 값 비교를 위한 __eq__ 혹은 __cmp__ 매직 함수를 구현한 타입입니다. 파이썬의 내장 타입 (dict, set 등)은 모두 이를 구현하였기에 사용자가 사용할 때는 별도로 구현할 필요가 없습니다.

---

리스트와 튜플에서는 정렬되지 않은 상태에서의 최적의 경우 (이진 탐색) 탐색에 $O(log n)$ 시간복잡도로 값을 찾을 수 있지만 사전과 셋은 주어진 색인을 상수 시간복잡도로 ($O(1)$) 찾을 수 있습니다. 삽입 연산의 시간복잡도 또한 $O(1)$ 입니다. 하지만 사전과 셋은 보통 메모리를 많이 사용하고 사용하는 해쉬 함수에 전적으로 의존하기에 해쉬 함수가 느리다면 $O(1)$ 시간복잡도라도 실제 연산이 느려질 수 있습니다.

 

삽입과 검색

사전과 셋은 모두 해시 테이블을 사용해서 시간복잡도가 $O(1)$이 소요되는데, 이는 임의의 키를 리스트의 색인으로 변환하는 해시 함수를 사용하기 때문입니다. 즉, 데이터의 키를 리스트의 색인처럼 사용하도록 변환하는 작업을 통해 특정 데이터가 있는 지 효율적으로 확인할 수 있는 것이죠.

 

자료구조 - 해시 테이블 (Hash Table)

해시 테이블을 처음 생성하면 배열을 사용할 때처럼 메모리부터 할당하는데, 기존 배열 (리스트/튜플)과 달리 연속적인 메모리에 데이터를 나열하기 위해 키의 해쉬값을 마스크 처리하여 배열의 색인으로 정하게 됩니다. 만약에 메모리 블록을 8개 할당했다면, 마스크는 해시값이 할당된 메모리 블록의 수보다 작아야하므로 2진수 값 0b111 (7) 이 될 것이고, 해시값이 28975라면 메모리 블록의 색인은 29975 & 0b111 이 되게 됩니다. 사전이 할당받은 메모리 블록이 512개 라면 마스크 값은 0b111111111 (511) 이 될 것이고 블록의 색인은 29975 & 0b111111111 이 될 것입니다.

메모리 블록의 색인을 구했으면 해당 블록이 사용 중인지 검사해야겠죠. 빈 블록이라면 키와 값을 삽입하고, 해당 블록이 사용 중이고 내장 함수인 cmp로 비교하여 저장된 값이 삽입하려는 값과 같다면 이미 키/값이 해시 테이블에 있으므로 그냥 반환합니다. 하지만 키가 다르다면 데이터를 저장할 다른 곳을 프로빙을 통해 찾습니다. 또한, 파이썬은 키/값 데이터를 표준 배열에 덧붙이고 오직 배열의 색인만 해시 테이블에 저장하여 메모리 사용량을 50% 줄이는 기법을 사용합니다.

---

해시 테이블 포스트에서 open addressing 기반의 선형 탐색 프로빙을 알아보았는데, 파이썬의 프로빙 메커니즘은 원래 해시값에서 충돌을 피하기 위해 해시값의 더 상위 bit를 활용하게 됩니다. 위 예제에서 29975 해시값의 마지막 3bit 만 사용했지만 충돌이 발생하면 마지막 3bit 보다 더 상위의 bit를 활용하여 색인을 구하게 되는 것이죠. 이를 psuedo code로 나타내면 다음과 같습니다. 

def index_sequence(kay, mask=0b11, PERTURB_SHIFT=5):
	perturb = hash(key)
    i = perturb & mask
    yield i
    while True:
    	perturb >>= PERTURB_SHIFT  # 상위 bit 활용
        i = (i * 5 + perturb + 1) & mask  # mask 는 그대로
        yield i

특정 키로 값을 검색하는 과정도 비슷합니다. 키가 색인으로 변환되고 그 색인의 값을 검색하여 색인에 맞는 키가 있으면 해당 값을 반환합니다. 그렇지 않다면 프로빙을 사용해 새로운 색인을 만들어 일치하는 키를 찾을 때까지 이 과정을 반복합니다. 만약 생성한 색인이 빈 블록을 참조한다면 해당 데이터가 해시 테이블에 존재하지 않는다는 것이고 KeyError를 내뱉게 됩니다.

---

 

사용자 정의 해시 함수 예시

간단하게 파이썬의 ord 함수를 이용하여 입력의 첫 글자를 정수로 변환하는 해시 테이블을 만들어 보겠습니다. (해시 함수는 부호가 없는 정수를 return 해야 합니다)

class City(str):
    def __hash__(self):
        return ord(self[0])

data = {City("Rome"): 'Italy', City("San Fransisco"): 'USA', City('Jeju'): 'ROK', City('Barcelona'): 'Spain' }

여기서 Barcelona와 Rome의 해시가 충돌하게 되는데, 사전의 최소 항목 개수가 8개라 mask는 0b111를 사용하게 되어 다음과 같이 같은 색인을 만들기 때문입니다.

hash('Barcelona') = ord('B') & 0b111 = 66 & 0b111 = 0b1000010 & 0b111 = 0b010
hash('Rome') = ord('R') & 0b111 = 82 & 0b111 = 0b1010010 & 0b111 = 0b010

 

삭제

해시 테이블에서 값을 삭제할 때는 단순히 해당 메모리 블록을 NULL로 만들지 않습니다. NULL 을 프로빙 시 해시 충돌을 위한 감싯값으로 사용하기 때문인데, 따라서 해당 블록이 비었음을 나타내는 특수한 값을 기록해둡니다. 예를 들어 Rome이 삭제된 이후에 Barcelona를 검색하면 Rome이 들어있던 블록이 비었음을 나타내는 값이 있는 배열 항목을 먼저 만나게 되고 index_sequence 함수에 따라 다음 색인을 검색하게 됩니다. 해시 테이블의 빈 슬롯은 새로운 값이 쓰이거나 해시 테이블의 크기가 변경될 때 삭제됩니다.

 

크기 변경

해시 테이블에 항목이 추가되면 해시 테이블의 크기도 그에 맞춰 변경되어야 합니다. 해시 테이블의 임계 크기는 2/3 으로 항목 개수가 테이블의 2/3 이하라면 임계 크기까지 계속 사용합니다. 2/3 이 넘어가면 더 큰 메모리를 할당하고 그 크기에 맞게 마스크 값을 조정한 후 모든 항목을 새로운 해시 테이블로 옮기게 됩니다. 이 과정에서 바뀐 마스크 값으로 인해 색인을 새로 계산해주어야 해서 꽤 비싼 작업이지만 크기 변경은 여유 공간이 아주 적을 때만 수행되므로 개별 항목 추가 (amortized 복잡도, 평균 복잡도)는 시간복잡도가 $O(1)$로 유지된다고 볼 수 있습니다. (일부 특정 케이스의 삽입은 더 비싸지만 평균적으로는 $O(1)$)

기본적으로 해시 테이블의 최소 크기는 8이고 2/3 씩 찰 때마다 3배씩 늘립니다. 따라서 빈 사전에 6번째 항목이 삽입되면 사전 크기는 18이 되고, 13번째 항목이 삽입되면 39개로 매번 크기가 3배씩 늘어나게 됩니다. 또한, 해시 테이블의 많은 항목이 삭제되면 크기를 줄이게 되고 삽입 연산 중에 크기 변경이 발생합니다.

8; 18; 39; 81; 165; 333; 669; ....