Hash table, 비전공자 문돌이가 설명하는 파이썬(Python) 기본 문법 (7)

1. 해시(Hash)란? 

Set과 Dictionary에선 원소를 검색하는 것의 시간 복잡도는 O(1) 입니다. 이유는 Hash라는 기법을 사용하기 때문인데요. 차근차근 알아보겠습니다.

L = [1, 3, 5, 10] 이라는 리스트가 있다고 합시다. 그러면 아래 테이블과 같이 표시될 것입니다.

하지만 데이터 자체를 인덱스로 생각하면 어떨까요? 이는 Data indexed arrays라는 개념인데, 아래 테이블을 보면 이해할 수 있습니다. [1, 3, 5, 10] 자체를 인덱스로 생각하고, 해당 인덱스의 값들은 boolean 타입으로 표시하는 것입니다.  

Data indexed arrays는 처음 선언할 때 인덱스 값들이 모두 Flase입니다. 나중에 어떤 원소가 추가될 때는 해당하는 인덱스 값을 True로 바꿔주면 됩니다.

이렇게 되면 in 연산도 정말 간단해지죠. 인덱스 하나하나를 찾아가는 과정이 필요 없고 인덱스 값이 True냐, False냐만 따지면 되는 것입니다. 따라서 시간 복잡도는 O(1)이 되겠죠.

지금까지 숫자만 다루었는데, 문자열은 어떻게 인덱스로 변환할 수 있을까요? 영어 알파벳(소문자)을 예로 들어보겠습니다. 총 26개의 알파벳이 있고, a=1, b=2, c=3..., z=26 식으로 매핑합니다.(27진수)

문자열 "abc"의 인덱스는 $(1x27^2) + (2x27^1) + (3x0^1) = 759$가 됩니다. 사용자가 "abc"를 입력하면 Data indexed arrays에서 759번째 인덱스 값이 True가 되는 것입니다. 

일반적으로 영어를 기준으로 했을 때, 256진수로 문자열(문자, 기호 등)을 표현하는 아스키 코드(ASCII Code)를 사용합니다. 아스키 코드는 제 블로그 다른 글을 참고해주세요. 비전공자 문돌이가 설명하는 파이썬(Python) 기본 문법 (1) (tistory.com)

비전공자 문돌이가 설명하는 파이썬(Python) 기본 문법 (1)

Integer Overflow란?

이전에도 언급했던 적이 있지만, 파이썬은 integer overflow 문제가 발생하지 않습니다. 하지만 C나 Java와 같은 언어는 최대로 입력할 수 있는 정수 크기가 제한되어 있습니다. 'int32'라고 선언하면 $2^{32}-1$까지 밖에 표현하지 못합니다. 만약 최대 크기를 넘어가게 되면 훨씬 작은 값이 리턴됩니다. 예를 들어, 최대 크기가 10인데, 이보다 더 큰 12를 입력했다면 12 % 10 = 2를 리턴합니다. 

M: maximum value 
n: integer larger than M
result: n % M

아스키 코드로 문자열을 인덱스로 바꾸려면 이러한 integer overflow가 발생합니다. "abcdefghijklmnopqrstuvwxyz"를 입력한다면 'int32' 크기보다 훨씬 커지기 때문에 해당 문자열은 $2^{32}-1$로 나눈 나머지 값으로 표현할 수 밖에 없습니다. 이렇게 되면 문자열마다 나눈 나머지 값이 같아지게 되는 중복(collisions) 문제가 생기겠죠.  "abcd"랑 "abcdefg"가 똑같은 인덱스를 가지는 중복 문제는 어떻게 해결할 수 있을까요? 이를 해결하는 것이 해시 함수(Hash Function)입니다. 

먼저 중복 문제부터 처리해보겠습니다. 우리는 인덱스 밸류 값을 boolean 타입이 아니라 또 다른 어레이, set, Linked list로 활용할 수 있습니다. 여기선 Linked list를 통해 설명해보겠습니다. Linked list는 센티넬 노드를 사용하기 때문에 sentinel.next가 진정한 첫 번째 노드임을 지난 시간에 살펴봤었죠. sentinel.val은 None이 아닌 특정한 값이지만 숫자적 의미는 중요하지 않습니다. 

그리고 다른 인덱스의 기본값은 None이 되며 Linked list가 들어오면서 None이 풀리고 노드를 연결합니다. 

def __init__(self) -> None:
    self.array = [None]*429491254
   
def add(self, x) -> None:
    i = hash_value(x)
    if self.array[i] == None:
        self.array[i] = SLList() # Linked List 구현
    self.array[i].addFirst(x)
    
A = di_array()
A.add("abcdefg")
A.add("abcd!")
"abcd" in A # <- 1,655,344,223번째 인덱스의 원소들을 모두 search

위 코드의 결과가 바로 위에 있는 테이블 모양입니다.

중복 문제를 처리했기 때문에 그렇게 큰 어레이 사이즈가 필요 없게 되었습니다. 즉 'int32'라고 선언하지 않고 더 작은 'int8'을 선언해도 되는 것이죠. 이제 해시 테이블(Hash table)을 살펴볼 차례입니다. 

해시 테이블(Hash table)이란?

해시 테이블이란, 1) 데이터를 해시 함수를 통해 해시값으로 바꾸고, 2) 해당 해시값을 리덕션(reduction)하여 유효한 값으로 바꾼 최종 결과를 말합니다. 간단하게 총 12개의 인덱스를 사용한다고 하면 과정은 아래와 같습니다. 

1. When you add item x, compute its hashValue i
2. Add x to di_array[i % 12] instead of di_array[i]

해시 테이블을 더 자세히 알아보죠. 해시 테이블 성능을 보면 원소를 추가하거나 in 연산을 진행할 때 시간 복잡도가 모두 O(1)입니다. 어떻게 O(1)이 되는지 아래에서 설명드리겠습니다.

위에서 우리는 인덱스 밸류 값에 Linked list를 사용하기로 했고, 이 연결고리를 체인(chian)이라 부릅니다. 이 연결고리의 가장 긴 길이(or 깊이)를 K로 나타냅니다.   

K: length of the longest chain

그럼 K는 best case인 N/M과 worst case인 N 사이에 존재할 것입니다. 주의할 점은 best case일 때 역시 시간 복잡도는 결국 O(N)이 된다는 것인데요. M이 5로 고정되어 있다면, O(K)=O(N/5)=O(N)이 되겠죠. 즉 M을 고정시켜서는 안된다는 결론을 얻을 수 있습니다. 

따라서 N이 증가할 때마다 일정 비율대로 M 역시 증가시킵니다. 시간 복잡도 O(K)=O(N/M)이 O(N)이 아니라 최대한 O(1)이 되도록 해야 합니다. 간단한 예로는 N/M >= 1.5일 때 M을 2배 늘리는 전략(resize)을 취할 수 있겠죠. 이렇게 하면 아무런 전략이 없을 때보다 K 크기는 평균적으로 1.5배 줄어듭니다. M을 얼마나 늘릴 것인가는 엄격하게 정해지지 않았지만 resize 자체 연산도 O(N)을 잡아먹기 때문에 자주 하는 것은 좋지 않습니다. 그래서 평균적으로 2배를 늘리는 것이 가장 효과가 좋다고 합니다.

M=5, N=18일 때, N=8이 된 순간 N/M=1.6이 되어 resize를 진행합니다. M=10이 되고, 해시값을 리덕션할 때 5가 아닌 10으로 나누게(di_array[i % 10]) 됩니다. 

resize 덕분에 search operation(add, in 연산)의 시간 복잡도는 O(1)이 됩니다. 하지만 resize를 하게 되면, 기존에 있던 원소를 재배열하기 때문에 O(N)이 걸린다고 했는데요. 다행히도 N/M >= 1.5일 때 M을 2배씩 증가시키기 때문에 resize를 계속 하는 것은 아닙니다. M=1일 때, N=2가 되면 M * 2를 하여 M=2가 되고, N=4가 되면 M * 2를 하여 M=4가 됩니다. 즉 resize하는 순간은 M=1, 2, 4, 8, ..., N이 되는 것이죠. 

따라서 총 N개의 원소를 더한다고 했을 때 resize 시간 복잡도는 1 + 2 + 4 + ... + N = 2N-1입니다. 이는 N개 원소가 추가될 때까지 소요된 총 시간으로 한 번 추가될 때 걸린 평균 시간은 O((2N-1)/N)=O(1)이 됩니다. 

지금까지 나온 Data indexed array, Data indexed array with chains(no resizing), Data indexed array with chains(with resizing)의 성능을 비교해보겠습니다.

케이스	add	in
SLList	O(1)	O(N)
List	O(1)	O(N)
Data indexed array	O(1)	O(1)
Data indexed array with chains(no resizing)	O(N)	O(N)
Data indexed array with chains(with resizing)	O(1)	O(1)

사실 hashValue를 구하기 위한 Hash Function까지 파고드려면 더 복잡합니다.(저 또한 알지 못합니다 ㅠㅠ) 다만 유용한 hashValue를 구하려면 아무래도 랜덤성이 포함되어야 합니다. 또한, 중복 문제야 완벽하게 해결할 수는 없지만 그래도 생각해볼 문제가 있습니다. 긴 문장이 입력으로 들어왔을 때, 마지막 글자만 같은 경우 모두 hashValue가 같게 된다면 이도 문제가 되는 것이죠. 

Hash Function과 관련해서는 나중에 좀 더 공부하고 추가 설명을 하도록 하겠습니다.