[자료구조 및 프로그래밍] 12. Hashing & Hash Table

자료구조와 탐색 시간

지금까지 자료구조를 정리하면서 주요하게 다뤘던 내용 중 하나는 바로 "탐색" 이었다.

그리고 원하는 자료를 탐색하기 위해 수행한 가장 근본적인 동작은 바로 키를 비교하는 것이었다.

어떤 키가 다른 키와 같은지 다른지, 혹은 큰 지 작은 지를 비교하여 원하는 값을 탐색해내갔다.

 

여기 3글자 알파벳 소문자로 이루어진 이름과 4개의 숫자 쌍을 저장하는 간단한 주소록 프로그램이 있다.

그리고 이 주소록 프로그램에서 주소록 정보를 BST를 이용해 저장한다고 해보자.

만약 1000개의 주소록 데이터를 BST에 저장한다면, 최적의 경우 BST의 높이는 log(1000) 이므로 대략 10이라고 할 수 있고, 최악의 경우의 높이는 대략 1000이 될 것이다.

또 평균적으로는 1000개의 데이터를 BST에 넣으면 20 미만의 높이를 갖는다.

이 말은, 우리가 데이터를 찾고, 추가하고, 삭제하는데 20번의 비교가 필요하다는 뜻이다.

그리고 당연하게도 BST에 넣는 주소록 데이터의 양이 늘어날 수록, 그에 비례해 탐색 시간 역시 증가한다.

---

해시

그런데, 오늘 정리할 hashing 을 이용하면 이상적인 상황에서 데이터가 얼마나 많이 늘어나는가에 상관 없이 데이터를 O(1) 즉, 단 한번의 연산으로 찾을 수 있다.

 

주소록 프로그램에서는 '이름' 이라는 키를 가지고 번호를 찾는다.

이제 그 '이름' 이라는 키로 가능한 모든 집합을 U 라고 해보자.

이름은 알파벳 소문자로 구성될 수 있으므로, 26^3 = 대략 20000 가지의 key가 존재한다.

 

h 라는 function 이 있다고 생각해보자.

이 function은 U 를 정의역으로 하며, 0부터 M-1 까지의 값을 공역으로 갖는다고 해보자.

우리는 이런 function 을 'hash function' 이라고 부르고, 0부터 M-1 사이의 값을 hash value 라고 부른다.

그리고 이를 h(k) 와 같이 쓸 수 있다.

 

다시 위 주소록 프로그램의 상황에 대해서 생각해보자.

만약 어떤 키값을 넣었을 때, 0부터 1999 사이의 값을 내는, (즉, M = 2000 ) 해시 함수를 가지고 있고, 모든 키값에 대해 해시함수의 결과값이 서로 다르게 나온다면, 우리는 2000사이즈 배열에 우리가 원하는 데이터를 모두 저장할 수 있다.

그리고 이 데이터에 접근할 때는 오직 해시 함수에 의한 해시 값 계산만큼의 시간밖에 걸리지 않는다.

 

그러나 실제로는 키값의 집합 U의 사이즈가 아주 큰 반면 해시함수가 내놓는 값의 범위는 비교적 좁아서, 어떤 두 키값 k1, k2 에 대해 h(k1) = h(k2) 가 되는 상황이 발생하는 경우가 많으며, 이런 경우를 '충돌' 이라고 한다.

 

그렇다면 보통 해시함수는 어떻게 구현할까?

좋은 해시함수는 빠르게 계산할 수 있으면서도, 충돌이 적게 일어나는 함수다.

'해시' 라는 말 자체가 어떤 덩어리를 잘게 잘게 썰어낸다는 의미가 있다 (해시 브라운의 그 해시도 그 뜻이다)

그래서 좋은 해시함수는 겹치지 않게 작은 조각으로 잘 조각내는 함수라고 할 수 있다.

 

보통 해시함수는 아래와 같은 형태를 자주 사용한다.

 

h(k) = k mod M

 

그리고 보통 M 값은 소수를 사용한다.

(합성수를 사용할 때보다 충돌 횟수가 꽤 크게 줄어든다.)

 

이 '해시'는 여러 곳에서 사용된다.

대표적으로 사용하는 것이 해시 테이블 (해시 맵) 과 Set 자료구조를 구현하는데 사용할 수 있다.

또 비밀번호를 평문이 아니라 해싱하여 저장하므로써, 외부 사람이 봤을 때 평문을 알 수 없게 하는 데에도 사용된다.

---

해시 충돌의 해결

해시는 이상적으로는 매우 좋은 자료구조이다.

임의의 데이터를 상수시간만에 찾아낼 수 있기 때문이다.

그렇지만 실제로는 '해시 충돌' 문제가 있어 이를 해결해야 한다.

 

해시 충돌을 해결하는 방법은 크게 2가지로 나누어 진다.

 

1. Chaining

2. Open Addressing

 

첫번째 방법인 체이닝은, 충돌이 일어나는 것 자체를 인정하고, 해시값에 해당하는 위치에 하나의 데이터를 저장하는 것이 아니라 '연결 리스트' 의 노드를 저장한다.

 

그래서 만약 어떤 해시값에 해당하는 데이터가 들어오면, 그 데이터를 연결 리스트에 차곡 차곡 추가하는 방식이다.

어떤 데이터를 찾을 때도, 키을 해싱한 값에 위치해있는 연결리스트를 순회하여 찾으면 된다.

 

두번째 방법인 open addressing 방식은, 해시충돌이 일어났을 때, 적당한 규칙을 가지고 그 값을 비어있는 다른 키값에 저장하는 것이다.

예를 들어 h(k) 위치에 이미 값이 있다면 h(k) + 1 위치나 h(k)-1 위치가 비어있을 때 이곳에 그냥 저장하는 방식이다.

값을 찾을 때도 h(k) 위치에 있는 값이 찾는 값과 다르다면 그 주변을 탐색하여 찾는 방식이다.

---

지금까지 Hashing 에 대하여 간단하게 정리해보았다.

다음 글에서는 파이썬의 dictionary 가 어떻게 구현되어 있는지, 해시를 쓰고 있다면 어떤 해시 함수를 사용하고 있는지 간단하게 살펴보려고 한다.