13. 자료구조론 - Hashing

Hashing

해시 테이블은 특정 값을 삽입, 삭제, 탐색하는 것을 상수시간 내에 할 수 있게 해주는 자료구조입니다.

해시 테이블은 고정된 사이즈의 배열로 이루어져있고, 키값이 주어지면 해시 함수를 통해 배열의 인덱스로 맵핑됩니다.

이렇게 해시함수를 이용해 임의의 범위의 키값을 일정 범위 안으로 맵핑시켜 배열에 들어가도록 할 수 있습니다.

하지만 다른 키 값이더라도 해시함수에 통과시켰을 때 같은 값이 도출될 수 있는데, 이 경우 collision이 발생했다고 합니다.

 

Collision의 해결

Collision을 해결하는 대표적인 두가지 방법이 있습니다.

• Separate chaining : 같은 인덱스로 맵핑되는 모든 키에 대한 값들을 리스트로 연결해두는 방법
• Open addressing : 키가 충돌하면 다른 빈 슬롯을 찾아 넣는 방법

Seperate Chaining (Open hashing)

위와 같이 해시함수를 적용했을 때, 해시 테이블의 같은 슬롯으로 맵핑되는 키값들을 리스트로 달아두는 방법이다.

이 방법을 쓰면 해시테이블의 슬롯에는 값이 들어가는게 아니라, 링크드리스트 헤더의 주소가 들어간다.

 

구현은 간단하게 다음과 같다.

typedef struct Node* List;
struct Node {
    ElementType element;
    Position next;
};
struct HashTable {
    int size;
    List* lists;
}

Node* Find(int key, HashTable hash_table) {
	Node* node;
    List list;
    
    list = hash_table->lists[HashFunc(key)];
    node = list->next;
    
    while (node != NULL && node->element != key) 
    	node = node->next;
        
    return node;
}

void Insert(int key, HashTable hash_table) {
	Node* node, new_node;
    List list;
    node = Find(key, hash_table);
    
    if (node == NULL) {
    	new_node = new Node();
        new_node->element = key;
        list = hash_table->lists[HashFunc(key)];
        new_node->next = list->next;
        list->next = new_node;
    }
}

이 방법은 해시테이블의 각 슬롯에 링크드리스트를 생성하기 때문에 다음 노드를 가리키는 포인터와 각 노드마다 생성되는 노드객체 등 추가적인 메모리가 필요하다는 단점이 있다.

Open addressing (Closed hashing)

이 방식에서는 해시테이블 각 슬롯에 리스트의 포인터 등이 아닌 값이 직접 들어간다. collision이 발생하면 일정한 규칙에 따라 해당 위치가 아닌 다른 빈 위치를 찾아간다.

처음에는 H0(key)에서 나온 인덱스로 갔다가, 해당 칸이 이미 차있다면 H1(key)를 통해 나온 인덱스로 찾아간다. 거기서도 collision이 발생한다면 다음 인덱스를 찾아가는 식을 반복한다. 

이 때 H_i(key) = (Hash(key) + F(i)) mod m (m은 해시테이블의 사이즈) 으로 나타낼 수 있고, F(i)는 collision 을 해결하기 위한 새로운 함수이다.

F(i)에 사용하는 함수 중 대표적인 두가지 방식이 있다.

• Linear probing : F(i) = i 인 linear 함수이다. 이 경우 Hash(key)가 실패하면 Hash(key) + 1, Hash(key) + 2...를 차례로 시도한다. 즉 collision이 발생하면 계속해서 바로 다음 칸으로 가 다시 시도하는 것이다.

• Quadratic probing : F(i) = i^2인 quadratic 함수이다. 이 경우 Hash(key)가 실패하면 Hash(key) + 1, Hash(key) + 4...를 차례로 시도한다. Linear probing보다 더 크게 건너뛰며 다음 칸을 찾아보는 방식이다.

Linear probing의 문제점

Linear probing처럼 순차적으로 다음 슬롯을 탐색하는 방법에는 다음과 같은 문제점이 있다.

• Primary clustering : 값이 연속적으로 저장되어있는 덩어리인 클러스터 내의 값으로 해시되는 키들은 collision을 해결하기 위해 여러번 시도해야하고, 빈 자리를 찾아 들어가면 그 키 또한 클러스터의 일부가 되어서 값이 점점 밀집되는 현상을 뜻한다. 
• Secondary clustering : 이 문제는 같은 값으로 해시되는 키들은 collision을 해결하기 위해 계속해서 같은 위치를 탐색해나가기 때문에 발생하는 문제이다. 

Quadratic probing의 문제점

Quadratic probing은 연속된 공간을 탐색하지 않고 듬성듬성 탐색하기 때문에 Primary clustering 문제가 해결된다.

하지만 여전히 같은 값으로 해싱되면 같은 탐색순서를 가지기 때문에 Secondary clustering문제는 남아있다. 

Double hashing

위의 방법들은 하나의 해시함수를 사용한 것과 달리, 이번에는 두개의 해시함수를 사용한다. 

H_i(jkey) = (Hash(key) + F(i)) mod m

에서 F(i) = i * Hash2(key) 와 같이 설정한다. 

이렇게 하면 첫번째 Hash 함수에서 같은 값으로 해싱되더라도, 두번째 Hash2 함수에서도 같은 값으로 해싱되지 않는 이상 서로 다른 probing sequence를 가지며 Secondary clustering 문제도 해결된다. 

Extendible Hashing

해시테이블이 너무 커서 메인 메모리에 다 들어가지 못하는 상황을 생각해보자.

메인메모리에의 접근은 쉽지만 디스크로의 접근은 오버헤드가 크기 때문에 locality를 살려서 디스크 접근을 줄일 수 있도록 해시 테이블을 구성하는 것이 중요하다

 

이 방법에서는 해시 테이블을 Bucket이라는 더 작은 해시테이블들로 나눈다.

그리고 각 버킷의 최대 사이즈는 디스크 페이지의 사이즈로 설정한다.

그러면 이제 원하는 값을 찾으려면 어떤 버킷을 살펴봐야할지 결정하기 위해 메인메모리에 Directory라는 자료구조를 저장해둔다. 각 디렉토리는 연관되는 버킷의 디스크 주소를 담고있다.