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)이 된다.

See also

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