Hash

Overview

Hash 내용 정리

Hashing, Hash function

해시함수(Hash function)란, 데이터의 효율를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 이 때 매핑 전 원래 데이터의 값을 키(Key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(Hashing)이라고 한다.

해시함수는 해쉬 값의 개수보다 대게 많은 키 값을 해쉬값으로 변환(many-to-one 대응)하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시 값을 내는 해시충돌(collision)이 발생하게 된다.

Advantage

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

색인(index)에 해시값을 사용함으로써 모든 데이터를 살피지 않아도 검색과 삼입/삭제를 빠르게 수행할 수 있다.

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

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

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

다만 현재까지 개발된 거의 모든 해시함수는 해시충돌을 일으키는 것으로 확인된다. 물론 해시충돌 자체를 줄이는 것도 의미가 있겠지만, 중요한 것은 해시값 전체에 걸쳐 균들하게 발생하게끔 하는 것이다.

Hash table

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

Direct-address table

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

Direct-address table의 장점은 키 개수와 테이블 크기가 동일하기 때문에 해시출동 문제가 발생하지 않는다는 것이다. 하지만 실제 사용하는 키(actual key)보다 전체 키(universe of key)가 훨씬 많은 경우 사용하지 않는 키들을 위한 공간까지 마련해야 하는 탓에 메모리 효율성이 크게 떨어진다.

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

Collision

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

Chaining

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

Time complexity

Chaining 의 시간복잡도를 따져보자. 삽입(insertion), 탐색(search), 삭제(delete) 세 가지가 있다. 다음을 가정하고 진행한다.

• 해시 테이블의 크기 : m
• 실제 사용하는 키 개수 : n
• 해시함수가 키들을 모든 버킷에 균등하게 할당한다고 가정하면, 버킷 하나당 n/m = a 개의 키들이 존재하게 된다.

삽입의 시간복잡도를 계산해보자. 해시함수가 'pchero'라는 키를 해시값으로 매핑하는데에는 O(1)이 소요된다. 그리고 해당 해시값에 해당하는 연결 리스트의 head 에 이를 추가하는 데 O(1)이 소요된다. 따라서 삽입의 시간복잡도는 둘을 합친 O(1)이 된다.

이번에는 탐색의 시간복잡도를 계산해보자. 두 가지의 경우로 나뉘어서 계산한다.

쿼리 키 값에 해당하는 데이터가 해시테이블에 존재하지 않는 경우(unsuccessful search)이다. 이 경우 키를 해시 값으로 바꾸고, 해당 해시값에 해당하는 버킷의 요소들 a를 모두 탐색해봐야 존재하지 않는 사실을 알 수 있다. 따라서 unsuccessful search 의 시간복잡도는 O(1 + a)가 된다.

이번엔 쿼리 키 값에 해당하는 데이터가 해시테이블에 존재하는 경우(successful search)이다. 이 경우 키를 해시 값으로 바꾸고, 해당 해시값에 해당하는 버킷의 요소들 가운데 키 해당하는 데이터가 있는지 탐색해봐야 한다.

Big O notation 의 시간 복잡도를 따져보기 위해서는 항상 최악의 경우를 고려해야 한다. 즉, 해당 버킷의 tail 에 값이 있는 경우이다. 데이터가 해시 테이블에 존재한다고 가정했으므로 버킷 내 a 개 요소 가운데 반드시 찾고자 하는 값이 존재한다. a - 1 개를 비교했는데도 값을 찾지 못했다면 tail 값은 자동적으로 찾고자하는 값이 된다.

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

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

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

Open addressing

Open addressing 은 chaining 과는 달리 한 버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시테이블이다. 해시함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용한다는 취지에서 open addressing 이라는 이름이 붙었다. 메모리 문제가 발생하지는 않으나, 해시충돌이 발생할 수 있다.

Insert, Delete, Search

해시함수가 '키 값을 8로 나눈 나머지'이고, 10, 18, 26 순으로 해시테이블에 데이터를 삽입한다고 가정해보자. 세 숫자 가운데 첫번째 입력값인 10을 제외한 18, 26 은 원래 버킷(2) 말고, 각각 다음(3), 다음 다음(4) 버킷에 저장하는 것이 open addressing 의 방식이다.

여기서 18을 삭제해보자. 18의 해시값은 2 인데, 여기에는 10이 저장되어 있으므로 스킵하고, 그 다음 버킷(3)을 탐색해서 값을 확인하면 18이 있음을 확인할 수 있다. 확인된 18을 삭제한다.

이제 26을 탐색해보자. 26의 해시값은 2 인데, 여기에는 10이 저장되어 있으므로 스킵하고, 그 다음 버킷(3)을 탐색해보자. 그런데 비어 있다. 여기서 별도의 조치를 취하지 않으면 알고리즘은 '2번 해시값 1칸 옆인 3에 저장된 데이터가 없고, 해시충돌도 없으므로 탐색을 종료한다'가 되어 버린다.

이를 해결하기 위해 삭제 연산 때, 'DEL'와 같은 별도의 표시를 해둔다.

Probing

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

• 선형탐사(Linear probing)

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

그런데 탐사 이동폭이 고정되어 있는 선현탐사는 특정 해시값 주변 버킷이 모두 채워져 있는 primary clustering 문제에 취약하다. 예를 들어 52 ~ 56 까지의 데이터가 저장되어 있고 임의 의 키의 최초 해시값이 52라면 탐사를 4번 수행하고 나서야 원하는 위치를 찾을 수 있다.

• 제곱탐사(Quadratic probing)

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

하지만 제곱탐사는 여러 개의 서로 다른 키들이 동일한 초기 해시값(initial probe)을 갖는 secondary clustering 에 취약하다. 초기 해시 값이 같으면 다음 탐사 위치 또한 동일하기 때문에 효율성이 떨어진다.

• 이중해싱(double hashing)

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

해시값을 반환해주는 h1 을 '3으로 나는 나머지, 이동폭을 결정해주는 h2 를 '5로 나눈 나머지'라고 하자. 예컨데 키가 3, 6인 데이터의 최초 해시값은 모두 0이 된다. 하지만 키가 3인 데이터의 탐사 이동폭은 3, 키가 6 데이터의 탐사 이동폭은 1로 달라진다. 반대로 키가 6, 11인 데이터의 탐사 이동폭은 모두 1이 되지만, 최초 해시값은 0과 2로 달라지게 된다.

단, 키 값은 서로소(relatively prime, 공약수가 1뿐)이어야만 원하는 결과를 볼 수 있다.

Time complexity

Open addressing 은 chaining 과 달리 해시 테이블의 크기(m)가 고정되어 있으므로, n개 데이터를 모두 저장하려고 하는 경우, Load factor a = n/m 1 과 같거나 작다고 가정한다. 다시 말해 open addressing 은 해시테이블에 데이터가 꽉 차지 않았다는 것을 전제로 한다는 이야기이다. 아울러 open addressing 에 적용된 해시함수는 키들을 모든 버킷에 균등하게 할당한다고 가정하고 시간복잡도를 분석한다.

open addressing 탐색의 시간복잡도는 탐사(probing) 횟수에 비례한다. 따라서 탐색 계산복잡도를 따질 때 핵심은 '탐사 횟수의 기댓값'이다. Successful search 와 Unsuccessful search 의 탐사횟수 기대값은 각각 다음과 같다.

• Successful search

(1 / a) ln (1 / (1 - a))

• Unsuccessful search

1 / a

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

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

Hash function

해시테이블의 크기가 m 이라면 좋은 해시함수는 임의 키 값을 임의의 해시값에 매핑할 확률이 1/m 이 될 것이다. 다시 말해 특정 값에 치우치지 않고 해시값을 고르게 만들어내는 해시함수가 좋은 해시함수라는 것이다.

Division method

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

Multiplication method

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

• h(k) = (kA mod 1) x m

Universal hashing

다수의 해시함수를 만들고, 이 해시함수의 집합 H 에서 무작위로 해시함수를 선택해 해시값을 만드는 기법이다. H 에서 무작위로 뽑은 해시함수가 주어졌을 때 임의의 키 값을 임의의 해시값에 매핑할 확률을 1 / m 으로 만드는 것이 목적이다. 다음과 같은 특정 조건의 해시함수 집합 H 는 1 / m 으로 만드는 것이 가능하다.

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

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

See also

• https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/ - 해싱, 해시함수, 해시테이블