해싱, 해시함수, 해시테이블

1. 해싱, 해시함수, 해시테이블
1.1 해시함수(hash function)란?
: 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 한다.

해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one 대응)하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생하게 된다. 아래 그림은 이름-전화번호부를 매핑하기 위한 해시함수를 개념적으로 나타냈다. 예시의 해시함수는 ‘John Smith’와 ‘Sandra Dee’를 모두 ‘02’로 매핑해 해시충돌을 일으키고 있다.

1.2 해시테이블의 장점
: 해시충돌이 발생할 가능성이 있음에도 해시테이블을 쓰는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리하기 위해서다. 예컨대 해시함수로 하드디스크나 클라우드에 존재하는 무한에 가까운 데이터(키)들을 유한한 개수의 해시값으로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있게 된다.

색인(index)에 해시값을 사용함으로써 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행할 수 있다. 위 그림의 경우 해시함수에 ‘Lisa Smith’를 입력하면 02라는 색인이 생성된다.

해시함수는 언제나 동일한 해시값을 리턴하고, 해당 색인만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근할 수 있으며, 색인은 계산이 간단한 함수(상수시간)로 작동하기 때문에 매우 효율적이다. 다시 말해 해시는 데이터 액세스(삽입, 삭제, 탐색)시 계산복잡성을 O(1)O(1)을 지향한다.

해시테이블을 다른 자료구조와 비교해보자. 이진탐색트리와 그 변형의 경우 메모리를 효율적으로 사용하는 편이지만 데이터 탐색에 소요되는 계산복잡성은 O(nlogn)O(nlog⁡n)이다. 배열(array)의 경우 데이터 탐색에 따른 계산복잡성은 O(1)O(1)이지만, 메모리를 미리 할당해 둬야 하기 때문에 공간 효율적이라고 말하기 어렵다.

해시는 보안 분야에서도 널리 사용된다고 한다. 키와 해시값 사이에 직접적인 연관이 없기 때문에 해시값만 가지고는 키를 온전히 복원하기 어렵기 때문이다. 아울러 해시함수는 길이가 서로 다른 입력데이터에 대해 일정한 길이의 출력을 만들 수 있어서 ‘데이터 축약’ 기능도 수행할 수 있다.

다만 현재까지 개발된 거의 모든 해시함수는 해시충돌을 일으키는 것으로 확인됐다고 한다. 물론 해시충돌 자체를 줄이는 것도 의미가 있겠지만, 중요한 것은 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 하는 것이다. 극단적으로 위 그림에서 모든 키가 02라는 동일한 해시값으로 매핑이 될 경우 데이터를 액세스할 때 비효율성이 커지고, 보안이 취약(서로 다른 키인데도 동일한 해시값)해져 굳이 해시를 도입해 데이터를 관리할 이유가 없어진다.

1.3 해시테이블
: 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조를 해시테이블(hash table)이라고 한다. 이 때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot)이라고 한다. 해시테이블의 기본 연산은 삽입, 삭제, 탐색(search)이다. 다음 그림과 같다.

위 예시 그림 각 버킷에는 데이터가 다음과 같이 저장된다.

키의 전체 개수와 동일한 크기의 버킷을 가진 해시테이블을 Direct-address table이라고 한다. 다음 그림과 같다.

Direct-address table의 장점은 키 개수와 해시테이블 크기가 동일하기 때문에 해시충돌 문제가 발생하지 않는다는 것이다. 하지만 실제 사용하는 키(actucal key)보다 전체 키(unverse of key)보다 훨씬 많은 경우 사용하지 않는 키들을 위한 공간까지 마련해야 하는 탓에 메모리 효율성이 크게 떨어진다. 위 그림처럼 1, 9, 4, 0, 7, 6을 위한 버킷은 굳이 만들어놓을 이유가 없다.

보통의 경우 Direct-address table보다는 해시테이블 크기(mm)가 실제 사용하는 키 개수(nn)보다 적은 해시테이블을 운용한다. 다뤄야할 데이터가 정말 많고, 메모리 등 리소스 문제도 생기기 때문이다. 이 때 n/mn/m을 load factor(αα)라고 한다. 해시테이블의 한 버킷에 평균 몇 개의 키가 매핑되는가를 나타내는 지표이다. Direct-address table의 load factor는 1 이하이며, 1보다 큰 경우 해시충돌 문제가 발생한다.

해시충돌 문제를 해결하기 위해 다양한 기법들이 고안됐다. chining은 해시테이블의 크기를 유연하게 만들고, open addressing은 해시테이블 크기는 고정시키되 저장해 둘 위치를 잘 찾는 데 관심을 둔 구조이다. 이뿐 아니라 해시함수를 개선하는 접근도 있다. 차례대로 살펴보자.

1.3.1 chaining
: 해시충돌 문제를 해결하기 위한 간단한 아이디어 가운데 하나는 한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써 모든 자료를 해시테이블에 담는 것이다. 해당 버킷에 데이터가 이미 있다면 체인처럼 노드를 추가하여 다음 노드를 가리키는 방식으로 구현(연결리스트)하기 때문에 체인이라는 말이 붙은 것 같다. 유연하다는 장점을 가지나 메모리 문제가 발생할 수 있다. 아래 그림과 같다.

위 예시 그림의 해시함수는 ‘John Smith’와 ‘Sandra Dee’를 같은 해시값(152)으로 매핑하고 있다. 이 경우 해당 해시값에 대응하는 동일한 버킷에 두 개 데이터를 저장해 둔다. 데이터를 위 그림처럼 연결리스트로 저장해 둘 경우 최근 데이터는 연결리스트의 head에 추가한다.

- 삽입, 탐색, 삭제 연산과 계산복잡성
: chaining 방식의 계산복잡성을 따져보자. 삽입(insertion), 탐색(search), 삭제(delete) 세 가지가 있다. 본격적인 분석에 앞서 가정을 하나 해보자. 해시테이블의 크기가 mm, 실제 사용하는 키 개수가 nn, 해시함수가 키들을 모든 버킷에 균등하게 할당한다고 가정하면, 버킷 하나당 n/m=αn/m=α개의 키들이 존재할 것이다. 위 그림 예시에서 2560개의 키에 해당하는 데이터를 저장한다면 버킷 하나당 10개 데이터가 있다는 얘기다.

삽입의 계산복잡성이다. 위 예시그림의 해시함수가 254로 매핑하는 ‘Mark Zuckerberg’의 전화번호를 새로 추가한다고 가정한다. ‘Mark Zuckerberg’라는 키를 해시값 254로 매핑하는 데 O(1)O(1)이 걸린다. 해당 해시값에 해당하는 연결리스트의 head에 이를 추가하는 데 O(1)O(1)이 걸린다. 따라서 삽입의 계산복잡성은 둘을 합친 O(1)O(1)이다.

이번엔 탐색을 살펴보자. 두 가지로 나눠서 생각해 보자.

쿼리 키값에 해당하는 데이터가 해시테이블에 존재하지 않는 경우(unsuccessful search)이다. 위 예시그림의 해시함수가 152로 매핑하는 ‘Steve Jobs’의 전화번호를 탐색한다고 가정하자. 이 경우 키를 해시값으로 바꾸고, 해당 해시값에 해당하는 버킷의 요소들 αα개를 모두 탐색해봐야 존재하지 않는다는 사실을 알 수 있다. 따라서 unsuccessful search의 계산복잡성은 O(1+α)O(1+α)가 된다.

이번엔 쿼리 키값에 해당하는 데이터가 해시테이블에 존재하는 경우(successful search)이다. 예컨대 ‘Sandra Dee’의 전화번호를 위와 같은 해시테이블에서 탐색한다고 가정해 본다. 이를 위해선 ‘Sandra Dee’를 해시값(152)으로 바꾸고 버킷 요소들 가운데 ‘Sandra Dee’에 해당하는 데이터가 있는지 탐색해봐야 한다.

Big O notation의 계산복잡성을 따져보기 위해선 최악의 경우를 고려해야 한다. 해당 버킷의 tail에 값이 있는 경우다. 데이터가 해시테이블에 존재한다고 가정했으므로 버킷 내 αα개 요소 가운데 반드시 찾고자 하는 값이 존재한다. α−1α−1개를 비교했는데도 원하는 값을 찾지 못했다면 tail값은 따져볼 필요도 없이 찾고자 하는 값이 된다.

그런데 버킷의 요소들 평균이 αα개일 때 successful search는, 요소가 α−1α−1개인 버킷을 탐색했는데 찾는 값이 없어서(unsuccessful search), 해당 버킷에 쿼리에 해당하는 데이터를 삽입하여 결과적으로 해당 버킷의 요소 수를 αα개로 만드는 계산량과 동일하다. unsuccessful search의 계산복잡성은 O(1+α)O(1+α)이므로, successful search의 계산복잡성 또한 이와 같은 O(1+α)O(1+α)가 된다.

삭제의 계산복잡성은 탐색과 본질적으로 비슷하다. 우선 쿼리 키값을 해시값으로 매핑하고(O(1)O(1)), 해당 버킷 내에 키값에 해당하는 데이터가 있는지 탐색(O(α)O(α))해야 하기 때문이다. 물론 탐색 연산과 비교해 삭제에 드는 계산도 추가적으로 필요하나, 연결리스트로 해시테이블을 구현할 경우 삭제 연산의 계산복잡성은 O(1)O(1)이므로 무시할 만한 수준이다.

chaining에서 삽입을 제외한, 탐색/삭제의 계산복잡성은 버킷당 요소 개수의 평균 αα가 좌지우지하는 구조다. 최악의 경우 한 버킷에 모든 데이터가 들어있어 O(n)O(n)이 될 수 있다. 하지만 데이터의 개수가 해시테이블 크기의 두 세배쯤(αα가 2~3)만 되어도 탐색, 삭제는 O(1)O(1)이 된다.

1.3.2 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의 방식이다.

위 표에서 18을 삭제해보면, 18의 해시값은 2인데 여기엔 10이 저장돼 있으므로 스킵하고, 그 다음 버킷(3)을 탐색해본다. 18을 찾으면, 지운다. 다음과 같다.

위 표에서 26을 탐색해보자. 26의 해시값은 2인데 여기엔 10이 저장돼 있으므로 스킵하고, 그 다음 버킷(3)을 탐색해 본다. 그런데 비어있다. 별도로 조치하지 않으면 알고리즘은 ‘2번 해시값 1칸 옆인 3에 저장된 데이터가 없구나, 해시충돌이 발생한 적이 없다는 얘기네, 탐색을 끝내야 겠다’고 판단할 수 있다.

이를 해결하기 위해 삭제 연산 때 아래처럼 별도로 표시를 해둔다.

1.3.3 probing
: open addressing은 그 구조상 해시충돌 문제가 발생할 수 있다. 앞선 예시에서 살펴봤듯 특정 해시값에 키가 몰리게 되면 open addressing의 효율성이 크게 떨어진다. 해시충돌은 탐사(probing) 방식으로 해결할 수 있다. 탐사란 삽입, 삭제, 탐색을 수행하기 위해 해시테이블 내 새로운 주소(해시값)를 찾는 과정이다.

선형 탐사(Linear probing)는 가장 간단한 방식이다. 앞선 예시에 해당한다. 최초 해시값에 해당하는 버킷에 다른 데이터가 저장돼 있으면 해당 해시값에서 고정 폭(예컨대 1칸)을 옮겨 다음 해시값에 해당하는 버킷에 액세스(삽입, 삭제, 탐색)한다. 여기에 데이터가 있으면 고정폭으로 또 옮겨 액세스한다.

그런데 탐사 이동폭이 고정돼 있는 선형탐사는 특정 해시값 주변 버킷이 모두 채워져 있는 primary clustring 문제에 취약하다고 한다. 아래 그림처럼 52~56까지 데이터가 저장돼 있고 임의의 키의 최초 해시값이 52라면 탐사를 네 번 수행하고 나서야 원하는 위치를 찾을 수 있다. 모두 빈 버킷이었다면 단 한 번의 해시만으로도 저장할 수 있었을 텐데 말이다.

제곱 탐사(Quadratic probing)는 고정 폭으로 이동하는 선형 탐사와 달리 그 폭이 제곱수로 늘어난다는 특징이 있다. 예컨대 임의의 키값에 해당하는 데이터에 액세스할 때 충돌이 일어나면 1212칸을 옮긴다. 여기에서도 충돌이 일어나면 이번엔 2222칸, 그 다음엔 3232칸 옮기는 식이다.

하지만 제곱탐사는 여러 개의 서로 다른 키들이 동일한 초기 해시값(아래에서 initial probe)을 갖는 secondary clustering에 취약하다고 한다. 초기 해시값이 같으면 다음 탐사 위치 또한 동일하기 때문에 효율성이 떨어진다. 예컨대 아래 그림에서 초기 해시값이 7인 데이터를 삽입해야 할 경우 선형 탐사 기법보다 성큼성큼 이동하더라도 탐사를 네 번 수행하고 나서야 비로소 데이터를 저장할 수 있다.

이중해싱(double hashing)은 탐사할 해시값의 규칙성을 없애버려서 clustering을 방지하는 기법이다. 2개의 해시함수를 준비해서 하나는 최초의 해시값을 얻을 때, 또 다른 하나는 해시충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용한다. 이렇게 되면 최초 해시값이 같더라도 탐사 이동폭이 달라지고, 탐사 이동폭이 같더라도 최초 해시값이 달라져 primary, secondary clustering을 모두 완화할 수 있다.

- 해시값을 반환해주는 h1h1을 ‘3으로 나눈 나머지’, 탐사 이동폭을 결정해주는 h2h2를 ‘5로 나눈 나머지’라고 둔다. 키가 3, 6인 데이터의 최초 해시값은 모두 0이 된다. 하지만 키가 3인 데이터의 탐사이동폭은 3, 6인 데이터의 이동폭은 1로 달라진다. 반대로 키가 6, 11인 데이터의 탐사이동폭은 모두 1이 된다. 하지만 키가 6인 데이터의 최초 해시값은 0, 11은 2로 달라진다.

- 단 제수(위 예시에서 3, 5)는 서로소(relatively prime, 공약수가 1뿐)이어야 원하는 효과를 볼 수 있다.

계산복잡성
: open addressing은 chaining과 달리 해시테이블의 크기(mm)가 고정돼 있으므로 nn개 데이터를 모두 저장하려는 경우 Load Factor α=n/mα=n/m는 1과 같거나 작다고 가정하자. 다시 말해 open addressing은 해시테이블에 데이터가 꽉 차지 않는다는 걸 전제로 한다는 이야기다. 아울러 open addressing에 적용된 해시함수는 키들을 모든 버킷에 균등하게 할당한다고 가정하고 계산복잡성을 분석한다.

open addressing 탐색의 계산복잡성은 탐사(probing) 횟수에 비례한다. 따라서 탐색 계산복잡성을 따질 때 핵심은 ‘탐사 횟수의 기대값’이다. successful search와 unsuccessful search의 탐사횟수 기대값은 각각 다음과 같다고 한다.

해시테이블에 데이터가 반만 차 있다(α=0.5α=0.5)고 가정하면 successful search와 unsuccessful search의 탐사횟수 기대값은 각각 1.387, 2가 됩니다. 다시 말해 최초로 해시값을 만드는 1회를 뺀 나머지, 즉 한번 정도만 추가 탐사하면 원하는 데이터를 대체로 찾을 수 있다는 얘기입니다. 반대로 α=0.8α=0.8이라면 탐사횟수 기대값은 8.047과 5로 치솟게 됩니다.

요컨대 open addressing 탐색 연산의 계산복잡성은 αα에 크게 영향을 받는 구조입니다. 따라서 해시테이블에 데이터가 어느 정도 차게 되면 해시테이블 크기 mm을 적절하게 늘려주고 처음부터 다시 해싱을 하는 것이 좋다고 합니다. 삭제와 삽입 연산 역시 탐사 횟수가 중요하기 때문에 해시테이블 크기에 신경을 써주어야 합니다.

1.3.4 해시함수
: 해시함수로 해시충돌을 완화하는 방법을 살펴보겠습니다. 해시테이블의 크기가 mm이라면, 좋은 해시함수는 임의의 키값을 임의의 해시값에 매핑할 확률이 1/m1/m이 될 겁니다. 다시 말해 특정 값에 치우치지 않고 해시값을 고르게 만들어내는 해시함수가 좋은 해시함수라는 이야기입니다.

division method
: 나눗셈법은 간단하면서도 빠른 연산이 가능한 해시함수입니다. 숫자로 된 키를 해시테이블 크기 mm으로 나눈 나머지를 해시값으로 반환합니다. mm은, 대개 소수(prime number)를 쓰며 특히 2의 제곱수와 거리가 먼 소수를 사용하는 것이 좋다고 합니다. 다시 말해 해시함수 특성 때문에 해시테이블 크기가 정해진다는 단점이 있다는 이야기입니다.

multiplication method
: 숫자로 된 키가 kk이고 AA는 0과 1 사이의 실수일 때 곱셈법은 다음과 같이 정의됩니다. mm이 얼마가 되든 크게 중요하지는 않으며 보통 2의 제곱수로 정한다고 합니다. 나눗셈법보다는 다소 느리다고 합니다. 2진수 연산에 최적화한 컴퓨터 구조를 고려한 해시함수라고 합니다.

h(k)=(kAmod1)×mh(k)=(kAmod1)×m

universal hasing
: 다수의 해시함수를 만들고, 이 해시함수의 집합 HH에서 무작위로 해시함수를 선택해 해시값을 만드는 기법입니다. HH에서 무작위로 뽑은 해시함수가 주어졌을 때 임의의 키값을 임의의 해시값에 매핑할 확률을 1/m1/m로 만드려는 것이 목적입니다. 다음과 같은 특정 조건의 해시함수 집합 HH는 1/m1/m으로 만드는 게 가능하다고 수학적으로 증명됐습니다.

- 해시테이블의 크기 mm를 소수로 정한다.
- 키값을 다음과 같이 r+1r+1개로 쪼갠다 : k0k0, k1k1,…, krkr
- 0부터 m−1m−1 사이의 정수 가운데 하나를 무작위로 뽑는다. 분리된 키값의 개수(r+1r+1)만큼 반복해서 뽑는다. 이를 a=[a0,a1,…,ar]a=[a0,a1,…,ar]로 둔다. 따라서 aa의 경우의 수는 모두 mr+1mr+1가지이다.
- 해시함수를 다음과 같이 정의한다 : ha(x)=Σri=0(aikimod m)ha(x)=Σi=0r(aikimod m)
- aa가 mr+1mr+1가지이므로 해시함수의 집합 HH의 요소 수 또한 mr+1mr+1개이다.

위와 같은 조건에서는 키가 동일하더라도 aa가 얼마든지 랜덤하게 달라질 수 있고, 이에 해당하는 해시함수 haha 또한 상이해지기 때문에 HH는 유니버설 함수가 된다.