해시 테이블 (Hash Table)

해시 테이블이란?

 

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 효율적인 탐색(빠른 탐색)을 위한 자료구조이다. 

 

해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

 

저장, 삭제, 검색의 시간복잡도는 모두 O(1)이다.

 

 

 

직접 주소화 테이블?

 

해시 테이블와는 다르게 직접 주소화 테이블(Direct-address Table)이라는 key값으로 k를 갖는 데이터를 index k에 저장하는 방식이 있다. 이를 통하여 key-value 쌍의 데이터를 저장하고자 하면 많은 문제가 발생한다. 

 

첫 번째로, 불필요한 공간 낭비가 발생한다. key값이 큰 숫자라면 index의 값이 커지므로 남아도는 공간이 늘어나게 된다. 

key: 학번, value: 이름

(2022390, 노정호)
(2022392, 배준석)
(2022393, 정재헌)
(2022401, 남영욱)

 

두 번째로, key가 다양한 자료형을 담을 수 없다. key값이 index로 활용되기 때문에 예를 들어 문자열로 된 key값은 저장이 불가해지는 문제가 발생한다.

key: ID, value: 이름

(nossi8128, 노정호)
(js9876, 배준석)
(zebra001, 정재헌)
(nam1234, 남영욱)

 

따라서, key-value 데이터 쌍을 저장하기 위한 방법으로 직접 주소화 방법은 맞지 않는다.

 

해시 테이블은 hash function h를 이용해서 (key, value)를 index: h(k)에 저장한다. 이 때, “키 k값을 갖는 원소가 위치 h(k)에 hash된다.” 또는 “h(k)는 키 k의 해시값이다”라고 표현한다. key는 무조건 존재해야 하며, 중복되는 key가 있어서는 안된다.

 

 

예를 들어

(Key, Value)가 ("John Smith", "521-1234")인 데이터를 크기가 16인 해시 테이블에 저장한다고 하자.

그러면 먼저 index = hash_function("John Smith") % 16 연산을 통해 index 값을 계산한다.

그리고 array[index] = "521-1234" 로 전화번호를 저장하게 된다.

 

 

 

해시 함수

해시 함수에서 중요한 것은 고유한 인덱스 값을 설정하는 것이다.

좋은 해쉬 함수란, 데이터를 되도록 고르게 분포하여 충돌을 최소화할 수 있는 함수이다.

 

해시 테이블에 사용되는 대표적인 해시 함수로는 아래의 3가지가 있다.

1. Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.( 주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.
2. Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
3. Multiplication Method: 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k)=(kAmod1) × m
4. Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

 

 

해시(Hash)값이 충돌하는 경우(Collision)

그런데 만약 "John Smith"를 해시 함수를 돌려 나온 값과 "Mang Kyu"를 해시 함수를 돌려 나온 값이 동일하다면 어떻게 해야 할까? 이렇게 중복되지 않는 서로 다른 key의 해시값이 중복될 때의 상황을 Collision이 발생했다고 한다. 

 

따라서, Collision이 최대한 적게 나도록 해시함수를 잘 설계해야하지만 그럼에도 발생하는 경우는 분리 연결법(Separate Chaining)과 개방 주소법(Open Addressing) 같은 방법을 사용하여 해결해야 한다.다

 

 

 

 

분리 연결법(Separate Chaining)

 

 

동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다. 그 추가 메모리로 Linked List(연결리스트)를 이용한다. 각 index에 데이터를 저장하는 Linked List에 대한 포인터를 가지는 방식이다. 위의 그림과 같이 동일한 버킷으로 접근을 한다면 데이터들을 연결하여 관리해주고 있다. 

 

추가 

만약에 동일  index로 인해서 충돌이 발생하면 그 index가 가리키고 있는 Linked list에 노드를 추가하여 값을 추가한다.  따라서, 시간복잡도는 O(1)이다. 이렇게 함으로써 충돌이 발생하더라도 데이타를 삽입하는 데 문제가 없다. 

 

검색

데이타를 추출을 하고자할 때는 key에 대한 index를 구한후, index가 가리키고 있는 Linked List를 선형 검색하여, 해당 key에 대한 데이타가 있는지를 검색하여 리턴하면 된다. 기본적으로 O(1)이지만 n개의 모든 key가 동일한 해시값을 갖게 되면 길이 n의 linked list가 생성되게 된다. 따라서 최악의 경우, 검색의 시간복잡도가 O(n)이 된다.

 

삭제

key를 삭제하는 것 역시 간단한데, key에 대한 index가 가리키고 있는 Linked List에서, 그 노드를 삭제하면 된다. 시간복잡도는 삭제를 하기 위해선 검색을 먼저 해야하므로 검색의 시간복잡도와 동일하다.

 

이러한 Chaining 방식은 해시 테이블의 확장이 필요없고 간단하게 구현이 가능하며, 손쉽게 삭제할 수 있다는 장점이 있다. 하지만 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아지면 효율성이 감소한다는 단점이 있다.

 

 

※ 참고

기본적으로 linked list를 이용하여 데이터를 저장하지만, collision이 많이 발생하여 linked list의 길이가 길어지면 Binary Search Tree(BST)자료구조를 이용하여 데이터를 저장하기도 한다. BST를 사용함으로써 검색의 최악 시간복잡도를 O(n) 에서 O(logn)으로 낮출 수 있다.

 

 

이진 탐색 트리 (BST-Binary Search Tree)

 

 

개방 주소법(Open Addressing)

 

Open Addressing이란 추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다. Open Addressing을 구현하기 위한 대표적인 방법으로는 3가지 방식이 존재한다.

 

1. 선형 조사법(Linear Probing) : 현재의 버킷 index로부터 고정폭 만큼씩(+1,+2,+3, ...) 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
2. 이차 조사법(Quadratic Probing) : 해시의 저장순서 폭을 제곱으로(+1^2, +2^2, +3^2, ...) 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.

→ 선형 조사법이나 이차 조사법의 경우 탐사이동폭이 같기 때문에 충돌 횟수가 많아지면 특정 영역에 데이터가 집중적으로 몰리는 클러스터링(clustering)현상이 발생하는 단점이 있다. 클러스터링 현상이 발생하면, 평균 탐색 시간이 증가하게 된다. 이러한 문제가 발생하지 않도록 다음과 같은 방식을 사용한다. 

 

1. 이중해시(Double Hashing Probing) : 클러스터링 문제가 발생하지 않도록 2개의 해시함수를 사용하여 하나는 최초의 해시값을 얻을 때 사용하고 또 다른 하나는 해시 충돌이 발생할 때 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

 

 

 

해시테이블 시간복잡도와 공간효율

 

각각의 Key값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간복잡도로 데이터를 조회할 수 있다. 또한, 저장이나 삭제도 O(1)이다. 하지만 데이터의 충돌이 발생한 경우 Chaining에 연결된 리스트들까지 검색을 해야 하므로 O(N)까지 시간복잡도가 증가할 수 있다. 

 

공간효율성은 떨어진다. 데이터가 저장되기 전에 미리 저장공간(slot, bucket)을 확보해야 하기 때문이다. 따라서 저장공간이 부족하거나 채워지지 않은 부분이 많은 경우가 생길 수 있다.

 

 

 

해시테이블 성능 향상

만약 테이블이 꽉 차있는 경우라면 테이블을 확장하는 Resizing을 해주어야 하는데,

 

Resizing

Open addressing의 경우, 고정 크기 배열을 사용하기 때문에 데이타를 더 넣기 위해서는 배열을 확장해야 한다. 

또한 Separate changing에 경우에도 버킷이 일정 수준으로 차 버리면 각 버킷에 연결되어 있는 List의 길이가 늘어나기 때문에, 검색 성능이 떨어지기 때문에 버킷의 개수를 늘려줘야 한다. 

이를 Resizing이라고 하는데, Resizing은 별다른 기법이 아니라 더 큰 버킷을 가지는 array를 새로 만든 다음에, 다시 새로운 array에 hash를 다시 계산해서 복사해줘야 하는 것이다. 

 

이는 매우 심각한 성능의 저하를 불러오기 때문에 가급적이면 확장을 하지 않도록 테이블을 설계해주어야 한다. 

(통계적으로 해시 테이블의 공간 사용률이 70% ~ 80%정도가 되면 해시의 충돌이 빈번하게 발생하여 성능이 저하되기 시작한다고 한다.) 

 

 

Cache를 이용한 성능 향상

또한 해시 테이블에서 자주 사용하게 되는 데이터를 Cache에 적용하면 효율을 높일 수 있다. 자주 hit하게 되는 데이터를 캐시에서 바로 찾음으로써 해시 테이블의 성능을 향상시킬 수 있다.