[자료구조] 해싱

키 값을 input으로 output이 특정 범위 내로 나오도록 연산을 수행한다. 이 결과를 주소로 hash table의 항목에 접근한다.

저장/ 탐색 모두 O(1), 최악의 경우 O(n)

Dictionary(사전구조)

map또는 table로 불리며 탐색 키와 value, 2가지 필드로 구성된다.   

---

hash function (해시 함수)

탐색 키를 입력받아 hash address(해시 주소)를 생성

hash address가 hash table의 index

+ hash value: 해시 함수의 결과값

 

Prime Number Modular Function (제산함수)

h(k) = k mod M

M: 해시 테이블 크기, 소수(prime number)로 선택

 

비트추출 함수

M = 2^k일 때, 임의의 위치의 k개의 비트를 이진수로 간주하여 해시 주소로 사용

---

hash table(해시 테이블)

M개의 bucket으로 구성된 table, 각 bucket은 s개의 slot으로 이루어짐

 

충돌(collision): 서로 다른 두 개의 탐색키의 hash address가 같을 때, 즉 h(k1) == h(k2)

오버플로우(overflow): 충돌이 버켓의 슬롯 수보다 많이 발생

 

실제로는 collision & overflow를 해결하기 위한 알고리즘 추가

-> O(1) + ɑ

---

충돌 해결책

Linear Probing (선형조사법)

충돌이 일어난 바로 다음 칸을 조사 (비어있는 공간이 나올 때까지)

테이블의 끝에 도달하면, 테이블의 처음부터 조사

조사 시작 위치로 돌아오면 테이블이 가득 찬 것

 

단점:

군집화(clustering) - collision이 한 번 시작되면 그 주위에서 계속 발생

결합(coalescing) - cluster들이 합쳐짐 

//문자로 된 키를 숫자로 변환
int transform(char* key){
    int number = 0;
    
    while(*key){
        number += (int)*key;
        key++;
    }
    
    return number;
}

int hash_function(char* key){
    //키를 자연수로 변환하고 테이블의 크기로 나누어 나머지를 반환
    return transform(key)%TABLE_SIZE;
}

void hash_lp_add(element item, element ht[]){
    int i, hash_value;
    hash_value = i = hash_function(item.key);
    
    while(!empty(ht[i])){ //slot이 비어있는 버켓을 찾을 때까지
        //item이 이미 hash table에 있음
        if(equal(item, ht[i])){
            //탐색키 중복
            exit(1);
        }
        
        //collision
        i = (i+1)%TABLE_SIZE;
        
        //출발 지점으로 돌아옴
        if(i == hash_value){
            //테이블이 가득참
            exit(1);
        }
    }
    
    //삽입
    h[i] = item;
}

---

Quadratic Probing (이차조사법)

다음 조사할 위치: ( h(k) + inc*inc ) mod M

inc는 1씩 커짐

군집과 결합 크게 완화 가능

 

단점: h(k)가 같은 키에 대해서는 계속 collision 발생

int inc = 0;

i = (i + inc*inc) % TABLE_SIZE;
inc++;

---

Double Hashing (이중 해싱법) 

rahashing(재해싱)이라고도 함

 

오버플로우가 발생하면 원 해시함수와 다른 별개의 해시 함수 사용

이차조사법처럼 같은 패턴 반복되지 않음

 

ex)

h'(k) = C - (k mod C) 

C는 M보다 작은 소수

 

h(k) -> collision -> h(k)+h'(k) -> collision -> h(k) + 2h'(k) -> collision -> h(k) + 3h'(k) ....

---

Chaining (체이닝)

오버플로우 문제를 연결 리스트로 해결

각 버켓에 고정된 슬롯을 할당하는 게 아니라, 연결 리스트를 할당

충돌 나면 새로운 노드 생성해서 저장

void hash_chain_add(element item, struct list *ht[]){
    int hash_value = hash_function(item.key);
    
    struct list *ptr;
    struct list *node_before = NULL;
    struct list *node = ht[hash_value];
    
    for(; node; node_before = node, node = node->link){
        if(node -> item.key == item.key){
            //이미 탐색키가 저장되어 있음
            return;
        }
    }
    
    ptr = (struct list*)malloc(sizeof(struct list));
    ptr->item = item;
    ptr->link = NULL;
    
    if(node_before) node_before->link = ptr;
    else ht[hash_value] = ptr;
}