<해싱 (Hashing)>: 기본 개념

# 해싱이란?

---

 대부분의 탐색 방법들은 탐색 키를 저장된 키 값과 반복적으로 비교하면서 탐색을 원하는 항목에 접근한다. 반면 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 이렇게 키 값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(hash table)이라 부르고, 해시 테이블을 이용한 탐색을 해싱(hashing)이라 한다.

 키들의 비교에 의한 탐색 방법은 정렬이 안 되어 있다면 $O(n)$이고 정렬이 되어 있다면 $O(log_2n)$이다. 정렬되어 있는 경우의 시간 복잡도가 $O(log_2n)$인 건 이진 탐색 알고리즘 혹은 이진 탐색 트리의 탐색 알고리즘의 시간복잡도를 생각하면 된다. 잘 모르겠다면 이진 탐색 또는 이진 탐색 트리 알고리즘 게시물을 참고하도록 하자.

 해싱이 나오게 된 배경은 위에서 설명한 시간복잡도 보다 더욱 빠른 탐색을 필요로 할 때다. 해싱은 이론적으로 $O(1)$의 시간 안에 탐색을 끝마칠 수도 있다. 해싱은 보통 사전(dictionary)과 같은 자료 구조를 구현할 때에 최상의 선택이 된다.

# 사전 구조

---

 사전 구조(dictionary)는 맵(map)이나 테이블(table)로 불리기도 한다. 사전 구조는 다음과 같이 탐색 키, 그리고 탐색 키와 관련 있는 값 이렇게 2가지 종류의 필드를 가진다.

• 영어 단어나 사람의 이름 같은 탐색 키 (saerch key)
  
  
• 단어의 정의나 주소 또는 전화 번호와 같은 탐색 키와 관련된 값 (value)

 영어 사전으로 예를 들자면, 영어 단어가 탐색 키 (search key)이고 영어 단어의 뜻풀이가 값 (value)이 된다. 사전 구조는 항목들을 탐색 키에 의하여 식별하고 관리한다. 항목들의 위치는 상관 없다. 따라서 항목들을 접근하고 삭제할 때는 단지 키만 있으면 된다. // 키를 삭제하면 키와 관련 있는 뜻풀이까지 함께 날아가기 때문에 단지 키만 삭제하면 되는 것이다.

 사전 구조에 있는 항목들은 모두 탐색 키를 가지고 있다는 점에서 리스트와 같은 다른 자료구조들과는 구분이 된다. 리스트에도 물론 탐색 키를 같이 넣어서 저장할 수 있지만, 리스트는 근본적으로 위치에 의하여 관리되는 자료구조이다. 반면 자료구조는 오직 탐색 키에 의해서만 관리된다. // 리스트에서는 특정 노드를 방문할 때, 해당 노드가 나올 때까지 계속 다음노드를 살펴봐야 한다. 이것 또한 $O(n)$의 시간복잡도가 요구되는 작업이다.

 사전 구조에서는 유일한 탐색 키를 사용하기도 하고 동일한 탐색 키를 허용하기도 한다. 예를 들면, 주민등록번호에 의하여 학생들을 관리하는 사전 구조는 유일한 탐색키를 사용하는 경우이다. 그러나 영어 사전의 경우 철자가 동일한 단어가 많은 의미를 가질 수 있기 때문에 중복되는 탐색키를 사용한다.

 우리가 일상생활에서 사용하는 영어 사전은 단어들이 알파벳 순으로 정렬되어 있다. 그러나 자료 구조에서의 사전 구조는 탐색 키에 따라 정렬되어 있기도 하고 그렇지 않기도 하다. 사전 구조에서는 무조건 탐색 키에 의하여 항목에 접근할 수만 있으면 된다. 따라서 정렬 여부는 추상 자료형 사전 구조를 구현할 때에 결정해야 할 문제이다.

 시간 구조를 효율적으로 구현하기 위해서 어떤 자료구조를 사용해야할까? 이진 탐색트리를 사용한다고 가정해보면, 최악의 경우 이진 탐색트리의 모양은 경사 이진 트리가 될 것이고, $n$개의 노드를 가지는 경사 이진 트리의 높이는 $n$ 이므로 시간 복잡도는 $O(n)$이 될 것이다. 사전 구조를 가장 효율적으로 구현할 수 있는 방법은 우리가 다룰 해싱이다. 해싱은 탐색 키의 비교가 아닌 탐색 키에 수식을 적용시켜서 바로 탐색 키가 저장된 위치를 얻는다.

# 해싱의 구조

---

해싱에서는 자료를 저장하는 데 배열을 사용한다. 배열은 원하는 항목이 저장된 위치를 알고 있을 경우 매우 빠르게 자료를 삽입하거나 꺼낼 수 있다. 리스트와 같이 저장된 위치를 찾기 위해 다음 노드로 옮기는 등의 작업이 전혀 없으므로 시간 복잡도는 $O(1)$로 매우 빠르다. 해싱이란 어떤 항목의 탐색 키만을 가지고 바로 항목이 저장되어 있는 배열의 인덱스를 결정하는 기법이다.

 예를 들어, 탐색 키들이 0부터 999까지의 정수라고 가정해보자. 이들을 만약 1000개의 요소를 가진 배열로 구성하고 각 정수에 맞게 인덱스를 설정했다고 가정해보자. 999의 정수를 접근하기 위해서 우리가 해야할 일은 단지 인덱스 999에 접근하기만 하면 되는 것이다. 배열의 이름을 arr이라고 했을 때, 999 값을 읽기 위해서는 arr[999]만 해주면 되는 것이다.

 그러나 현실적으로는 탐색 키들이 문자열이거나 매우 큰 숫자이기 때문에 탐색 키를 일일이 직접 배열의 인덱스로 사용하기에는 무리가 있다. 그래서 우리는 각 탐색 키를 작은 정수로 사상(mapping)시키는 함수( = hash function)가 필요하다.

 해시 함수(hash function)란 탐색 키를 입력으로 받아 해시 주소(hash address)를 생성하고 이 해시 주소가 배열로 구현된 해시 테이블(hash table)의 인덱스가 된다. 이 배열의 인덱스 위치에 자료를 저장할 수도 있고 저장된 자료를 꺼낼 수도 있다. 예를 들어 영어 사전을 배열 hashTable[ ]에 저장한다고 하면 단어을 해싱 함수를 이용하여 적절한 정수 i로 변환한 다음, 배열 요소 hashTable[ i ]에 단어의 정의를 저장하는 것이다.

위의 그림을 살펴보자. 해쉬 테이블 hashTable은 $n$개의 버켓(bucket)으로 이루어지는 테이블로, hashTable[0], hashTable[1], ..., hashTable[$n-1$]의 원소를 가진다. 하나의 버켓은 $s$개의 슬롯(slot)을 가질 수 있으며, 하나의 슬롯에는 하나의 항목이 저장된다. 

 하나의 버켓에 여러 개의 슬롯을 두는 이유는 서로 다른 두 개의 키가 해시 함수에 의해 동일한 해시 주소로 변환될 수 있으므로 여러 개의 항목을 동일한 버켓에 저장하기 위함이다. // 지금까지 만들어진 어떤 해시 함수도 완벽히 다른 주소로 변환하는 함수는 존재하지 않는다. 동일한 주소를 반환하는 충돌 문제가 발생할 수 있다는 것이다. 따라서 그에 대한 대비를 하는 것은 자료구조를 작성할 때 당연히 해야할 일이다. 그러나 대부분의 경우 하나의 버켓은 하나의 슬롯을 가진다.

 해시 테이블에 존재하는 버켓의 수가 $n$이므로 해쉬 함수 hashFunction( )은 모든 key에 대하여 $0$$\leq$$hashFunction(key)$$\leq$$n-1$의 범위의 값을 제공해야 한다. 대부분의 경우 해시 테이블의 버켓 수는 키가 가질 수 있는 모든 경우의 수보다 매우 작으므로 여러 개의 서로 다른 탐색 키가 해시 함수에 의해 같은 해시 주소로 사상(mapping)되는 경우가 자주 발생한다.

 서로다른 두 개의 탐색 키 $k1$과 $k2$에 대하여 $h(k1) = h(k2)$인 경우를 충돌(collision)이라고 하며, 이러한 키 $k1$과 $k2$를 동의어(synonym)라 한다. 만약 충돌이 발생하면 같은 버켓에 있는 다른 슬롯에 항목을 저장하게 된다. 충돌이 자주 발생하면 버켓 내부에서의 순차 탐색 시간이 길어져서 탐색 성능이 저하될 수 있으므로 해시 함수를 수정하거나 해시 테이블의 크기를 적절히 조절해주어야 한다.

 이러한 충돌이 버켓에 할당된 슬롯 수보다 많이 발생하게 되면 버켓에 더 이상 항목을 저장할 수 없게 되는 오버플로(overflow)가 발생하게 된다. 만약 버켓당 슬롯의 수가 하나(s=1)이면 충돌이 곧 오버플로를 의미한다. 오버플로가 발생하면 더 이상 항목을 저장할 수 없게 되므로 오버플로를 해결하기 위한 방법이 반드시 필요하다.