[알고리즘] 해시 테이블 :: 늦깎이 IT

[ 해시 테이블이란? ]

해시 테이블이란 데이터의 효율적으로 관리하기 위한 자료구조이다. 해시 테이블은 검색하고자 하는 키(Key) 값을 해시 함수를 통해 해시 값으로 변환하고 그 해시 값을 가지고 데이터에 접근하는 것이다.

[ 해시함수란? ]

해시함수란 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시 코드(hash code) 혹은 해시 값(hash value)라고 하며 매핑하는 과정 전체를 해싱(hasing)이라고한다.

[ 충돌 발생 ]

해시 함수는 서로 다른 키(key) 값에 대해서 서로 다른 해시 코드(hash code)를 생성한다고 했다. 하지만, 꼭 그렇지 않을 가능성이 있다.

예를 들어, 임의의 해시 함수 F가 있다고 가정하자. 해시 함수는 입력으로 받은 키를 100으로 나눈 후 그 나머지 값을 반환한다고 가정하자. 그렇다면 해시 함수 F의 입력으로 102와 202라는 키 값을 전달하면 그 결과는 모두 2가 되는 것을 알 수 있다.

서로 다른 키 값에 대해서 해시 코드가 같기 때문에, 해시 테이블에 저장하는 과정에서도 충돌이 발생하게 된다.

이처럼, 충돌이 발생하지 않게하는 해시 함수일수록 좋은 해시 함수라고 할 수 있다.

아래 그림은 테이블의 메모리 상황을 표현한 것이다. 그림에서 검은 영역은 데이터가 채워진 버킷을 의미하고, 반대로 흰 영역은 빈 버킷을 의미한다. 이 그림을 보면 데이터가 테이블의 전체 영역에 고루 분포되어 있음을 알 수 있다. 이처럼 고루 분포된다는 것은 데이터가 '충돌'할 가능성이 적다는 것을 의미한다.

아래 그림은 테이블의 특정 영역에 데이터가 몰려있는 상황을 보여준다. 이처럼 데이터가 테이블의 특정 영역에 해싱된다면 데이터가 '충돌'할 가능성이 높다는 것을 의미한다.

즉, 데이터의 분포도를 넓게 퍼뜨리는 것이 좋은 해시 함수라고 할 수 있다.

[ 해시 함수 ]

위에서 데이터의 분포도를 넓게 퍼뜨리는 것이 좋은 해시 함수라고 했다. 

해시 테이블의 크기가 m이라면 좋은 해시 함수는 임의의 키 값을 매핑할 확률이 1/m이 될 것이다. 

또한, 키 값들이 어떤 특정한 패턴을 가지고 있다하더라도, 해시 함수 값이 불규칙적인 것이 바람직하다.

1. Division 기법

해시 테이블에 저장할 키 값을 해시 테이블의 크기 m으로 나눈 나머지를 반환하는 기법이다. m은 대체로 소수(prime number)를 사용한다. 

그러나, 어떤 m 값에 대해서는 해시 함수값이 키의 특정 부분에 의해서 결정되는 경우가 있다.

예를 들어, m = 2^p 이면 키의 하위 p비트가 해시 함수값이 되므로 바람직한 방법은 아니라고 할 수 있다.

2. Multipication 기법

해시 테이블에 저장할 키를 k라고 하고 0과 1사이에 있는 소수 A가 있다고 하자. 그 이후, k와 A를 곱한 결과의 소수 부분에 m을 곱한 후, 소수점을 버리는 것이다. (말이 복잡한데... 수식을 보자)

[ Open Addressing 방법 ]

서로 다른 키에 대한 해시 코드가 같을 경우 충돌이 발생한다고 했다. 충돌이 발생한 그 자리를 대신해서 빈자리를 찾아가는 방법이 있는데, 이를 Open Addressing 방법이라고 부른다.

1. 선형 탐사법 (Linear Probing)

충돌이 발생했을 때 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장하는 것이 '선형 탐사법'이다.

예를 들어, 다음과 같이 정의된 해시 함수가 있다고 가정하자.

• hash function F(key) = key % 7

이때, 입력된 키가 9라고 한다면 9를 7로 나눈 나머지인 2에 저장될 것이다.

그 다음으로 입력된 키가 2인 데이터를 해시 테이블에 저장하려고 한다면, 충돌이 발생한다. 이때 충돌이 발생한 인덱스로부터 인접한 위치를 확인하며 빈칸을 찾아 저장한다. 

그러나, 선형 탐사법의 단점으로는 충돌의 횟수가 증가됨에 따라 '클러스터 현상'이 발생한다는 것이다. 즉, 특정 영역에 데이터가 집중적으로 몰리는 현상이 발생한다.

2. 이차 탐사법 (Quadratic Probing)

선형 탐사법의 단점인 '클러스터' 문제를 해결하기 위한 방법으로 이차 탐사법이 있다. 이차 탐사법은 충돌이 발생한 인덱스에서 다음 위치를 찾을 때, 바로 인접한 칸을 찾는 것이 아닌 조금 더 멀리 떨어진 곳에서 빈 공간을 찾는다.

그러나, 이차 탐사법의 경우에도 클러스터가 발생할 가능성이 있다. 위의 수식을 보면 같은 해시 코드를 갖는 키 값들에 대해서 빈 버킷을 찾기 위해 접근하는 위치가 늘 동일하다.

3. 이중 해시 (Double Hash)

선형/이차 탐사법의 단점인 '클러스터' 현상의 발생 가능성을 낮추기 위한 방법으로 '이중 해시' 방법이 있다.

이중 해시 방법은, 충돌이 발생한 인덱스로부터 빈 버킷을 찾기위한 탐색 범위(?)를 불규칙적으로 갖게 하는 방법이다.

이중 해시 방법에서는 두 개의 해시 함수를 사용한다.

• 첫 번째 해시 함수는 입력되는 키 값을 기준으로 저장 위치를 결정하는 해시 함수이다.

• 두 번째 해시 함수는 충돌이 발생했을 때, 몇 칸 뒤에 위치한 버킷을 살펴볼지 그 거리를 결정하는 해시 함수이다.

다음과 같이 정의된 두 개의 해시 함수가 있다고 가정하자.

• 

• 

1. 1차 해시 함수를 %15로 결정했다는 것은, 해시 테이블의 크기가 15라고 예상할 수 있다.

2. 2차 해시 함수에서 1을 더하는 이유는 2차 해시 함수 값이 0이 되는 것을 막기 위해서다. 2차 해시 함수는 충돌이 발생한 위치로부터 몇 칸 뒤에 위치한 버킷을 살펴보기 위한 함수이므로, 0을 반환하는 것은 의미가 없기때문이다.

3. c 값은 15보다 작은 소수로 결정한다. 그 이유는 2차 해시 값이 1차 해시 값보다 커지는 것을 방지하기 위해서이다. 예를 들어, 1차 해시 함수 값이 14이고, 2차 해시 값이 34라면 빈 자리를 찾기 위해서 해시 테이블을 몇바퀴나 돌아야 할지 모르는 일이기 때문이다.

4. c 값을 소수로 결정하는 이유는 소수를 선택했을 때 클러스터 현상의 발생 확률을 낮출 수 있다는 통계를 근거로 한 것이다.

4. 키의 삭제

해시 테이블의 각 버킷에는 총 세 개의 상태 정보를 저장해야한다.

• EMPTY            해당 버킷에 데이터가 저장된적이 없다.
• DELETED         해당 버킷에 데이터가 저장된적 있지만, 현재는 비워진 상태이다.
• INUSE            해당 버킷에 현재 데이터가 저장되어 있다.

세 개의 상태중에서 유심히 살펴봐야 할 것은 DELETED이다. 인덱스 2에 있는 데이터 9를 지운 상태인 아래 그림을 보자.

위의 그림과 같은 상태에서 키가 2인 데이터를 탐색하는 과정을 살펴보자. 키가 2인 데이터는 해시 함수를 통해 해시 코드 2를 갖게되므로, 해시 테이블의 인덱스가 2인 곳부터 탐색을 진행한다.

그러나, 충돌이 발생했을 경우 선형/이차 탐사법에 의해 해시 코드 값에 해당하는 인덱스가 아닌 그 뒤의 인덱스에 저장될 수 있음을 알고있다.

만약, 인덱스가 2인 버킷의 상태가 EMPTY 상태라면 그 뒤의 인덱스를 더 이상 탐색하지 않게되므로, DELETED라는 상태 정보를 남김으로써 그 이후의 인덱스도 검사할 수 있도록하는 것이다.

[ Separate Chaining 방법 ]

충돌이 발생하면, 빈 버킷을 찾아가는 Open Addressing 방법과는 달리 Chaining 방법은 충돌이 발생하더라도 자신의 위치에 데이터를 저장하는 방식이다.

이는 연결 리스트를 기반으로 하여 구현할 수 있다. 그림을 보면 직관적으로 이해가 될 것이다.

 위 그림처럼, 버킷을 생성하고 연결 리스트의 모델로 연결해나가는 방식으로 충돌 문제를 해결하는 것이 Chaining 방법이다.

Chaining 방법을 적용하면, 하나의 해시 값에 다수의 버킷들이 저장되는 것을 확인할 수 있다. 따라서 탐색을 위해서는 동일한 해시 값으로 묶여있는 모든 버킷들을 확인해야 한다는 단점이 생긴다.

하지만, 해시 함수를 잘 정의하여 모든 데이터들이 골고루 분포되게 하여 충돌 확률이 높지 않다면 탐색에 드는 비용은 부담스러운 정도는 아닐 것이다.

[ 시간 복잡도 ]

Chaining 방법의 시간 복잡도를 살펴보자.

시간 복잡도를 계산하기 위해서는 Load Factor라는 개념을 알아야 한다. Load Factor란 해시 테이블의 하나의 버킷에 평균 몇 개의 키가 해싱되는지 나타내는 지표이다.

해시 테이블의 크기를 m, 해시 테이블에 저장될 키의 갯수를 n이라고 할 때 Load Factor(α) 는 다음과 같이 구한다.

α가 의미하는 바는, 해시 테이블의 모든 버킷에 저장된 키의 평균 갯수가 α라는 뜻이다.

1. 삽입

• 해시 테이블에 저장할 키 값을 해시 코드로 변환하는 시간 복잡도는 O(1)이다.
• 키 값을 버킷에 있는 연결 리스트의 헤더 부분에 추가하는 시간 복잡도는 O(1)이다.
• 즉, 삽입 연산의 시간 복잡도는 이 둘을 합친 O(1)이다.

2. 탐색

• 해시 테이블에 탐색할 키 값을 해시 코드로 변환하는 시간 복잡도는 O(1)이다.
• 해시 값에 해당하는 버킷에서 해당 키 값을 찾기 위해 걸리는 시간 복잡도는 O(α)이다.
• 즉, 탐색 연산의 시간 복잡도는 이 둘을 합친 O(1+α)이다.

3. 삭제

• 해시 테이블에 탐색할 키 값을 해시 코드로 변환하는 시간 복잡도는 O(1)이다.
• 해시 값에 해당하는 버킷에서 해당 키 값을 찾기 위해 걸리는 시간 복잡도는 O(α)이다.
• 해당 버킷의 연결 리스트에서 해당 키 값을 삭제하는 연산은 O(1) 이다.
• 즉, 삭제 연산의 시간 복잡도는 O(1+α)이다.

해시 테이블과 관련된 더 상세한 내용은 [이곳]을 참고하기 바란다.