배열 검색 - 해시법(체인법, 오픈 주소법)

배경

 

예를 들어 배열 x의 원소 수가 13이고, 그 안에 오름차순으로 정렬된 10개의 데이터가 저장되어 있다고 가정해보겠습니다.

[5, 6, 14, 20, 29, 34, 37, 51, 69, 75]

 

이 배열에서 35를 추가한다면 과정은 다음과 같습니다.

① x[5], x[6] 사이에 값이 추가되도록 이진 검색법으로 검사

② x[6] 이후의 모든 원소를 한 칸씩 뒤로 이동

③ x[6]에 35 대입

 

원소가 이동하는데 필요한 복잡도는 O(n)이고, 비효율적입니다.

 

해시법

 

해시법은 해시값을 통해 추가·삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색을 수행하는 알고리즘입니다.

 

해시값은 배열의 원소들을 총 원소 개수로 나눈 나머지입니다. 이 해시값은 데이터에 접근할 때 기준이 됩니다. 위 예시라면 배열 x의 각 원소들을 13으로 나눈 나머지입니다.

 

이러한 해시값을 인덱스로 하여 원소를 새로 저장한 배열이 해시 테이블입니다. 배열 x에 대한 해시 테이블은 다음과 같습니다.

[-, 14, -, 29, 69, 5, 6, 20, 34, -, 75, 37, 51]

 

이제 이 해시 테이블에 새로운 원소인 35를 추가하겠습니다. 35를 13으로 나눈 나머지는 9입니다. 그렇다면 바로 x[9]에 35를 저장합니다. 해시테이블의 원소를 버킷(bucket)이라고 합니다.

[-, 14, -, 29, 69, 5, 6, 20, 34, 35, 75, 37, 51]

 

즉, 새로운 값을 추가해도 원소를 이동할 필요가 없습니다.

 

해시 충돌

 

만약 x의 해시테이블에 18을 추가해보겠습니다. 18을 13으로 나눈 나머지는 5. 하지만 이미 x[5]에는 값이 들어가있습니다. 이처럼 저장할 버킷에 값이 이미 들어가 있는 현상을 충돌이라고 합니다. 

 

이렇게 해시법에서 충돌이 발생하는 경우 다음 2가지 방법으로 대처할 수 있습니다.

① 체인법: 해시값이 같은 원소를 연결 리스트로 연결

② 오픈 주소법: 빈 버킷을 찾을 때까지 해시를 반복

 

체인법(Open Hash)

 

체인법이란 해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결하는 방법입니다. 

해시 테이블의 버킷에 저장되는 것은 그 인덱스를 해시값으로 하는 배열 x의 원소가 아닌, 인덱스를 해시값으로 하는 연결 리스트의 앞쪽 노드를 참조하는 것입니다.

 

 

이 연결리스트를 저장할 Node는 다음과 같습니다.

from __future__ import annotations
from typing import Any, Type
import hashlib

class Node:
    def __init__(self, key: Any, value: Any, next: Node) -> None:
        self.key = key  # 키
        self.value = value  # 값
        self.next = next  # 다음 노드를 참조

 

Node라는 클래스는 다음과 같이 3개의 필드로 이루어집니다. key와 value는 임의의 자료형이며, next는 다음 노드를 참조하므로 Node형입니다. __init__() 함수를 통해 각 인자를 전달 받아 대입하여 Node 클래스를 초기화합니다.

 

다음은 ChainedHash 해시 클래스입니다. 해시 테이블을 초기화하고, 각 key에 대한 해시값으로 해시 테이블 구성하는 함수가 작성됩니다.

class ChainedHash:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity  # 해시 테이블의 크기를 지정
        self.table = [None] * self.capacity  # 해시 테이블(리스트)을 선언

    def hash_value(self, key: Any) -> int:
        if isinstance(key, int):
            return key % self.capacity
        return(int(hashlib.sha256(str(key).encode()).hexdigest(), 16) % self.capacity)

 

__init__() 함수를 통해 빈 해시 테이블을 생성합니다. 해시 테이블의 크기인 capacity를 전달 받고, 원소 수가 capacity인 해시 테이블인 table의 모든 원소를 None으로 만듭니다.

 

그 다음 인수 key에 해당하는 해시값을 구하는 hash_value() 함수를 작성합니다. 만약 key가 int형이라면, key를 capacity인 13으로 나눈 나머지가 해시 값이 되지만, 위처럼 int형이 아닌 경우 표준 라이브러리로 형 변환을 해야 해시값을 얻을 수 있습니다.

 

A. search() 함수

 

33 검색하기

33의 해시값은 7이므로, table[7]이 가리키는 연결 리스트를 찾아갑니다. 20 → 33으로 찾아가게 됩니다.

 

26 검색하기

26의 해시값은 0입니다. table[0]은 None이므로 검색에 실패합니다.

 

이처럼 search() 함수는 다음과 같이 정리할 수 있습니다.

① 해시 함수를 사용하여 key를 해시값으로 변환

② 해시값을 인덱스로 하는 버킷을 주목

③ 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 스캔. 마지막 연결 리스트까지 스캔해서 발견되지 못할 경우 검색 실패

# ChainedHash 메서드
    def search(self, key: Any) -> Any:
        hash = self.hash_value(key)  # 검색하는 키의 해시값
        p = self.table[hash]  # 노드를 노드

        while p is not None:
            if p.key == key:
                return p.value  # 검색 성공
            p = p.next  # 뒤쪽 노드를 주목

        return None  # 검색 실패

 

B. add() 함수

 

add() 함수는 키가 key이고 값이 value인 원소를 추가합니다.

 

13 추가하기

13의 해시값은 0이고, table[0]은 None이므로, 노드를 새로 생성하고, 그 노드에 대한 참조를 table[0]에 대입합니다.

 

46 추가하기

46의 해시값은 7이고, table[7] 버킷에는 20, 33을 연결한 연결 리스트에 대한 참조가 저장되어 있습니다. 그러므로, 46을 저장하는 노드를 새로 생성하고, 연결 리스트의 맨 앞에 이 노드에 대한 참조를 table[7]에 대입합니다. 그리고 추가한 노드의 next 포인터가 다음 연결 리스트의 노드인 20을 주목하도록 설정합니다.

 

이처럼 add() 함수는 다음과 같이 정리할 수 있습니다.

① 해시 함수를 사용하여 key를 해시값으로 변환

② 해시값을 인덱스로 하는 버킷을 주목

③ 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 스캔. 키와 같은 값이 발견되면 키가 이미 등록된 경우이므로 추가에 실패. 연결 리스트의 마지막 노드까지 발견되지 않으면, 새로 생성한 노드를 버킷의 맨 앞에 대입하고, 노드의 next 포인터에 다음 노드를 주목하도록 설정

# ChainedHash 메서드
    def add(self, key: Any, value: Any) -> bool:
        hash = self.hash_value(key)  # 삽입하는 키의 해시값
        p = self.table[hash]  # 주목하는 노드

        while p is not None:
            if p.key == key:
                return False  # 삽입 실패
            p = p.next  # 그 다음 노드 주목

        temp = Node(key, value, self.table[hash])
        self.table[hash] = temp  # 노드 삽입
        return True  # 삽입 성공

 

C. remove() 함수

 

remove() 함수는 키가 key인 원소를 삭제합니다.

 

69 삭제하기

69의 해시값은 4입니다. table[4]의 버킷에 저장되어 있는 참조하는 곳의 연결 리스트를 순차적으로 스캔 시 69를 발견할 수 있습니다. 69의 값을 저장한 노드의 next 포인터는 17을 주목하고 있습니다. 

그러므로, table[4]에 17을 저장한 노드에 대한 참조를 대입하면 69를 저장한 노드가 삭제됩니다.

 

이처럼 remove() 함수는 다음과 같이 정리할 수 있습니다.

① 해시 함수를 사용하여 key를 해시값으로 변환

② 해시값을 인덱스로 하는 버킷을 주목

③ 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 스캔. 키와 같은 값이 발견되면 키가 이미 등록된 경우이므로 추가에 실패. key와 같은 값이 발견되면 이전 노드를 key가 주목하고 있는 노드와 연결.

# ChainedHash 메서드
    def remove(self, key: Any) -> bool:
        hash = self.hash_value(key)  # 삭제할 키의 해시값
        p = self.table[hash]  # 주목하고 있는 노드
        pp = None  # 바로 앞 주목 노드

        while p is not None:
            if p.key == key:  # key를 발견하면 아래를 실행
                if pp is None:
                    self.table[hash] = p.next
                else:
                    pp.next = p.next
                return True  # key 삭제 성공
            pp = p
            p = p.next  # 뒤쪽 노드에 주목
        return False  # 삭제 실패(key가 존재하지 않음)

 

D. dump() 함수

 

dump() 함수는 해시 테이블의 내용을 한번에 출력하는 함수입니다. 

# ChainedHash 메서드    
    def dump(self) -> None:
        for i in range(self.capacity):
            p = self.table[i]
            print(i, end='')
            while p is not None:
                print(f'  → {p.key} ({p.value})', end='')  # 해시 테이블에 있는 키와 값을 출력
                p = p.next
            print()

 

오픈 주소법(Close Hash)

 

오픈 주소법은 충돌이 발생했을 때 재해시(rehashing)을 수행하여 빈 버킷을 찾는 방법입니다. 재해시를 위한 해시 함수는 자유롭게 정할 수 있습니다. 본 실습에서는 key에 1을 더하여 13으로 나눈 나머지를 사용합니다.

 

A. 원소 추가하기

 

다음과 같이 해시 테이블이 구성되었다고 가정하겠습니다. 이때 원소 18을 추가하고자 합니다. 

 

 

18을 13으로 나눈 나머지는 5. 하지만 table[5]에 값이 채워져 있으므로 재해시를 합니다. 사전에 본 실습에서는 1을 더한 후 13으로 나눈 나머지를 재해시로 정의했으므로, 재해시한 결과값은 (18+1) % 13 = 6입니다.

 

이또한 값이 채워져 있으니, 다시 수행하여 결과값 7을 얻습니다. table[7]은 값이 비워져 있으므로 18을 추가합니다. 

 

이처럼 오픈 주소법은 빈 버킷이 나올 때까지 재해시를 반복하므로 선형 탐사법이라고도 합니다.

 

B. 원소 삭제하기

 

위 해시 테이블에서 5를 삭제하는 과정을 알아보겠습니다. 단순히 5를 비우는 것으로는 삭제가 이루어지지 않습니다.

예를 들어 앞서 추가한 18을 삭제한다고 했을 때 해시값이 같은 5가 비워져있다면, 아 버킷에 값이 없네? 하며 삭제를 실패하기 때문입니다.

 

이러한 오류 방지를 위해 각 버킷에 다음과 같은 속성을 부여해야 합니다.

① 데이터가 저장되어 있음(숫자)

② 비어 있음(-): 해시값이 같은 데이터는 존재하지 않다.

③ 삭제 완료(☆): 해시값이 같은 데이터는 다른 버킷에 저장되어 있다.

 

 

C. 원소 검색하기

 

17 검색하기

해시값이 4인 버킷은 - 속성이므로 해시값이 같은 데이터가 존재하지 않는다는 비어있음으로, 검색 실패입니다.

 

18 검색하기

18의 해시값이 5인 버킷은 ☆ 속성이므로 해시값이 같은 데이터가 다른 버킷에 저장되어 있다는 의미입니다. 이때 재해시를 통해 검색하는 값인 18을 찾아나가야 합니다.

 

다음 코드는 key 값의 수정/삭제를 위한 속성이 정의된 Status 클래스와 해시 테이블을 구성하는 각 Bucket, 그리고 각 메서드가 정의된 OpenHash 클래스 코드입니다.

from __future__ import annotations
from typing import Any, Type
from enum import Enum
import hashlib

# 버킷의 속성
class Status(Enum):
    OCCUPIED = 0  # 데이터를 저장
    EMPTY = 1     # 비어 있음
    DELETED = 2   # 삭제 완료

class Bucket:
    """해시를 구성하는 버킷"""

    def __init__(self, key: Any = None, value: Any = None,
                       stat: Status = Status.EMPTY) -> None:
        """초기화"""
        self.key = key      # 키
        self.value = value  # 값
        self.stat = stat    # 속성

    def set(self, key: Any, value: Any, stat: Status) -> None:
        """모든 필드에 값을 설정"""
        self.key = key      # 키
        self.value = value  # 값
        self.stat = stat    # 속성

    def set_status(self, stat: Status) -> None:
        """속성을 설정"""
        self.stat = stat

class OpenHash:
    """오픈 주소법을 구현하는 해시 클래스"""

    def __init__(self, capacity: int) -> None:
        """초기화"""
        self.capacity = capacity                 # 해시 테이블의 크기를 지정
        self.table = [Bucket()] * self.capacity  # 해시 테이블

    def hash_value(self, key: Any) -> int:
        """해시값을 구함"""
        if isinstance(key, int):
            return key % self.capacity
        return(int(hashlib.md5(str(key).encode()).hexdigest(), 16)
                % self.capacity)

    def rehash_value(self, key: Any) -> int:
        """재해시값을 구함"""
        return(self.hash_value(key) + 1) % self.capacity

    def search_node(self, key: Any) -> Any:
        """키가 key인 버킷을 검색"""
        hash = self.hash_value(key)  # 검색하는 키의 해시값
        p = self.table[hash]         # 버킷을 주목

        for i in range(self.capacity):
            if p.stat == Status.EMPTY:
                break
            elif p.stat == Status.OCCUPIED and p.key == key:
                return p
            hash = self.rehash_value(hash)  # 재해시
            p = self.table[hash]
        return None

    def search(self, key: Any) -> Any:
        """키가 key인 갖는 원소를 검색하여 값을 반환"""
        p = self.search_node(key)
        if p is not None:
            return p.value  # 검색 성공
        else:
            return None     # 검색 실패

    def add(self, key: Any, value: Any) -> bool:
        """키가 key이고 값이 value인 요소를 추가"""
        if self.search(key) is not None:
            return False             # 이미 등록된 키

        hash = self.hash_value(key)  # 추가하는 키의 해시값
        p = self.table[hash]         # 버킷을 주목
        for i in range(self.capacity):
            if p.stat == Status.EMPTY or p.stat == Status.DELETED:
                self.table[hash] = Bucket(key, value, Status.OCCUPIED)
                return True
            hash = self.rehash_value(hash)  # 재해시
            p = self.table[hash]
        return False                        # 해시 테이블이 가득 참

    def remove(self, key: Any) -> int:
        """키가 key인 갖는 요소를 삭제"""
        p = self.search_node(key)  # 버킷을 주목
        if p is None:
            return False           # 이 키는 등록되어 있지 않음
        p.set_status(Status.DELETED)
        return True

    def dump(self) -> None:
        """해시 테이블을 덤프"""
        for i in range(self.capacity):
            print(f'{i:2} ', end='')
            if self.table[i].stat == Status.OCCUPIED:
                print(f'{self.table[i].key} ({self.table[i].value})')
            elif self.table[i].stat == Status.EMPTY:
                print('-- 미등록 --')
            elif self.table[i] .stat == Status.DELETED:
                print('-- 삭제 완료 --')

 

출처

 

Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편