해싱, 해시함수, 해시테이블
25 Oct 2017 | Data structure
이번 글에서는 해싱(hashing)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아, 그리고 스택오버플로우와 고니 님의 블로그를 참고해 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concepts
해시함수(hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 합니다.
해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one 대응)하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생하게 됩니다. 아래 그림은 이름-전화번호부를 매핑하기 위한 해시함수를 개념적으로 나타냈습니다. 예시의 해시함수는 ‘John Smith’와 ‘Sandra Dee’를 모두 ‘02’로 매핑해 해시충돌을 일으키고 있습니다.
##해시테이블의 장점
해시충돌이 발생할 가능성이 있음에도 해시테이블을 쓰는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리하기 위해서입니다. 예컨대 해시함수로 하드디스크나 클라우드에 존재하는 무한에 가까운 데이터(키)들을 유한한 개수의 해시값으로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있게 됩니다.
색인(index)에 해시값을 사용함으로써 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행할 수 있습니다. 위 그림의 경우 해시함수에 ‘Lisa Smith’를 입력하면 01이라는 색인이 생성됩니다.
해시함수는 언제나 동일한 해시값을 리턴하고, 해당 색인만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근할 수 있으며, 색인은 계산이 간단한 함수(상수시간)로 작동하기 때문에 매우 효율적입니다. 다시 말해 해시는 데이터 액세스(삽입, 삭제, 탐색)시 계산복잡성을 $O(1)$을 지향합니다.
해시테이블을 다른 자료구조와 비교해보겠습니다. 이진탐색트리와 그 변형의 경우 메모리를 효율적으로 사용하는 편이지만 데이터 탐색에 소요되는 계산복잡성은 $O(\log{n})$입니다. 배열(array)의 경우 데이터 탐색에 따른 계산복잡성은 $O(1)$이지만, 메모리를 미리 할당해 둬야 하기 때문에 공간 효율적이라고 말하기 어렵습니다.
해시는 보안 분야에서도 널리 사용된다고 합니다. 키와 해시값 사이에 직접적인 연관이 없기 때문에 해시값만 가지고는 키를 온전히 복원하기 어렵기 때문입니다. 아울러 해시함수는 길이가 서로 다른 입력데이터에 대해 일정한 길이의 출력을 만들 수 있어서 ‘데이터 축약’ 기능도 수행할 수 있습니다.
다만 현재까지 개발된 거의 모든 해시함수는 해시충돌을 일으키는 것으로 확인됐다고 합니다. 물론 해시충돌 자체를 줄이는 것도 의미가 있겠습니다만, 중요한 것은 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 하는 것입니다. 극단적으로 위 그림에서 모든 키가 02라는 동일한 해시값으로 매핑이 될 경우 데이터를 액세스할 때 비효율성이 커지고, 보안이 취약(서로 다른 키인데도 동일한 해시값)해져 굳이 해시를 도입해 데이터를 관리할 이유가 없어집니다.
해시테이블
해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조를 해시테이블(hash table)이라고 합니다. 이 때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot)이라고 합니다. 해시테이블의 기본 연산은 삽입, 삭제, 탐색(search)입니다. 다음 그림과 같습니다.
위 예시 그림 각 버킷에는 데이터가 다음과 같이 저장됩니다.
Index(Hash Value)
Data
01
(Lisa Smith, 521-8976)
02
(John Smith, 521-1234)
…
…
키의 전체 개수와 동일한 크기의 버킷을 가진 해시테이블을 Direct-address table이라고 합니다. 다음 그림과 같습니다.
Direct-address table의 장점은 키 개수와 해시테이블 크기가 동일하기 때문에 해시충돌 문제가 발생하지 않는다는 겁니다. 하지만 전체 키(unverse of key)가 실제 사용하는 키(actucal key)보다 훨씬 많은 경우 사용하지 않는 키들을 위한 공간까지 마련해야 하는 탓에 메모리 효율성이 크게 떨어집니다. 위 그림처럼 1, 9, 4, 0, 7, 6을 위한 버킷은 굳이 만들어놓을 이유가 없습니다.
보통의 경우 Direct-address table보다는 “해시테이블 크기($m$)가 실제 사용하는 키 개수($n$)보다 적은 해시테이블”을 운용합니다. 다뤄야할 데이터가 정말 많고, 메모리 등 리소스 문제도 생기기 때문입니다. 이 때 $n/m$을 load factor($α$)라고 합니다. 해시테이블의 한 버킷에 평균 몇 개의 키가 매핑되는가를 나타내는 지표입니다. Direct-address table의 load factor는 1 이하이며, 1보다 큰 경우 해시충돌 문제가 발생합니다.
해시충돌 문제를 해결하기 위해 다양한 기법들이 고안됐습니다. chining은 해시테이블의 크기를 유연하게 만들고, open addressing은 해시테이블 크기는 고정시키되 저장해 둘 위치를 잘 찾는 데 관심을 둔 구조입니다. 이뿐 아니라 해시함수를 개선하는 접근도 있습니다. 차례대로 살펴보겠습니다.
chaining
해시충돌 문제를 해결하기 위한 간단한 아이디어 가운데 하나는 한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써 모든 자료를 해시테이블에 담는 것입니다. 해당 버킷에 데이터가 이미 있다면 체인처럼 노드를 추가하여 다음 노드를 가리키는 방식으로 구현(연결리스트)하기 때문에 체인이라는 말이 붙은 것 같습니다. 유연하다는 장점을 가지나 메모리 문제를 야기할 수 있습니다. 아래 그림과 같습니다.
위 예시 그림의 해시함수는 ‘John Smith’와 ‘Sandra Dee’를 같은 해시값(152)으로 매핑하고 있습니다. 이 경우 해당 해시값에 대응하는 동일한 버킷에 두 개 데이터를 저장해 둡니다. 데이터를 위 그림처럼 연결리스트로 저장해 둘 경우 최근 데이터는 연결리스트의 head에 추가합니다(이 경우 $O(1)$, tail에 저장할 경우 $O(n)$이 됨, 자세한 내용은 이곳 참고)
삽입, 탐색, 삭제 연산과 계산복잡성
chaining 방식의 계산복잡성을 따져보겠습니다. 삽입(insertion), 탐색(search), 삭제(delete) 세 가지가 있습니다. 본격적인 분석에 앞서 가정을 하나 하겠습니다. 해시테이블의 크기가 $m$, 실제 사용하는 키 개수가 $n$, 해시함수가 키들을 모든 버킷에 균등하게 할당한다고 가정하면, 버킷 하나당 $n/m=α$개의 키들이 존재할 것입니다. 예컨대 위 그림 예시에서 2560개의 키에 해당하는 데이터를 저장한다면 버킷 하나당 10개 데이터가 있다는 얘기입니다.
삽입의 계산복잡성입니다. 예컨대 위 예시그림의 해시함수가 254로 매핑하는 ‘Mark Zuckerberg’의 전화번호를 새로 추가한다고 칩시다. ‘Mark Zuckerberg’라는 키를 해시값 254로 매핑하는 데 $O(1)$이 듭니다. 해당 해시값에 해당하는 연결리스트의 head에 이를 추가하는 데 $O(1)$이 듭니다. 따라서 삽입의 계산복잡성은 둘을 합친 $O(1)$입니다.
이번엔 탐색을 살펴보겠습니다. 두 가지로 나눠서 생각해 보겠습니다.
쿼리 키값에 해당하는 데이터가 해시테이블에 존재하지 않는 경우(unsuccessful search)입니다. 예컨대 위 예시그림의 해시함수가 152로 매핑하는 ‘Steve Jobs’의 전화번호를 탐색한다고 가정해 봅시다. 이 경우 키를 해시값으로 바꾸고, 해당 해시값에 해당하는 버킷의 요소들 $α$개를 모두 탐색해봐야 존재하지 않는다는 사실을 알 수 있습니다. 따라서 unsuccessful search의 계산복잡성은 $O(1+α)$가 됩니다.
이번엔 쿼리 키값에 해당하는 데이터가 해시테이블에 존재하는 경우(successful search)입니다. 예컨대 ‘Sandra Dee’의 전화번호를 위와 같은 해시테이블에서 탐색한다고 가정해 봅시다. 이를 위해선 ‘Sandra Dee’를 해시값(152)으로 바꾸고 버킷 요소들 가운데 ‘Sandra Dee’에 해당하는 데이터가 있는지 탐색해봐야 할 겁니다.
Big O notation의 계산복잡성을 따져보기 위해선 최악의 경우를 고려해야 합니다. 해당 버킷의 tail에 값이 있는 경우일 겁니다. 데이터가 해시테이블에 존재한다고 가정했으므로 버킷 내 $α$개 요소 가운데 반드시 찾고자 하는 값이 존재합니다. $α-1$개를 비교했는데도 원하는 값을 찾지 못했다면 tail값은 따져볼 필요도 없이 찾고자 하는 값이 됩니다.
그런데 버킷의 요소들 평균이 $α$개일 때 successful search는, 요소가 $α-1$개인 버킷을 탐색했는데 찾는 값이 없어서(unsuccessful search), 해당 버킷에 쿼리에 해당하는 데이터를 삽입하여 결과적으로 해당 버킷의 요소 수를 $α$개로 만드는 계산량과 동일합니다. unsuccessful search의 계산복잡성은 $O(1+α)$이므로, successful search의 계산복잡성 또한 이와 같은 $O(1+α)$가 됩니다.
삭제의 계산복잡성은 탐색과 본질적으로 비슷합니다. 우선 쿼리 키값을 해시값으로 매핑하고($O(1)$), 해당 버킷 내에 키값에 해당하는 데이터가 있는지 탐색($O(α)$)해야 하기 때문입니다. 물론 탐색 연산과 비교해 삭제에 드는 계산도 추가적으로 필요하나, 연결리스트로 해시테이블을 구현할 경우 삭제 연산의 계산복잡성은 $O(1)$이므로 무시할 만한 수준입니다.
chaining에서 삽입을 제외한, 탐색/삭제의 계산복잡성은 버킷당 요소 개수의 평균 $α$가 좌지우지하는 구조입니다. 최악의 경우 한 버킷에 모든 데이터가 들어있어 $O(n)$이 될 수 있습니다. 하지만 데이터의 개수가 해시테이블 크기의 두 세배쯤($α$가 2~3)만 되어도 탐색, 삭제는 $O(1)$이 됩니다.
open addressing
open addressing은 chaining과 달리 한 버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시테이블입니다. 해시함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용한다는 취지에서 open addressing이라는 이름이 붙은 것 같습니다. 메모리 문제가 발생하지 않으나 해시충돌이 생길 수 있습니다.
예컨대 해시함수를 ‘키값을 7로 나눈 나머지’로 정의했다고 칩시다. 그리고 나서 키 50, 700, 76, 85, 92, 73, 101순으로 데이터를 저장한다고 가정해 봅시다. 다음 그림과 같습니다.
위 예시에서 주목할 부분은 85부터입니다. 85를 7로 나눈 나머지는 1입니다. 그런데 해시값 1에 해당하는 버킷에 이미 50이 있으므로, 다음 버킷(2)에 저장해 둡니다. 92를 7로 나눈 나머지 역시 1입니다. 그런데 해시값 1에 해당하는 버킷에 이미 50이 있고, 그 다음 해시값 2 버킷에 85가 있으므로, 92를 3번 버킷에 저장합니다. 73, 101 역시 자신의 버킷에는 이미 주인이 있으므로 빈 버킷에 할당합니다.
삭제, 삽입, 탐색
해시함수가 ‘키값을 8로 나눈 나머지’이고 10, 18, 26 순으로 해시테이블에 삽입한다고 가정해 보겠습니다. 세 숫자 가운데 첫번째 입력값 10을 제외한 18, 26은 원래 버킷(2) 말고 각각 다음(3), 다음다음(4) 버킷에 저장하는 것이 open addressing의 방식입니다.
0
1
2
3
4
5
6
7
8
10
18
26
위 표에서 18을 삭제해 보겠습니다. 18의 해시값은 2인데 여기엔 10이 저장돼 있으므로 스킵하고, 그 다음 버킷(3)을 탐색해 봅니다. 18이 여기에 있군요. 지웁니다. 다음과 같습니다.
0
1
2
3
4
5
6
7
8
10
26
위 표에서 26을 탐색해 보겠습니다. 26의 해시값은 2인데 여기엔 10이 저장돼 있으므로 스킵하고, 그 다음 버킷(3)을 탐색해 봅니다. 그런데 비어 있습니다. 별도로 조치하지 않으면 알고리즘은 ‘2번 해시값 1칸 옆인 3에 저장된 데이터가 없구나, 해시충돌이 발생한 적이 없다는 얘기네, 탐색을 끝내야 겠다’고 판단할 수 있습니다.
이를 해결하기 위해 삭제 연산 때 아래처럼 별도로 표시를 해둡니다.
0
1
2
3
4
5
6
7
8
10
DEL
26
probing
open addressing은 그 구조상 해시충돌 문제가 발생할 수 있습니다. 앞선 예시에서 살펴봤듯 특정 해시값에 키가 몰리게 되면 open addressing의 효율성이 크게 떨어집니다. 해시충돌은 탐사(probing) 방식으로 해결할 수 있습니다. 탐사란 삽입, 삭제, 탐색을 수행하기 위해 해시테이블 내 새로운 주소(해시값)를 찾는 과정입니다.
선형 탐사(Linear probing)는 가장 간단한 방식입니다. 앞선 예시에 해당합니다. 최초 해시값에 해당하는 버킷에 다른 데이터가 저장돼 있으면 해당 해시값에서 고정 폭(예컨대 1칸)을 옮겨 다음 해시값에 해당하는 버킷에 액세스(삽입, 삭제, 탐색)합니다. 여기에 데이터가 있으면 고정폭으로 또 옮겨 액세스합니다.
그런데 탐사 이동폭이 고정돼 있는 선형탐사는 특정 해시값 주변 버킷이 모두 채워져 있는 primary clustring 문제에 취약하다고 합니다. 예컨대 아래 그림처럼 52~56까지 데이터가 저장돼 있고 임의의 키의 최초 해시값이 52라면 탐사를 네 번 수행하고 나서야 원하는 위치를 찾을 수 있습니다. 모두 빈 버킷이었다면 단 한 번의 해시만으로도 저장할 수 있었을 텐데 말이죠.
제곱 탐사(Quadratic probing)은 고정 폭으로 이동하는 선형 탐사와 달리 그 폭이 제곱수로 늘어난다는 특징이 있습니다. 예컨대 임의의 키값에 해당하는 데이터에 액세스할 때 충돌이 일어나면 $1^2$칸을 옮깁니다. 여기에서도 충돌이 일어나면 이번엔 $2^2$칸, 그 다음엔 $3^2$칸 옮기는 식입니다.
하지만 제곱탐사는 여러 개의 서로 다른 키들이 동일한 초기 해시값(아래에서 initial probe)을 갖는 secondary clustering에 취약하다고 합니다. 초기 해시값이 같으면 다음 탐사 위치 또한 동일하기 때문에 효율성이 떨어집니다. 예컨대 아래 그림에서 초기 해시값이 7인 데이터를 삽입해야 할 경우 선형 탐사 기법보다 성큼성큼 이동하더라도 탐사를 네 번 수행하고 나서야 비로소 데이터를 저장할 수 있습니다.
이중해싱(double hashing)은 탐사할 해시값의 규칙성을 없애버려서 clustering을 방지하는 기법입니다. 2개의 해시함수를 준비해서 하나는 최초의 해시값을 얻을 때, 또 다른 하나는 해시충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용합니다. 이렇게 되면 최초 해시값이 같더라도 탐사 이동폭이 달라지고, 탐사 이동폭이 같더라도 최초 해시값이 달라져 primary, secondary clustering을 모두 완화할 수 있습니다.
- 해시값을 반환해주는 $h_1$을 ‘3으로 나눈 나머지’, 탐사 이동폭을 결정해주는 $h_2$를 ‘5로 나눈 나머지’라고 둡시다. 예컨대 키가 3, 6인 데이터의 최초 해시값은 모두 0이 됩니다. 하지만 키가 3인 데이터의 탐사이동폭은 3, 6인 데이터의 이동폭은 1로 달라집니다. 반대로 키가 6, 11인 데이터의 탐사이동폭은 모두 1이 됩니다. 하지만 키가 6인 데이터의 최초 해시값은 0, 11은 2로 달라집니다.
- 단 제수(위 예시에서 3, 5)는 서로소(relatively prime, 공약수가 1뿐)이어야 원하는 효과를 볼 수 있습니다.
계산복잡성
open addressing은 chaining과 달리 해시테이블의 크기($m$)가 고정돼 있으므로 $n$개 데이터를 모두 저장하려는 경우 Load Factor $α=n/m$는 1과 같거나 작다고 가정합니다. 다시 말해 open addressing은 해시테이블에 데이터가 꽉 차지 않는다는 걸 전제로 한다는 이야기입니다. 아울러 open addressing에 적용된 해시함수는 키들을 모든 버킷에 균등하게 할당한다고 가정하고 계산복잡성을 분석합니다.
open addressing 탐색의 계산복잡성은 탐사(probing) 횟수에 비례합니다. 따라서 탐색 계산복잡성을 따질 때 핵심은 ‘탐사 횟수의 기대값’입니다. successful search와 unsuccessful search의 탐사횟수 기대값은 각각 다음과 같다고 합니다.
\[\begin{align*}
successful\quad search\quad &:\quad \frac { 1 }{ \alpha } \ln { \frac { 1 }{ 1-\alpha } } \\ unsuccessful\quad search\quad &:\quad \frac { 1 }{ \alpha }
\end{align*}\]
해시테이블에 데이터가 반만 차 있다($α=0.5$)고 가정하면 successful search와 unsuccessful search의 탐사횟수 기대값은 각각 1.387, 2가 됩니다. 다시 말해 최초로 해시값을 만드는 1회를 뺀 나머지, 즉 한번 정도만 추가 탐사하면 원하는 데이터를 대체로 찾을 수 있다는 얘기입니다. 반대로 $α=0.8$이라면 탐사횟수 기대값은 8.047과 5로 치솟게 됩니다.
요컨대 open addressing 탐색 연산의 계산복잡성은 $α$에 크게 영향을 받는 구조입니다. 따라서 해시테이블에 데이터가 어느 정도 차게 되면 해시테이블 크기 $m$을 적절하게 늘려주고 처음부터 다시 해싱을 하는 것이 좋다고 합니다. 삭제와 삽입 연산 역시 탐사 횟수가 중요하기 때문에 해시테이블 크기에 신경을 써주어야 합니다.
해시함수
이번엔 해시함수로 해시충돌을 완화하는 방법을 살펴보겠습니다. 해시테이블의 크기가 $m$이라면, 좋은 해시함수는 임의의 키값을 임의의 해시값에 매핑할 확률이 $1/m$이 될 겁니다. 다시 말해 특정 값에 치우치지 않고 해시값을 고르게 만들어내는 해시함수가 좋은 해시함수라는 이야기입니다.
division method
나눗셈법은 간단하면서도 빠른 연산이 가능한 해시함수입니다. 숫자로 된 키를 해시테이블 크기 $m$으로 나눈 나머지를 해시값으로 반환합니다. $m$은, 대개 소수(prime number)를 쓰며 특히 2의 제곱수와 거리가 먼 소수를 사용하는 것이 좋다고 합니다. 다시 말해 해시함수 특성 때문에 해시테이블 크기가 정해진다는 단점이 있다는 이야기입니다.
multiplication method
숫자로 된 키가 $k$이고 $A$는 0과 1 사이의 실수일 때 곱셈법은 다음과 같이 정의됩니다. $m$이 얼마가 되든 크게 중요하지는 않으며 보통 2의 제곱수로 정한다고 합니다. 나눗셈법보다는 다소 느리다고 합니다. 2진수 연산에 최적화한 컴퓨터 구조를 고려한 해시함수라고 합니다.
\[h\left( k \right) =\left( kA\quad mod\quad 1 \right) \times m\]
universal hasing
다수의 해시함수를 만들고, 이 해시함수의 집합 $H$에서 무작위로 해시함수를 선택해 해시값을 만드는 기법입니다. $H$에서 무작위로 뽑은 해시함수가 주어졌을 때 임의의 키값을 임의의 해시값에 매핑할 확률을 $1/m$로 만드려는 것이 목적입니다. 다음과 같은 특정 조건의 해시함수 집합 $H$는 $1/m$으로 만드는 게 가능하다고 수학적으로 증명됐습니다.
- 해시테이블의 크기 $m$를 소수로 정한다.
- 키값을 다음과 같이 $r+1$개로 쪼갠다 : $k_0$, $k_1$,…, $k_r$
- 0부터 $m-1$ 사이의 정수 가운데 하나를 무작위로 뽑는다. 분리된 키값의 개수($r+1$)만큼 반복해서 뽑는다. 이를 $a=[a_0, a_1,…,a_r]$로 둔다. 따라서 $a$의 경우의 수는 모두 $m^{r+1}$가지이다.
- 해시함수를 다음과 같이 정의한다 : $h_a(x)=Σ_{i=0}^r{(a_ik_i\mod\ m)}$
- $a$가 $m^{r+1}$가지이므로 해시함수의 집합 $H$의 요소 수 또한 $m^{r+1}$개이다.
위와 같은 조건에서는 키가 동일하더라도 $a$가 얼마든지 랜덤하게 달라질 수 있고, 이에 해당하는 해시함수 $h_a$ 또한 상이해지기 때문에 $H$는 유니버설 함수가 됩니다.
이번 글에서는 해싱(hashing)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아, 그리고 스택오버플로우와 고니 님의 블로그를 참고해 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concepts
해시함수(hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 합니다.
해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one 대응)하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생하게 됩니다. 아래 그림은 이름-전화번호부를 매핑하기 위한 해시함수를 개념적으로 나타냈습니다. 예시의 해시함수는 ‘John Smith’와 ‘Sandra Dee’를 모두 ‘02’로 매핑해 해시충돌을 일으키고 있습니다.
##해시테이블의 장점
해시충돌이 발생할 가능성이 있음에도 해시테이블을 쓰는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리하기 위해서입니다. 예컨대 해시함수로 하드디스크나 클라우드에 존재하는 무한에 가까운 데이터(키)들을 유한한 개수의 해시값으로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있게 됩니다.
색인(index)에 해시값을 사용함으로써 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행할 수 있습니다. 위 그림의 경우 해시함수에 ‘Lisa Smith’를 입력하면 01이라는 색인이 생성됩니다.
해시함수는 언제나 동일한 해시값을 리턴하고, 해당 색인만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근할 수 있으며, 색인은 계산이 간단한 함수(상수시간)로 작동하기 때문에 매우 효율적입니다. 다시 말해 해시는 데이터 액세스(삽입, 삭제, 탐색)시 계산복잡성을 $O(1)$을 지향합니다.
해시테이블을 다른 자료구조와 비교해보겠습니다. 이진탐색트리와 그 변형의 경우 메모리를 효율적으로 사용하는 편이지만 데이터 탐색에 소요되는 계산복잡성은 $O(\log{n})$입니다. 배열(array)의 경우 데이터 탐색에 따른 계산복잡성은 $O(1)$이지만, 메모리를 미리 할당해 둬야 하기 때문에 공간 효율적이라고 말하기 어렵습니다.
해시는 보안 분야에서도 널리 사용된다고 합니다. 키와 해시값 사이에 직접적인 연관이 없기 때문에 해시값만 가지고는 키를 온전히 복원하기 어렵기 때문입니다. 아울러 해시함수는 길이가 서로 다른 입력데이터에 대해 일정한 길이의 출력을 만들 수 있어서 ‘데이터 축약’ 기능도 수행할 수 있습니다.
다만 현재까지 개발된 거의 모든 해시함수는 해시충돌을 일으키는 것으로 확인됐다고 합니다. 물론 해시충돌 자체를 줄이는 것도 의미가 있겠습니다만, 중요한 것은 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 하는 것입니다. 극단적으로 위 그림에서 모든 키가 02라는 동일한 해시값으로 매핑이 될 경우 데이터를 액세스할 때 비효율성이 커지고, 보안이 취약(서로 다른 키인데도 동일한 해시값)해져 굳이 해시를 도입해 데이터를 관리할 이유가 없어집니다.
해시테이블
해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조를 해시테이블(hash table)이라고 합니다. 이 때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot)이라고 합니다. 해시테이블의 기본 연산은 삽입, 삭제, 탐색(search)입니다. 다음 그림과 같습니다.
위 예시 그림 각 버킷에는 데이터가 다음과 같이 저장됩니다.
| Index(Hash Value) | Data |
|---|---|
| 01 | (Lisa Smith, 521-8976) |
| 02 | (John Smith, 521-1234) |
| … | … |
키의 전체 개수와 동일한 크기의 버킷을 가진 해시테이블을 Direct-address table이라고 합니다. 다음 그림과 같습니다.
Direct-address table의 장점은 키 개수와 해시테이블 크기가 동일하기 때문에 해시충돌 문제가 발생하지 않는다는 겁니다. 하지만 전체 키(unverse of key)가 실제 사용하는 키(actucal key)보다 훨씬 많은 경우 사용하지 않는 키들을 위한 공간까지 마련해야 하는 탓에 메모리 효율성이 크게 떨어집니다. 위 그림처럼 1, 9, 4, 0, 7, 6을 위한 버킷은 굳이 만들어놓을 이유가 없습니다.
보통의 경우 Direct-address table보다는 “해시테이블 크기($m$)가 실제 사용하는 키 개수($n$)보다 적은 해시테이블”을 운용합니다. 다뤄야할 데이터가 정말 많고, 메모리 등 리소스 문제도 생기기 때문입니다. 이 때 $n/m$을 load factor($α$)라고 합니다. 해시테이블의 한 버킷에 평균 몇 개의 키가 매핑되는가를 나타내는 지표입니다. Direct-address table의 load factor는 1 이하이며, 1보다 큰 경우 해시충돌 문제가 발생합니다.
해시충돌 문제를 해결하기 위해 다양한 기법들이 고안됐습니다. chining은 해시테이블의 크기를 유연하게 만들고, open addressing은 해시테이블 크기는 고정시키되 저장해 둘 위치를 잘 찾는 데 관심을 둔 구조입니다. 이뿐 아니라 해시함수를 개선하는 접근도 있습니다. 차례대로 살펴보겠습니다.
chaining
해시충돌 문제를 해결하기 위한 간단한 아이디어 가운데 하나는 한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써 모든 자료를 해시테이블에 담는 것입니다. 해당 버킷에 데이터가 이미 있다면 체인처럼 노드를 추가하여 다음 노드를 가리키는 방식으로 구현(연결리스트)하기 때문에 체인이라는 말이 붙은 것 같습니다. 유연하다는 장점을 가지나 메모리 문제를 야기할 수 있습니다. 아래 그림과 같습니다.
위 예시 그림의 해시함수는 ‘John Smith’와 ‘Sandra Dee’를 같은 해시값(152)으로 매핑하고 있습니다. 이 경우 해당 해시값에 대응하는 동일한 버킷에 두 개 데이터를 저장해 둡니다. 데이터를 위 그림처럼 연결리스트로 저장해 둘 경우 최근 데이터는 연결리스트의 head에 추가합니다(이 경우 $O(1)$, tail에 저장할 경우 $O(n)$이 됨, 자세한 내용은 이곳 참고)
삽입, 탐색, 삭제 연산과 계산복잡성
chaining 방식의 계산복잡성을 따져보겠습니다. 삽입(insertion), 탐색(search), 삭제(delete) 세 가지가 있습니다. 본격적인 분석에 앞서 가정을 하나 하겠습니다. 해시테이블의 크기가 $m$, 실제 사용하는 키 개수가 $n$, 해시함수가 키들을 모든 버킷에 균등하게 할당한다고 가정하면, 버킷 하나당 $n/m=α$개의 키들이 존재할 것입니다. 예컨대 위 그림 예시에서 2560개의 키에 해당하는 데이터를 저장한다면 버킷 하나당 10개 데이터가 있다는 얘기입니다.
삽입의 계산복잡성입니다. 예컨대 위 예시그림의 해시함수가 254로 매핑하는 ‘Mark Zuckerberg’의 전화번호를 새로 추가한다고 칩시다. ‘Mark Zuckerberg’라는 키를 해시값 254로 매핑하는 데 $O(1)$이 듭니다. 해당 해시값에 해당하는 연결리스트의 head에 이를 추가하는 데 $O(1)$이 듭니다. 따라서 삽입의 계산복잡성은 둘을 합친 $O(1)$입니다.
이번엔 탐색을 살펴보겠습니다. 두 가지로 나눠서 생각해 보겠습니다.
쿼리 키값에 해당하는 데이터가 해시테이블에 존재하지 않는 경우(unsuccessful search)입니다. 예컨대 위 예시그림의 해시함수가 152로 매핑하는 ‘Steve Jobs’의 전화번호를 탐색한다고 가정해 봅시다. 이 경우 키를 해시값으로 바꾸고, 해당 해시값에 해당하는 버킷의 요소들 $α$개를 모두 탐색해봐야 존재하지 않는다는 사실을 알 수 있습니다. 따라서 unsuccessful search의 계산복잡성은 $O(1+α)$가 됩니다.
이번엔 쿼리 키값에 해당하는 데이터가 해시테이블에 존재하는 경우(successful search)입니다. 예컨대 ‘Sandra Dee’의 전화번호를 위와 같은 해시테이블에서 탐색한다고 가정해 봅시다. 이를 위해선 ‘Sandra Dee’를 해시값(152)으로 바꾸고 버킷 요소들 가운데 ‘Sandra Dee’에 해당하는 데이터가 있는지 탐색해봐야 할 겁니다.
Big O notation의 계산복잡성을 따져보기 위해선 최악의 경우를 고려해야 합니다. 해당 버킷의 tail에 값이 있는 경우일 겁니다. 데이터가 해시테이블에 존재한다고 가정했으므로 버킷 내 $α$개 요소 가운데 반드시 찾고자 하는 값이 존재합니다. $α-1$개를 비교했는데도 원하는 값을 찾지 못했다면 tail값은 따져볼 필요도 없이 찾고자 하는 값이 됩니다.
그런데 버킷의 요소들 평균이 $α$개일 때 successful search는, 요소가 $α-1$개인 버킷을 탐색했는데 찾는 값이 없어서(unsuccessful search), 해당 버킷에 쿼리에 해당하는 데이터를 삽입하여 결과적으로 해당 버킷의 요소 수를 $α$개로 만드는 계산량과 동일합니다. unsuccessful search의 계산복잡성은 $O(1+α)$이므로, successful search의 계산복잡성 또한 이와 같은 $O(1+α)$가 됩니다.
삭제의 계산복잡성은 탐색과 본질적으로 비슷합니다. 우선 쿼리 키값을 해시값으로 매핑하고($O(1)$), 해당 버킷 내에 키값에 해당하는 데이터가 있는지 탐색($O(α)$)해야 하기 때문입니다. 물론 탐색 연산과 비교해 삭제에 드는 계산도 추가적으로 필요하나, 연결리스트로 해시테이블을 구현할 경우 삭제 연산의 계산복잡성은 $O(1)$이므로 무시할 만한 수준입니다.
chaining에서 삽입을 제외한, 탐색/삭제의 계산복잡성은 버킷당 요소 개수의 평균 $α$가 좌지우지하는 구조입니다. 최악의 경우 한 버킷에 모든 데이터가 들어있어 $O(n)$이 될 수 있습니다. 하지만 데이터의 개수가 해시테이블 크기의 두 세배쯤($α$가 2~3)만 되어도 탐색, 삭제는 $O(1)$이 됩니다.
open addressing
open addressing은 chaining과 달리 한 버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시테이블입니다. 해시함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용한다는 취지에서 open addressing이라는 이름이 붙은 것 같습니다. 메모리 문제가 발생하지 않으나 해시충돌이 생길 수 있습니다.
예컨대 해시함수를 ‘키값을 7로 나눈 나머지’로 정의했다고 칩시다. 그리고 나서 키 50, 700, 76, 85, 92, 73, 101순으로 데이터를 저장한다고 가정해 봅시다. 다음 그림과 같습니다.
위 예시에서 주목할 부분은 85부터입니다. 85를 7로 나눈 나머지는 1입니다. 그런데 해시값 1에 해당하는 버킷에 이미 50이 있으므로, 다음 버킷(2)에 저장해 둡니다. 92를 7로 나눈 나머지 역시 1입니다. 그런데 해시값 1에 해당하는 버킷에 이미 50이 있고, 그 다음 해시값 2 버킷에 85가 있으므로, 92를 3번 버킷에 저장합니다. 73, 101 역시 자신의 버킷에는 이미 주인이 있으므로 빈 버킷에 할당합니다.
삭제, 삽입, 탐색
해시함수가 ‘키값을 8로 나눈 나머지’이고 10, 18, 26 순으로 해시테이블에 삽입한다고 가정해 보겠습니다. 세 숫자 가운데 첫번째 입력값 10을 제외한 18, 26은 원래 버킷(2) 말고 각각 다음(3), 다음다음(4) 버킷에 저장하는 것이 open addressing의 방식입니다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 10 | 18 | 26 |
위 표에서 18을 삭제해 보겠습니다. 18의 해시값은 2인데 여기엔 10이 저장돼 있으므로 스킵하고, 그 다음 버킷(3)을 탐색해 봅니다. 18이 여기에 있군요. 지웁니다. 다음과 같습니다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 10 | 26 |
위 표에서 26을 탐색해 보겠습니다. 26의 해시값은 2인데 여기엔 10이 저장돼 있으므로 스킵하고, 그 다음 버킷(3)을 탐색해 봅니다. 그런데 비어 있습니다. 별도로 조치하지 않으면 알고리즘은 ‘2번 해시값 1칸 옆인 3에 저장된 데이터가 없구나, 해시충돌이 발생한 적이 없다는 얘기네, 탐색을 끝내야 겠다’고 판단할 수 있습니다.
이를 해결하기 위해 삭제 연산 때 아래처럼 별도로 표시를 해둡니다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 10 | DEL | 26 |
probing
open addressing은 그 구조상 해시충돌 문제가 발생할 수 있습니다. 앞선 예시에서 살펴봤듯 특정 해시값에 키가 몰리게 되면 open addressing의 효율성이 크게 떨어집니다. 해시충돌은 탐사(probing) 방식으로 해결할 수 있습니다. 탐사란 삽입, 삭제, 탐색을 수행하기 위해 해시테이블 내 새로운 주소(해시값)를 찾는 과정입니다.
선형 탐사(Linear probing)는 가장 간단한 방식입니다. 앞선 예시에 해당합니다. 최초 해시값에 해당하는 버킷에 다른 데이터가 저장돼 있으면 해당 해시값에서 고정 폭(예컨대 1칸)을 옮겨 다음 해시값에 해당하는 버킷에 액세스(삽입, 삭제, 탐색)합니다. 여기에 데이터가 있으면 고정폭으로 또 옮겨 액세스합니다.
그런데 탐사 이동폭이 고정돼 있는 선형탐사는 특정 해시값 주변 버킷이 모두 채워져 있는 primary clustring 문제에 취약하다고 합니다. 예컨대 아래 그림처럼 52~56까지 데이터가 저장돼 있고 임의의 키의 최초 해시값이 52라면 탐사를 네 번 수행하고 나서야 원하는 위치를 찾을 수 있습니다. 모두 빈 버킷이었다면 단 한 번의 해시만으로도 저장할 수 있었을 텐데 말이죠.
제곱 탐사(Quadratic probing)은 고정 폭으로 이동하는 선형 탐사와 달리 그 폭이 제곱수로 늘어난다는 특징이 있습니다. 예컨대 임의의 키값에 해당하는 데이터에 액세스할 때 충돌이 일어나면 $1^2$칸을 옮깁니다. 여기에서도 충돌이 일어나면 이번엔 $2^2$칸, 그 다음엔 $3^2$칸 옮기는 식입니다.
하지만 제곱탐사는 여러 개의 서로 다른 키들이 동일한 초기 해시값(아래에서 initial probe)을 갖는 secondary clustering에 취약하다고 합니다. 초기 해시값이 같으면 다음 탐사 위치 또한 동일하기 때문에 효율성이 떨어집니다. 예컨대 아래 그림에서 초기 해시값이 7인 데이터를 삽입해야 할 경우 선형 탐사 기법보다 성큼성큼 이동하더라도 탐사를 네 번 수행하고 나서야 비로소 데이터를 저장할 수 있습니다.
이중해싱(double hashing)은 탐사할 해시값의 규칙성을 없애버려서 clustering을 방지하는 기법입니다. 2개의 해시함수를 준비해서 하나는 최초의 해시값을 얻을 때, 또 다른 하나는 해시충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용합니다. 이렇게 되면 최초 해시값이 같더라도 탐사 이동폭이 달라지고, 탐사 이동폭이 같더라도 최초 해시값이 달라져 primary, secondary clustering을 모두 완화할 수 있습니다.
- 해시값을 반환해주는 $h_1$을 ‘3으로 나눈 나머지’, 탐사 이동폭을 결정해주는 $h_2$를 ‘5로 나눈 나머지’라고 둡시다. 예컨대 키가 3, 6인 데이터의 최초 해시값은 모두 0이 됩니다. 하지만 키가 3인 데이터의 탐사이동폭은 3, 6인 데이터의 이동폭은 1로 달라집니다. 반대로 키가 6, 11인 데이터의 탐사이동폭은 모두 1이 됩니다. 하지만 키가 6인 데이터의 최초 해시값은 0, 11은 2로 달라집니다.
- 단 제수(위 예시에서 3, 5)는 서로소(relatively prime, 공약수가 1뿐)이어야 원하는 효과를 볼 수 있습니다.
계산복잡성
open addressing은 chaining과 달리 해시테이블의 크기($m$)가 고정돼 있으므로 $n$개 데이터를 모두 저장하려는 경우 Load Factor $α=n/m$는 1과 같거나 작다고 가정합니다. 다시 말해 open addressing은 해시테이블에 데이터가 꽉 차지 않는다는 걸 전제로 한다는 이야기입니다. 아울러 open addressing에 적용된 해시함수는 키들을 모든 버킷에 균등하게 할당한다고 가정하고 계산복잡성을 분석합니다.
open addressing 탐색의 계산복잡성은 탐사(probing) 횟수에 비례합니다. 따라서 탐색 계산복잡성을 따질 때 핵심은 ‘탐사 횟수의 기대값’입니다. successful search와 unsuccessful search의 탐사횟수 기대값은 각각 다음과 같다고 합니다.
\[\begin{align*} successful\quad search\quad &:\quad \frac { 1 }{ \alpha } \ln { \frac { 1 }{ 1-\alpha } } \\ unsuccessful\quad search\quad &:\quad \frac { 1 }{ \alpha } \end{align*}\]해시테이블에 데이터가 반만 차 있다($α=0.5$)고 가정하면 successful search와 unsuccessful search의 탐사횟수 기대값은 각각 1.387, 2가 됩니다. 다시 말해 최초로 해시값을 만드는 1회를 뺀 나머지, 즉 한번 정도만 추가 탐사하면 원하는 데이터를 대체로 찾을 수 있다는 얘기입니다. 반대로 $α=0.8$이라면 탐사횟수 기대값은 8.047과 5로 치솟게 됩니다.
요컨대 open addressing 탐색 연산의 계산복잡성은 $α$에 크게 영향을 받는 구조입니다. 따라서 해시테이블에 데이터가 어느 정도 차게 되면 해시테이블 크기 $m$을 적절하게 늘려주고 처음부터 다시 해싱을 하는 것이 좋다고 합니다. 삭제와 삽입 연산 역시 탐사 횟수가 중요하기 때문에 해시테이블 크기에 신경을 써주어야 합니다.
해시함수
이번엔 해시함수로 해시충돌을 완화하는 방법을 살펴보겠습니다. 해시테이블의 크기가 $m$이라면, 좋은 해시함수는 임의의 키값을 임의의 해시값에 매핑할 확률이 $1/m$이 될 겁니다. 다시 말해 특정 값에 치우치지 않고 해시값을 고르게 만들어내는 해시함수가 좋은 해시함수라는 이야기입니다.
division method
나눗셈법은 간단하면서도 빠른 연산이 가능한 해시함수입니다. 숫자로 된 키를 해시테이블 크기 $m$으로 나눈 나머지를 해시값으로 반환합니다. $m$은, 대개 소수(prime number)를 쓰며 특히 2의 제곱수와 거리가 먼 소수를 사용하는 것이 좋다고 합니다. 다시 말해 해시함수 특성 때문에 해시테이블 크기가 정해진다는 단점이 있다는 이야기입니다.
multiplication method
숫자로 된 키가 $k$이고 $A$는 0과 1 사이의 실수일 때 곱셈법은 다음과 같이 정의됩니다. $m$이 얼마가 되든 크게 중요하지는 않으며 보통 2의 제곱수로 정한다고 합니다. 나눗셈법보다는 다소 느리다고 합니다. 2진수 연산에 최적화한 컴퓨터 구조를 고려한 해시함수라고 합니다.
\[h\left( k \right) =\left( kA\quad mod\quad 1 \right) \times m\]universal hasing
다수의 해시함수를 만들고, 이 해시함수의 집합 $H$에서 무작위로 해시함수를 선택해 해시값을 만드는 기법입니다. $H$에서 무작위로 뽑은 해시함수가 주어졌을 때 임의의 키값을 임의의 해시값에 매핑할 확률을 $1/m$로 만드려는 것이 목적입니다. 다음과 같은 특정 조건의 해시함수 집합 $H$는 $1/m$으로 만드는 게 가능하다고 수학적으로 증명됐습니다.
- 해시테이블의 크기 $m$를 소수로 정한다.
- 키값을 다음과 같이 $r+1$개로 쪼갠다 : $k_0$, $k_1$,…, $k_r$
- 0부터 $m-1$ 사이의 정수 가운데 하나를 무작위로 뽑는다. 분리된 키값의 개수($r+1$)만큼 반복해서 뽑는다. 이를 $a=[a_0, a_1,…,a_r]$로 둔다. 따라서 $a$의 경우의 수는 모두 $m^{r+1}$가지이다.
- 해시함수를 다음과 같이 정의한다 : $h_a(x)=Σ_{i=0}^r{(a_ik_i\mod\ m)}$
- $a$가 $m^{r+1}$가지이므로 해시함수의 집합 $H$의 요소 수 또한 $m^{r+1}$개이다.
위와 같은 조건에서는 키가 동일하더라도 $a$가 얼마든지 랜덤하게 달라질 수 있고, 이에 해당하는 해시함수 $h_a$ 또한 상이해지기 때문에 $H$는 유니버설 함수가 됩니다.
Comments