[자료구조] 개방 주소법 (open addressing) - 선형 조사법, 이차 조사법, 이중 해시법

개방 주소법 (open addressing)

개방 주소법은 특정 버킷에서 충돌이 발생하면, 비어있는 버킷을 찾아 항목을 저장하게 됩니다. 해시 테이블에서 비어있는 공간을 찾는 것을 조사(probing)라고 합니다.

 

선형 조사법 (linear probing)

선형 조사법은 충돌이 발생한 곳에서 다음 버킷이 비어있는 곳이 나올 때까지 계속해서 조사하는 방법입니다. 만약 테이블의 끝에 도달하게 되면 다시 테이블의 처음으로 갑니다.

 

선형 조사법 구현

삽입 연산에서 해당하는 해시 값에 비어있는지 검사합니다.

• 비어 있으면 해당 버킷에 삽입합니다.
• 비어 있지 않으면 그 주소에 저장된 키와 동일한지 체크합니다.
  • 동일하지 않다면, 주소를 나타내는 변수를 1 증가해 다음 버킷을 가리키도록 합니다.

void hash_lp_add(element item, element ht[]) {
    int i, hash_value;
    hash_value = i = hash_function(item.key);
    
    while(!empty(ht[i])) {
        if(equal(item, ht[i])) {
            fprintf(stderr, "탐색키가 중복되었습니다.\n");
            exit(1);
        }
        i = (i + 1) % TABLE_SIZE;
        if(i == hash_value) {
            fprintf(stderr, "테이블이 가득찼습니다.");
            exit(1);
        }
    }
    ht[i] = item;
}

 

저장된 키들을 탐색할 때는 삽입과 마찬가지로 탐색할 키를 해시 함수에 적용시킵니다. 그 계산된 주소에 찾고자 하는 값을 얻지 못하면 찾을 때까지 다음 버킷을 탐색합니다. 다시 원래 주소로 돌아오면 없다는 뜻입니다.

void hash_lp_search(element item, element ht[]) {
    int i, hash_value;
    hash_value = i = hash_function(item.key);
    while(!empty(ht[i])) {
        if(equal(item, ht[i])) {
            fprintf(stderr, "탐색 %s: 위치 = %d\n", item.key, i);
            return;
        }
        i = (i + 1) % TABLE_SIZE;
        if(i == hash_value) {
            fprintf(stderr, "찾는 값이 테이블에 없음");
            return;
        }
    }
    fprintf(stderr, "찾는 값이 테이블에 없음\n");
}

 

 

다음은 삭제 연산입니다. 삭제 연산이 조금 복잡한데, 단순히 버킷에 값만 빼면 안 됩니다. 선형 조사법에서 항목이 삭제되면 탐색이 불가능해질 수 있습니다.

해결법은 다른 버킷도 만드는 것입니다.

• 한 번도 사용하지 않은 버킷
• (이전에 사용되었지만) 지금은 사용하지 않는 버킷
• 현재 사용 중인 버킷

세 가지로 분류해야 합니다.

 

다시 삭제 연산으로 돌아옵시다. 버킷을 삭제하고 탐색 연산을 수행해서 특정 값을 찾으려면, 삭제된 버킷의 인덱스는 지금은 사용하지 않는 버킷으로 바뀌기 때문에 이를 만나면 다음 버킷을 찾을 수 있도록 구현해주면 됩니다.

 

이차 조사법 (quadratic probing)

선형 조사법은 1씩 증가했던 것과는 달리 이차 조사법은 제곱수씩 더해서 조사할 위치를 정하는 방식입니다.

$$ (h(k) + i * i) \space mod \space M for \space i = 0, 1, \cdots, M - 1 $$

void hash_qp_add(element item, element ht[]) {
    int i, hash_value, inc = 0;
    hash_value = i = hash_function(item.key);
    while(!empty(ht[i])) {
        if(equal(item, ht[i])) {
            fprintf(stderr, "탐색키가 중복되었습니다\n");
            exit(1);
        }
        i = (hash_value + inc * inc) % TABLE_SIZE;
        inc = inc + 1;
        if(i == hash_value) {
            fprintf(stderr, "테이블이 가득 찼습니다.\n");
            exit(1);
        }
    }
    ht[i] = item;
}

 

이중 해시법 (double probing)

이중 해시법은 항목을 저장할 다음 위치를 결정할 때, 원래 해시 함수와 다른 별개의 해시 함수를 같이 이용하는 방법입니다.

 

이중 해시법은 키를 참조해 더해지는 값이 결정됩니다. 따라서 해시 함수값이 같더라도 키가 다르면 서로 다른 조사순서를 갖습니다. 두 번째 해시함수부터 조사 간격을 결정합니다. 이 때, $C$의 값은 해시 테이블의 크기 $M$보다 작은 소수입니다.

 

$$ h’(k) = C - (k \space mod \space C) $$

void hash_dh_add(element item, element ht[]) {
    int i, hash_value, inc;
    hash_value = i = hash_function(item.key);
    inc = hash_function2(item.key);
    // printf("hash_address=%d\n", i);
    while(!empty(ht[i])) {
        if(equal(item, ht[i])) {
            fprintf(stderr, "탐색키가 중복되었습니다.\n");
            exit(1);
        }
        i = (i + inc) % TABLE_SIZE;
        if(i == hash_value) {
            fprintf(stderr, "테이블이 가득 찼습니다.\n");
            exit(1);
        }
    }
    ht[i] = item;
}

 

각 방법들로 충돌 처리하기

입력할 숫자가 다음과 같이 입력된다고 한다면 위에서 소개한 방법들로 해시테이블의 내용을 그리시오. (단, 해시 테이블의 크기는 7, 해시 함수 $h(k) = k \space mod \space 7$)

$$ 12, 47, 93, 23, 89,60, 78 $$

 

선형 조사법

 

이차 조사법