1. 테이블 구조란?

일반적으로 현실에서 데이터를 저장하고 저장된 데이터를 참조할 때, 단순히 나열된 데이터를 이용하는 것 보다 표 형식의 데이터를 이용하는 것이 효율적이다.

201600001 가가가 201600002 가가각 … 201608432 홍길동 …

보다

학번 이름
201600001 가가가
201600002 가가각
… …
201608432 홍길동
… …

가 더 직관적이고 효율적이다

이러한 ‘표’ 를 영어로 Table이라 하는데, 컴퓨터과학에서는 이를 한층 더 추상화하여 Key-Value쌍으로 저장된 모든 데이터를 테이블(Table) 또는 맵(Map) 구조라 한다(혹은 사전 구조 - Dictionary 라고도 한다).

테이블 구조는 Key(학번)를 알면 Value(이름)을 바로(혹은 매우 빠른 시간 안에) 찾을 수 있다.

일반적인 프로그래밍 문법에서는 배열의 인덱스 문법을 활용해 이러한 테이블 구조를 구현할 수 있다(테이블 구조에 사용되는 배열을 버킷-Bucket이라 한다).

이때 알 수 있는 점은 Key는 반드시 존재하여야 하고, 동시에 중복될 수 없다는 점이다.

배열에 데이터를 저장할 때 반드시 어디에 저장할지에 대한 인덱스가 필요하고, 한 인덱스가 가리키는 원소에 여러 데이터를 저장할 수 없는 것과 동일한 원리이다.

2. 테이블 구조의 한계와 해시 함수

이처럼 배열을 사용하여 테이블 구조의 구현이 가능하지만, 단순한 배열 테이블은 다음과 같은 단점이 있다.

  • 배열이 가장 큰 Key의 길이만큼의 길이를 가져야 한다.

만약 Key가 위의 예시처럼 9자리 학번일 경우, 테이블은 다음처럼 구현된다.

class Table
{
private:
    int* bucket;
    
public:
    Table(size_t maxKey)
        :bucket(new int[maxKey+1])	// maxKey = 999999999
    {}
}

게다가, 이러한 방식으로 만들어진 테이블 객체는 키의 범위가 다른 새로운 데이터 집단에 대응하기 어렵다.

따라서 임의의 키의 길이를 고정된 길이로 변환시켜주는 연산을 통해 새로운 값을 구해 사용하는데, 이 변환을 위한 함수를 해시 함수(Hash Function) 라 하며, 해시 함수로부터 도출된 값을 해시값(Hash value, 또는 HashSum, CheckSum) 이라 한다.

해시 함수는 일반적으로 나머지 연산을 이용하지만, 나머지 연산은 해시값의 중복이 발생할 가능성이 높다.

이때 해시값의 중복이 일어나는 것을 충돌(Collision) 이라 하며, 충돌은 이론적으로 완전히 피할 수 없다.

따라서 해시 테이블의 구현은 다음 두 가지 관점을 중점적으로 고려해야 한다.

  • 최대한 충돌이 적게 일어날 수 있는 해시 함수를 세워야 한다.
  • 결국 충돌은 일어나게 되므로 충돌이 일어날 때 이를 해결하기 위한 방법을 구현해야 한다.

3. 해시 함수의 설계

해시 함수의 설계를 할 때 고려해야 할 점은 얼마나 충돌이 적게 일어나는가이다.

충돌이 적게 일어난다는 말은, 해시 테이블 전체에서 해시 값이 고르게 도출(테이블 메모리에 데이터가 고르게 분포되어 저장)되는 것과 동치이다.

테이블에 데이터가 고르게 저장되지 않고 뭉쳐 있는 형태를 군집 형태(Cluster) 라 하며, 군집 형태가 구성되는 것을 군집화(Clustering) 라 한다.

결론적으로, 좋은 효율의(클러스터링을 최소화하는) 해시 함수를 구현하는 방법은 다음과 같이 알려져 있다.

  • 자릿수 선택(Digit Selection)
  • 자릿수 폴딩(Digit Folding)

3.1. 자릿수 선택(Digit Selection)

자릿수 선택 방법은 입력으로 주어진 임의의 길이의 키에서 특정한 자릿수의 값만을 추출해 이를 통해 해시 값을 도출하는 방법이다.

특정한 자릿수의 값을 추출한다는 말은 중복이 심하거나 불필요한 자릿수를 제외한다는 말과 같다.

앞서 든 예시처럼 학번의 경우, 앞 4자리는 입학연도를 의미하므로 동일 년도의 입학생들은 모두 같은 값을 가지게 된다. 이처럼 중복이 심한 값은 해시 함수에서 사용하지 않는 것이 효율 향상에 좋을 것이다.

또, 단순히 정수 자릿수의 관점에서 값을 추출하지 않고 비트 단위로 값을 추출하는 비트 추출 기법도 사용할 수 있다.

3.2. 자릿수 폴딩(Digit Folding)

Fold, 접는다는 단어에서 알 수 있듯이 자릿수 폴딩 방법은 주어진 키를 일정한 크기로 잘라 잘라진 각각의 자릿수를 겹쳐(연산하여) 해시 값을 도출하는 방법이다.

예를 들어 Key가

"abcd"

라면

이를 2Byte단위로 잘라

"ab", "cd"

잘라진 각 자리를 더한 결과를 해시값으로 사용하는 것이다.

int hashValue = "ab" + "cd";

이처럼 각 자릿수를 폴딩하는 과정에서도, 다양한 연산 규칙을 배합해 효율을 높일 수 있다.

예컨대, “abcd”와 “cdab”는 단순히 2Byte단위로 잘라서 더할 경우 충돌이 발생하지만, 자른 뒤 각 자릿수의 순서에 해당하는 정수를 곱한 후 그 값을 전부 더하면 충돌이 일어나지 않는 것을 볼 수 있다.

"ab"+"cd" == "cd"+"ab"	// collision!
    
"ab" * 2 + "cd" * 1 != "cd" * 2 + "ab" * 1	// OK.

폴딩을 위한 연산으로는 지금까지의 예시처럼 덧셈, 두 가지 이상의 연산 조합 외에도 XOR연산과 같은 비트 연산을 사용하는 등 매우 다양하다.

4. 충돌(Collision) 현상의 해결

아무리 좋은 해시 함수를 설계했다 하더라도 충돌 현상이 아예 발생하지 않을 수는 없으므로 충돌 현상이 발생할 때 이를 처리할 수 있어야 한다.

충돌 현상의 해결 방법은 크게 두 가지로 나눌 수 있다.

  • 개방 주소 기법(Open Addressing Method)
  • 폐쇄 주소 기법(Close Addressing Method)

주소의 개방/폐쇄가 의미하는 것은, 도출된 해시값에 대응되는 테이블의 위치에 이미 값이 저장되어 있을 경우(충돌이 발생한 경우) 최초의 해시값에 대응되는 자리를 고수할 것인지(폐쇄 주소 기법), 아니면 해시값에 대응되지 않지만 비어있는 다른 자리를 찾을 것인지(개방 주소 기법) 를 나타낸다.

쉽게 비유하면, 기존의 해시값에 해당하는 주소를 포기하고 다른 주소를 이용한다는 아이디어에 개방된 시각을 가진 방법인가?, 폐쇄적인 시각을 가진 방법인가? 라고 할 수 있다.

개방 주소 기법에는 다음과 같은 방법이 알려져 있다.

  • 선형 조사(Linear Probing)
  • 이차 조사(Quadratic Probing)
  • 이중 해시(Double Hash)

폐쇄 주소 기법에는 다음과 같은 방법이 알려져 있다.

  • 체이닝(Chaining)

4.1. 선형 조사(Linear Probing)

선형 조사(Linear Probing) 란, 충돌이 발생했을 때 그 옆자리부터 비어있는 자리를 선형적으로 조사하는 방법이다.

해시 값이 562일 때, 이미 562라는 값에 해당하는 테이블의 위치에 값이 저장되어 있다면

  • 562 + 1 = 563
  • 562 + 2 = 564
  • 562 + 3 = 565
  • …

처럼 한 칸씩 이동해 가며 비어있는 칸을 찾는 것이다.

4.2. 이차 조사(Quadratic Probing)

선형 조사의 경우 매우 간단하게 구현할 수 있지만 데이터가 연속적으로 저장될 수 밖에 없으며, 결국 클러스터링이 일어나게 된다.

이차 조사(Quadratic Probing) 는 선형 조사의 아이디어를 사용하되 한 칸씩 이동하는 것이 아닌 제곱수만큼 이동하며 비어있는 자리를 찾는 방식이다.

해시 값이 562일 때, 이미 562라는 값에 해당하는 테이블의 위치에 값이 저장되어 있다면

  • 562 + 1 * 1 = 563
  • 562 + 2 * 2 = 566
  • 562 + 3 * 3 = 571
  • …

처럼 비어있는 칸을 찾는 것이다.

선형 조사에 비해 데이터 간의 군집화가 적어진다는 장점이 있다.

4.3. 이중 해시(Double Hash)

이차 조사, 혹은 그 이상의 차원 조사를 이용한다 하더라도 조사 방식에 규칙성이 존재하기에 클러스터링이 발생할 수 밖에 없다.

이중 해시(Double Hash) 는 빈 위치를 조사하는 과정에서 규칙성을 최소화하기 위해 조사를 위한 해시 함수를 하나 더 사용하는 방법이다.

일반적으로 최초의 해시 값을 얻는 해시 함수를 1차 해시 함수라 하며, 충돌 시 새로운 위치를 찾기 위한 해시 함수를 2차 해시 함수라 한다.

만약 1차 해시 함수가 다음처럼 구현되어 있을 때

\[H_1 = k \,mod \,m\]

2차 해시 함수는 일반적으로 다음처럼 구현한다

\[H_2 = 1 + k \,mod \,c\]

(위 수식에서 c는 k보다 작은 소수인데, 이는 k보다 크게 되면 빈 자리를 찾기 위해 테이블 전체를 한 바퀴 돌 가능성이 생기며, 합성수가 아닌 소수를 이용할 경우 클러스터링 확률이 현저히 낮아진다는 결과가 알려져 있기 때문이다)

예를 들어 두 데이터의 해시 값이 모두 562일 때 이미 562라는 값에 해당하는 테이블의 위치에 값이 저장되어 있고, 2차 해시 함수의 결과가 각각 3, 7이라면

  • 562 + 3 * 1 = 565 // 562 + 7 * 1 = 569
  • 562 + 3 * 2 = 568 // 562 + 7 * 2 = 576
  • 562 + 3 * 3 = 571 // 562 + 7 * 3 = 583
  • …

처럼 비어있는 칸을 찾는 것이다.

이중 해시의 경우 1차 해시함수로부터 도출된 해시값이 같다 하더라도 2차 해시값에 따라 조사 방식이 다르기 때문에 분포가 불규칙적이게 되고, 이 결과 클러스터링이 최소화된다는 장점이 존재한다.

4.4. 개방 주소 기법의 공통 아이디어

개방 주소 기법의 경우 클러스터링의 관점만 놓고 보면 이중 해시가 가장 우수하고 그 뒤를 이어 이차 조사와 선형 조사가 우수한 것 처럼 보이지만, 오히려 선형 조사와 같이 데이터의 연속성이 보장되도록 충돌 처리를 할 경우 캐시 메모리를 활용할 수 있다는 의외의 장점이 존재한다.

또한, 모든 충돌 기법은 충돌 검사를 위해 테이블의 각 자리마다 그 상태를 알 수 있어야 하며, 아래 세 가지 상태로 분류한다.

  • 비어 있음(Empty)
  • 저장됨(In-use)
  • 삭제됨(Deleted)

이 중 삭제됨 상태가 필요한 이유는, 해당 자리의 데이터가 삭제되기 전에 개방 조사법을 통해 다른 자리에 값을 저장해 놓았을 경우 데이터가 삭제된 이후라도 동일 키값을 가지는 데이터가 다른 자리에 존재함을 알려야 하기 때문이다.

4.5. 체이닝(Chaining)

폐쇄 주소 기법은 충돌이 일어나더라도 다른 자리를 찾지 않고, 그 자리를 고수한다. 그러나 한 자리에는 오직 하나의 데이터만이 저장될 수 있으므로 여러 데이터를 한 자리에 저장하기 위해 추가적인 자료 구조를 이용한다.

체이닝(Chaining) 은 각 자리별로 여러 데이터를 연결 리스트의 형태로 저장하는 방법이다.

새로운 자리를 찾지 않고 지정된 자리에 데이터를 저장할 수 있다는 장점이 있지만, 추후 데이터를 찾을 때 연결 리스트의 탐색이 필요하여 리스트의 크기가 클 수록 효율이 저하된다는 단점이 있다(연결 리스트의 탐색 속도는 O(N)이기 때문이다).

5. 결론

해시 테이블은 이상적인 경우 데이터의 탐색 속도가 O(1)이라는 매우 좋은 효율을 보이지만, 클러스터링에 비례해 성능 저하가 일어나게 된다.

일반적으로 해시 테이블은 70% 이상의 용량에 데이터가 저장될 경우 효율 저하가 일어나는 것으로 알려져 있다.

따라서 데이터가 매우 많아질 경우 해시 테이블보다 균형 이진탐색트리(O(logN))를 이용하는 것이 효율적일 수 있다.

C++의 경우, 이와 같은 테이블 구조의 데이터 저장을 위한 STL로 std::map과 std::unordered_map이 있다.

std::map의 경우 균형 이진 트리(red-black tree)를 이용해 구현되어 있으며, std::unordered_map의 경우 해시 테이블로 구현되어 있다.