C++로 쉽게 풀어쓴 자료구조/ 탐색

탐색이란?

컴퓨터 프로그램에서 탐색은 하나 이상의 필드(field)로 구성되는 레코드(record)의 집합에서 원하는 레코드를 찾아내는 작업이다. 보통 이러한 레코드들의 집합을 테이블(table)이라 부른다. 레코드들은 서로 중복되지 않고 고유한 값을 가지는 키를 가지는데, 이것을 탐색키(search key)라 부른다.

맵이란?

맵은 탐색을 위한 자료구조이다. 맵(map) 또는 사전(dictionary)은 자료를 저장하고 키를 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 자료구조를 말한다. 맵은 키를 가진 레코드(keyed record) 또는 엔트리(entry)라 불리는 키-값 쌍(key, value)을 테이블에 저장한다. 이때 각 키는 유일하고 맵에 저장되는 키와 값은 어떠한 자료형도 가능하다.

키를 가진 레코드의 추상 자료형은 다음과 같다.

  • 객체
    • 키(key)와 값(value)을 가진 요소 (key, value)의 집합
  • 연산
    • create(key, value): 주어진 key와 value를 각각 키와 값으로 갖는 레코드를 생성한다.
    • getKey(): 레코드의 키를 반환한다.
    • getValue(): 레코드의 값을 반환한다.
    • update(value): 레코드의 값을 value로 변경한다.

맵의 추상 자료형은 다음과 같다.

  • 객체
    • 유일한 키를 가진 엔트리(키를 가진 레코드)의 집합
  • 연산
    • create(): 공백 상태의 맵을 생성한다.
    • search(key): 테이블에서 주어진 탐색키 key를 가진 레코드를 찾아 반환한다.
    • insert(entry): 테이블에서 주어진 entry를 삽입한다.
    • delete(key): 테이블에서 주어진 탐색키 key를 가진 레코드를 찾아 삭제한다.
    • count(): 테이블의 모든 레코드 수를 반환한다.

맵을 구현하는 가장 간단한 방법은 배열일 것이다. 그러나 맵의 탐색 성능을 향상하고자 한다면 이진 탐색 트리와 같은 보다 효율적인 자료구조를 사용해야 한다.

정렬되지 않은 배열에서의 탐색

순차 탐색

만약 배열을 이용해 맵을 구현하고 배열을 정렬하지 않으면 순차 탐색 방법을 사용할 수 있다. 순차 탐색(sequential search)은 가장 간단하고 직접적인 탐색 방법이다. 순차 탐색은 정렬되지 않은 배열에서 탐색키를 찾을 수 있는데, 배열의 요소들을 처음부터 마지막까지 하나씩 검사하여 원하는 레코드를 찾는 방법이다. 순차 탐색의 시간 복잡도는 O(n)이 된다.

정렬된 배열에서의 탐색

정렬된 배열에서의 개선된 순차 탐색

정렬된 리스트를 순차 탐색할 경우 비교 횟수는 배열에 해당 항목이 존재하여 탐색이 성공했을 경우에는 일반 순차 탐색과 동일하지만, 해당 항목이 리스트에 존재하지 않아서 탐색이 실패할 경우에는 비교 횟수가 반으로 줄어든다. 그러나 시간 복잡도의 차수는 원래 순차 탐색과 동일하게 O(n)으로 변함이 없다.

정렬된 배열에서의 이진 탐색

정렬된 배열의 탐색에는 이진 탐색(binary search)이 적용될 수 있다. 이 방법은 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 부분 배열에 있는지 오른쪽 부분 배열에 있는지를 판단하고 다음 단계의 탐색 범위를 반으로 줄인다. 따라서 매 단계에서 검색해야 할 리스트의 크기가 반으로 줄어든다.

이진 탐색은 탐색 범위가 급격히 줄어들지만, 이진 탐색을 적용하려면 탐색하기 전에 반드시 배열이 정렬되어 있어야 한다. 따라서 이진 탐색은 데이터의 삽입이나 삭제가 빈번한 경우에는 적합하지 않다.

search_binary(list, low, high, key)
    middle <- low에서 high 사이의 중간 위치
    if 탐색값 = list[middle]
        return middle;
    else if 탐색값 < list[middle]
        return search_binary(list, low, middle-1, key);
    else if 탐색값 > list[middle]
        return search_binary(list, middle+1, high, key);
    return -1;

이진 탐색은 탐색을 반복 할 때마다 탐색 범위를 반으로 줄인다. 이러한 탐색 범위가 더 줄일 수 없는 1이 될 때의 탐색 횟수를 k라 하면, n/2k = 1 이므로 k = log2n임을 알 수 있다. 결국 이진 탐색의 시간 복잡도는 O(log2n)이 된다.

색인 순차 탐색

색인 순차 탐색(indexed sequential search) 방법은 인덱스(index)라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법이다. 인덱스 테이블을 주 자료 리스트에서 일정 간격으로 발췌한 자료를 가지고 있다. 인덱스 테이블에 m개의 항목이 있고, 주 자료 리스트의 데이터 수가 n이면 각 인덱스 항목은 주 자료 리스트의 각 n/m 번째 데이터를 가지고 있다. 이때 주 자료 리스트와 인덱스 테이블은 모두 정렬되어 있어야 한다.

색인 순차 탐색 알고리즘은 그림 14.6에서 보듯이 우선 인덱스 테이블에서 index[i] <= key < index[i+1]을 만족하는 항목을 찾는다. 해당하는 항목을 찾으면 주 자료 테이블에서 해당 범위의 항목들에 대해서만 검색하면 된다. 이 방법은 주 자료 리스트에서의 탐색 식나을 상당히 줄일 수 있으므로 파일 처리, 데이터베이스 등의 응용 분야에서 많이 사용하는 방법이다.

색인 순차 탐색 알고리즘의 탐색 성능은 인덱스 테이블의 크기에 좌우된다. 인덱스 테이블의 크기를 줄이면 주자료 리스트에서의 탐색 시간을 증가시키고, 인덱스 테이블의 크기를 크게 하면 인덱스 테이블의 탐색 시간을 증가시킨다. 인덱스 테이블의 크기를 m이라 하고 주자료 리스트의 크기를 n이라 하면 색인 순차 탐색의 복잡도는 O(m+n/m)와 같다.

보간 탐색

보간 탐색(interpolation search)은 사전이나 전화번호부를 탐색하는 방법과 같이 탐색키가 존재할 위치를 예측하여 탐색하는 방법이다. 이는 우리가 사전을 찾을 때 ‘ㅎ’으로 시작하는 단어는 사전의 뒷부분에서 찾고 ‘ㄱ’으로 시작한느 단어는 앞부분에서 찾는 것과 같은 원리이다. 보간 탐색은 이진 탐색과 유사하나 리스트를 반으로 분할하지 않고 불균등하게 분할하여 탐색한다.

이진 탐색에서 탐색 위치는 항상 (low+high)/2 이나, 보간 탐색에서는 찾고자하는 키값과 현재의 low, high 위치의 값을 고려하여 다음과 같이 다음 탐색 위치를 결정한다.

탐색 위치 = (k - list[low]) / (list[high] - list[low]) x (high- low) + low

여기서 k는 찾고자 하는 키값을, low와 high는 각각 탐색할 범위의 최소, 최대 인덱스 값을 나타낸다. 이 식은 다음 그림과 같이 탐색 값과 위치는 비례한다는 가정에서 탐색 위치를 결정할 때 찾고자 하는 키 값이 있는 곳에 근접하도록 가중치를 주는 방법이다.

예컨대 14.8과 같은 리스트에서 탐색키가 55일 경우 위 식에 의해 계산된 탐색위치는 5가 된다.

보간 탐색은 이진 탐색과 같은 O(log2n)의 시간 복잡도를 가지지만 많은 데이터가 비교적 균등하게 분포되어 있는 자료의 경우 훨씬 효율적인 방법이 된다.

균형 이진 탐색 트리

맵은 이진 탐색 트리로도 구현할 수 있다. 이진 탐색에서 자료는 배열에 저장되어 있으므로 삽입과 삭제가 상당히 힘들다. 즉, 맵에 자료를 삽입하거나 삭제할 때 불필요한 항목들의 많은 이동이 필요하다. 반면에 맵을 이진 탐색 트리로 구현하면 O(log2n) 시간에 삽입과 삭제가 가능하다. 따라서 삽입과 삭제가 빈번히 이루어진다면 반드시 이진 탐색 트리를 사용하여야 한다.

이진 탐색트리는 균형 트리면 O(log2n)의 탐색 연산 시간 복잡도를 갖는다. 만약 경사 트리인 경우라면 탐색의 시간 복잡도가 O(n)으로 높아지게 된다.

따라서 이진 탐색 트리에서는 균형을 유지하는 것이 무엇보다 중요하다. 이것은 상당히 복잡하기 때문에 모든 주제를 다루지는 않고 여기서는 AVL 트리에 대해서만 알아본다. 트리에 정수가 저장된다고 가정하자.

AVL 트리

AVL 트리는 Adelson-Velskii와 Landis에 의해 제안된 트리로 각 노드에서 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1이하인 이진 탐색 트리를 말한다. 이 트리는 비균형 상태가 되면 스스로 노드들을 재배치하여 균형 상태로 만든다. AVL 트리는 항상 균형 트리를 보장하기 떄문에 O(log2n)의 탐색 시간을 보장한다. 삽입과 삭제 연산도 O(log2n) 시간 안에 할 수 있다.

그림 14.10에서 (a)는 모든 노드에서 양쪽 서브트리의 높이 차이가 1이하이다. 그러나 (b)는 노드 7에서 왼쪽 서브트리의 높이가 3인 반면 오른쪽 서브트리의 높이가 1이므로 균형을 이루지 못하고 따라서 AVL 트리가 아니다.

먼저 균형 인수(balance factor)를 정의하자. 균형 인수는 (왼쪽 서브트리의 높이 – 오른쪽 서브트리의 높이)로 정의되는데, 모든 노드의 균형 인수가 ±1 이하이면 AVL 트리이다. 그림 14.10에서 각 노드 옆의 숫자가 균형 인수를 보여주고 있다.

AVL 트리의 삽입 연산

이진 탐색 트리에서 노드가 삽입되면 삽입되는 위치에서 루트까지의 경로에 있는 모든 조상 노드들의 균형 인수가 영향을 받는다. 따라서 불균형 상태로 변한 가장 가까운 조상 노드의 서브트리들에 대하여 다시 균형을 잡아야 한다. 그 외의 다른 노드들은 변경할 필요가 없다. 예컨대 균형을 이룬 AVL 트리인 그림 14.11 (a)에 1을 삽입하면 트리는 (b)처럼 균형이 깨지게 된다. 따라서 균형이 깨진 가장 가까운 조상 노드인 5를 루트로 하는 서브트리의 노드들을 재배치하여 균형 상태로 만들어야 한다.

균형이 깨진 트리를 균형있게 만드는 방법은 서브트리를 회전시키는 것이다. 노드 1, 3, 5를 오른쪽으로 회전시키면 그림 14.12처럼 되어서 다시 균형 트리가 된다. 다른 노드들은 변경시키지 않음을 유의하라. 물론 이진 탐색 트리 조건을 만족한다.

AVL 트리에서 균형이 깨지는 경우는 다음의 4가지 타입이 있다. 새로 삽입된 노드 N으로부터 가장 가까우면서 균형 인수가 ±2가 된 조상 노드를 A라 하자.

  • LL 타입: N이 A의 왼쪽 서브트리의 왼쪽 서브트리에 삽입 된다.
  • LR 타입: N이 A의 왼쪽 서브트리의 오른쪽 서브트리에 삽입 된다.
  • RR 타입: N이 A의 오른쪽 서브트리의 오른쪽 서브트리에 삽입 된다.
  • RL 타입: N이 A의 오른쪽 서브트리의 왼쪽 서브트리에 삽입 된다.

LL과 RR은 대칭이고 LR과 RL도 대칭이다. 다음은 각각의 경우에 대하여 균형 트리로 다시 만드는 방법이다.

  • LL 회전: A부터 N까지의 경로상의 노드들을 오른쪽으로 회전시킨다.
  • LR 회전: A부터 N까지의 경로상의 노드들을 왼쪽-오른쪽으로 회전시킨다.
  • RR 회전: A부터 N까지의 경로상의 노드들을 왼쪽쪽으로 회전시킨다.
  • RL 회전: A부터 N까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전시킨다.

한번만 회전 시키는 것을 단순 회전(single rotation)이라 하는데, 이 경우 탐색 순서를 유지하면서 부모와 자식의 위치를 교환하면 된다. LL과 RR 회전이 이 경우에 속한다. 두 번의 회전이 필요한 경우 이중 회전(double rotation)이라 하며 LR과 RL 회전이 여기에 속한다.

LL 회전

그림 14.13은 LL 타입의 경우로 6, 5, 2 순으로 노드를 삽입했을 때 만들어진다. 노드 6은 균형 인수가 2로서 불균형하다. 그러나 만약 그림과 같이 6과 5를 바꾸면 다시 균형 트리를 만들 수 있다.

LL 회전을 보다 일반적인 경우로 정리해 보자. 일반적인 LL 타입은 조상 노드 A의 왼쪽 서브트리의 왼쪽 서브트리에 노드가 추가됨으로 해서 발생한다. LL 회전은 그림 14.16처럼 오른쪽으로 회전 시키면 된다.

RR 회전

그림 14.15는 왼쪽 회전의 경우로 6, 8, 9 순으로 노드를 삽입했을 경우 만들어진다. 마찬가지로 트리를 왼쪽으로 한번 회전하면 균형트리로 만들 수 있다. 여기서 회전한다는 의미는 부모 노드와 자식 노드를 바꾼다는 것이다.

RR 타입은 조상 노드 A의 오른쪽 서브트리의 오른쪽 서브트리에 노드가 추가됨으로 해서 발생한다. 일반적인 경우의 RR 타입은 그림 14.16처럼 노드 A와 B의 위치를 바꾸어 주고 서브트리들을 그림처럼 정리하면 균형 트리로 만들 수 있다.

LL 회전과 RR 회전을 알고리즘으로 만들면 다음과 같다.

rotate_LL(A)
    B <- A의 왼쪽 자식
    B의 오른쪽 자식을 A의 왼쪽 자식으로 만든다.
    A를 B의 오른쪽 자식 노드로 만든다.

rotate_RR(A)
    B <- A의 오른쪽 자식
    B의 왼쪽 자식을 A의 오른쪽 자식으로 만든다.
    A를 B의 왼쪽 자식 노드로 만든다.

RL 회전

RL 타입은 조상 노드 A의 오른쪽 서브트리의 왼쪽 서브트리에 노드가 추가됨으로 해서 발생한다. RL 회전은 균형 트리를 만들기 위하여 2번의 회전이 필요하다. RL 회전은 LL 회전을 한 다음, RR 회전을 하면 된다.

LR 회전

LR 타입은 조상 노드 A의 왼쪽 서브트리의 오른쪽 서브트리에 노드가 추가됨으로 해서 발생한다. LR 회전은 균형 트리를 만들기 위해 2번의 회전이 필요한데, RR 회전을 한 다음 LL 회전을 하면 된다.

RL 회전과 LR 회전을 알고리즘으로 만들면 다음과 같다.

rotate_RL(A)
    B <- A의 오른쪽 자식
    rotate_LL(B)가 반환하는 노드를 A의 오른쪽 자식으로 만든다.
    rotate_RR(A)

rotate_LR(A)
    B <- A의 왼쪽 자식
    rotate_RR(B)가 반환하는 노드를 A의 왼쪽 자식으로 만든다.
    rotate_LL(A)

해싱을 이용한 탐색

지금까지 맵을 구현하기 위한 방법들의 최고 성능은 시간 복잡도가 O(log n)이었다. 그러나 해싱을 이용하여 맵을 구현하면 탐색 연산의 이론적인 시간 복잡도가 O(1)이 된다.

해싱이란?

해싱은 키 값을 비교하는 것이 아니라 탐색키에 산술적인 연산을 적용하여 항목이 저장되어 있는 위치, 즉 인덱스를 직접 계산하는 방식이다. 이렇게 키값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(hash table)이라 하며 해시 테이블을 이용한 탐색을 해싱(hashing)이라 한다.

탐색키들이 1-100사이의 정수라 할 때 가장 빠르게 자료를 저장하고 꺼낼 수 있는 방법은 1000개의 요소를 가지는 배열을 만드는 것이다. 이 경우 연산은 O(1)이 되는데, 이것이 해싱의 기본 아이디어이다.

현실적으로는 탐색키들이 문자열이거나 굉장히 큰 숫자이기 때문에 탐색키를 직접적으로 배열의 인덱스로 사용하지 못하고 각 탐색키를 작은 정수로 사상(mapping) 시키는 어떤 함수가 필요한데, 이것을 해시 함수(hash function)이라 한다. 해시 함수는 탐색키를 입력 받아 해시 주소(hash address)를 계산하는데, 삽입이나 삭제, 탐색 연산은 모두 이 주소에서 이루어진다.

그림 14.20은 해싱의 구조를 보여준다. 키값 k를 입력받아 해시 함수로 연산한 결과인 해시 주소 h(k)를 인덱스로 사용하여 해시 테이블에 있는 항목에 접근한다. 해시 테이블 ht는 M개의 버켓(bucket)으로 이루어지는 테이블이고, 하나의 버켓에는 각각 레코드를 저장할 수 있는 여러 개의 슬롯(slot)을 가진다. 이것은 여러 개의 탐색키가 동일한 해시 주소로 변환될 수 있기 때문인데, 여기서는 슬롯이 하나라고 생각하자.

해시 테이블의 버켓의 수가 제한적이므로 경우에 따라 서로 다른 키 k1과 k2가 해시함수에 의해 같은 주소, 즉 h(k1) == h(k2)로 계산되는 상황이 발생한다. 이것을 충돌(collision)이라 하고, 이러한 키 k1과 k2를 동의어(synonym)라 한다.

충돌이 발생하면 어떻게 할까? 만약 버켓에 여러 개의 슬롯이 있다면 k1과 k2를 각각 다른 슬롯에 저장하면 된다. 그러나 충돌이 슬롯 수보다 더 많이 발생할 수도 있는데, 이러한 상황을 오버플로우(overflow)라고 한다. 이 경우 해당 버켓에 더 이상 항목을 저장할 수 없게 되므로 해싱에서는 오버플로우를 해결하기 위한 방법이 반드시 피룡하다.

이상적인 해싱과 실제의 해싱

충돌이 절대 일어나지 않는 경우가 가장 이상적인 해싱이지만, 테이블 크기를 키우는 방법은 용량을 많이 먹는 문제가 있다.

간단하면서도 강력한 방법은 나머지 연산을 이용하는 방법이다. 탐색키 i를 해시 테이블 크기 M으로 나누어서 나머지를 취하면 된다. 물론 이 경우도 같은 값이 나올 가능성은 존재하기 떄문에 완벽한 해결책은 아니다. 실제의 해싱에서는 충돌과 오버플로우가 빈번하게 발생하므로 시간 복잡도는 이상적인 경우의 O(1) 보다는 떨어지게 된다.

해시 함수

좋은 해시 함수의 조건은 다음의 3가지이다.

  • 충돌이 적어야 한다.
  • 해시 함수 값이 해시 테이블 주소 영역 내에서 고르게 분포되어야 한다.
  • 계산이 빨라야 한다.

제산 함수

가장 일반적인 방법이 나머지 연산자 mod를 사용하는 것이다. 테이블의 크기가 M일 때 탐색키 k에 대하여 해시 함수는 다음과 같다.

h(k) = k mod M

이때 가능하면 해시 주소를 더 고르게 분포시키기 위해 해시 테이블의 크기 M은 소수(prime number)를 선택한다. 즉, 1과 자기 자신만을 약수로 가지는 수라면 K mod M은 0에서 M-1을 골고루 사용하는 값을 만들어낸다.

폴딩 함수

폴딩 함수는 주로 탐색키가 해시 테이블의 크기보다 더 큰 정수일 경우에 사용된다. 예컨대 탐색키는 32비트이고 해시 테이블의 인덱스는 16비트 정수인 경우이다. 만약 이런 경우 탐색키의 앞의 16비트를 무시하고 뒤의 16비트를 해시코드로 사용한다면 충돌이 발생할 것이다. 따라서 탐색키의 일부만 사용하는 것이 아니고 탐색키를 몇 개의 부분으로 나누어 이를 더하거나 비트별로 XOR 같은 부울 연산을 하는 것이 보다 좋은 방법이다. 이것을 폴딩(folding)이라고 한다. 예컨대 32비트 키를 2개의 16비트로 나누어 비트별로 XOR 연산을 하는 코드는 다음과 같다.

hash_index = (short)(key ^ (key >> 16))

폴딩 함수는 탐색키를 여러 부분으로 나누어 모두 더한 값을 해시 주소로 사용한다. 탐색키를 나누고 더하는 방법에는 이동 폴딩(shift folding)과 경계 폴딩(boundary folding)이 대표적이다. 이동 폴딩은 탐색키를 여러 부분으로 나눈 값들을 더하고, 경계 폴딩은 이웃한 부분을 거꾸로 더해 해시 주소를 얻는다.

중간 제곱 함수

중간 제곱 함수는 탐색키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소를 생성한다. 제곱한 값의 중간 비트들은 대개 탐색키의 모든 문자들과 관련이 있기 때문에 서로 다른 탐색키는 몇 개의 문자가 같을지라도 서로 다른 해싱 주소를 갖게 된다. 탐색키 값을 제곱한 값의 중간 비트들의 값은 비교적 고르게 분산된다.

비트 추출 방법

해시 테이블의 크기가 M=2k일 때 탐색키를 이진수로 간주하여 임의의 위치으 k개의 비트를 해시 주소로 사용하는 것이다. 이 방법은 아주 간단하지만 탐색키의 일부 정보만을 사용하므로 해시 주소의 집중 현상이 일어날 가능성이 높다.

숫자 분석 방법

이 방법은 숫자로 구성된 키에서 각 위치마다 수의 특징을 미리 알고 있을 때 유용하다. 키의 각각의 위치에 있는 숫자 중에서 편중되지 않는 수들을 해시 테이블의 크기에 적합한만큼 조합하여 해시 주소로 사용하는 방법이다. 예컨대 학생의 학번이 201512345라 한다면 입학년도를 의미하는 앞의 4자리수는 편중되어 있으므로 가급적 사용하지 않고 나머지 수를 조합하여 해시 주소로 사용한다.

탐색키가 문자열인 경우

탐색키가 문자열인 경우는 보통 각 문자에 정수를 대응시켜 바꾸게 된다. 예컨대 ‘a’부터 ‘z’에 1부터 26을 할당할 수도 있고, 각 문자의 아스키 코드나 유니코드 값을 그대로 이용할 수 있다.

해싱의 오버플로우 처리 방법

해싱에서 오버플로우를 잘 처리하는 것은 매우 중요하다. 이러한 오버플로우를 처리하는 방법은 다음의 2가지로 나눌 수 있다.

  1. 선형 조사법(linear probing): 충돌이 일어나면 해시 테입르의 다른 위치에 찾아 항목을 저장한다.
  2. 체이닝(chaining): 해시 테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시 테이블의 구조를 변경한다.

선형 조사법

선형 조사법(linear probing)은 해싱 함수로 구한 버켓에 빈 슬롯이 없으면 그 다음 버켓에서 빈 슬롯이 있는지를 찾는 방법이다. 이때 비어 있는 공간을 찾는 것을 조사(probing)이라고 하는데, 여러 가지의 조사 방법이 가능하다.

만약 ht[k]에서 충돌이 발생했다고 하자. 선형 조사법은 먼저 ht[k+1]이 비어 있는지를 살핀다. 비어있지 않다면 다음 위치인 ht[k+2]를 살펴보는데, 이런 식으로 비어있는 공간이 나올 때까지 계속하는 조사 방법이다. 만약 테이블의 끝에 도달하게 되면 다시 테이블의 처음으로 간다. 처음 충돌이 났던 곳으로 다시 돌아오면 테이블이 가득 찬 것이 된다. 따라서 조사되는 위치는 다음과 같은 순서이다.

h(k), h(k)+1, h(k)+2, h(k)+3, ... mod M

크기가 7인 해시 테이블에서 해시 함수로 h(k) = k mod 7을 사용한다고 가정하고 8, 1, 9, 6, 13의 순으로 탐색키를 저장해보자. 아래에서 살펴본 바와 같이 선형 조사법은 오버플로우가 발생하면 항목의 저장을 위하여 빈 버켓을 순차적으로 탐색해 나간다.

  1. 8저장: h(8) = 8 mod 7 = 1 (저장)
  2. 1저장: h(1) = 1 mod 7 = 1 (충돌) => (h(1)+1) mod 7 = 2 (저장)
  3. 9저장: h(9) = 9 mod 7 = 2 (충돌) => (h(9)+1) mod 7 = 3 (저장)
  4. 6저장: h(6) = 6 mod 7 = 6 (저장)
  5. 13저장: h(13) = 13 mod 7 = 6 (충돌) => (h(13)+1) mod 7 = 0 (저장)

선형 조사법의 경우 한번 충돌이 발생한 위치에서 항목들이 집중되는 현상이 나타나는데 이를 군집화(clustering) 현상이라고 한다.

선형 조사법의 삭제 연산

선형 조사법은 간단하다는 장점이 있으나 오버플로우가 자주 발생하면 군집화 현상에 따라 탐색의 효율이 크게 저하될 수 있다. 또 항목을 삭제되면 탐색이 불가능해질 수가 있다. 이 문제를 해결하려면 버ㅔㅅ을 몇가지로 분류해야 한다. 즉, 한 번도 사용하지 않은 버켓과 사용은 되었지만 현재는 비어 있는 버켓, 현재 사용 중인 버켓으로 분류하여야 한다. 탐색 함수에서는 한 번도 사용이 안 된 버켓을 만나야만 탐색이 중단되도록 하여야 한다.

이차 조사법

이차 조사법(quadratic probing)은 선형 조사법과 유사하지만, 충돌 발생시 다음에 조사할 위치를 다음 식에 의하여 결정한다.

(h(k) + i*i) mod M for i = 0, 1, ... M-1

따라서 조사되는 위치는 다음과 같이 된다.

h(k), h(k)+1, h(k)+4, h(k)+9, ... mod M

여기서 주의할 것은 모든 위치를 조사하게 만들려면 여전히 테이블 크기는 소수여야 한다는 점이다. 이 방법은 선형 조사법에서의 문제점인 군집화 현상을 크게 완화시킬 수 있다.

이중 해싱법

이중 해싱법(double hashing) 또는 재해싱(rehashing)은 오버플로우가 발생함에 따라 항목을 저장할 다음 위치를 결정할 때, 원래 해시 함수와 다른 별개의 해시 함수를 이용하는 방법이다. 이 방법은 항목들을 해시 테이블에 보다 균일하게 분포시킬 수 있으므로 효과적이다.

이중 해싱법에서는 탐색키를 참조하여 더해지는 값이 결정된다. 따라서 해시 함수값이 같더라도 탐색키가 다르면 서로 다른 조사 순서를 갖는다. 따라서 이중 해싱법은 이차 집중을 피할 수 있다.

두 번째 해시 함수는 조사 간격을 결정하게 된다. 일반적인 형태는 다음과 같다.

step = C - (k mod C) = 1 + k mod C

이런 형태의 함수는 [1..C] 사이의 값을 생성한다.

충돌이 발생했을 경우 조사되는 위치는 다음과 같다.

h(k), h(k) + step, h(k) + 2*step, h(k) + 3*step ... mod M

C는 보통 테이블의 크기인 M 보다 약간 작은 소수이다. 이중 해싱에서는 보통 집중 현상이 매우 드물다. 왜냐하면 같은 버켓과 같은 탐색 순서를 가지는 요소들이 거의 없기 때문이다.

체이닝

체이닝은 하나의 버켓에 여러 개의 레코드를 저장할 수 있도록 하는 방법이다. 버켓은 여러 가지 방법으로 구현될 수 있겠지만 젖아할 항목의 수를 예측할 수 없으므로 연결 리스트로 구현하는 것이 적절할 것이다. 이와 같은 오버플로우 해결 방법을 체이닝(chaining)이라고 한다.

다음은 크기가 7인 해시 테이블에 h(k) = k mod 7의 해시 함수를 이용하여 8, 1, 9, 6, 13을 삽입할 때의 체이닝에 의한 충돌 처리를 보여준다.

  1. 8 저장: h(8) = 8 mod 7 = 1 (저장)
  2. 1 저장: h(1) = 1 mod 7 = 1 (충돌) => 새로운 노드 생성 및 저장
  3. 9 저장: h(9) = 9 mod 7 = 2 (저장)
  4. 6 저장: h(6) = 6 mod 7 = 6 (저장)
  5. 13 저장: h(13) = 13 mod 7 = 6 (충돌) => 새로운 노드 생성 및 저장

해싱의 성능 분석

해싱의 시간 복잡도는 O(1)이다. 그러나 이것은 충돌이 전혀 일어나지 않는 상황에서만 가능하고 실제 해싱의 탐색 연산은 O(1) 보다는 느리다.

해싱의 성능을 분석하기 위해 해시 테이블이 얼마나 채워져 있는지를 나타내는 적재 밀도(loading density) 또는 적재 비율(loading factor)을 다음과 같이 정의한다.

a = 저장된 항목의 개수 / 해싱 테이블의 버켓의 개수 = n / M

기존의 연구 결과들을 바탕으로 해싱을 정리해보자. 선형 조사법은 적재 밀도를 0.5 이하로 유지해야 한다. 이차 조사법과 이중 해싱법에서는 적재 밀도를 0.7 이하로 유지시키는 것이 좋다고 한다. 체인법은 적재 밀도에 비례하는 성능을 보인다.

해싱과 다른 탐색 방법의 비교

탐색 방법 탐색 삽입 삭제
순차 탐색 O(n) O(1) O(n)
이진 탐색 O(log2n) O(log2n+n) O(log2n+n)
이진 탐색 트리 – 균형 트리 O(log2n) O(log2n) O(log2n)
이진 탐색 트리 – 경사 트리 O(n) O(n) O(n)
해싱 – 최선의 경우 O(1) O(1) O(1)
해싱 – 최악의 경우 O(n) O(n)  O(n)
[ssba]

The author

지성을 추구하는 디자이너/ suyeongpark@abyne.com

댓글 남기기

This site uses Akismet to reduce spam. Learn how your comment data is processed.