[Python 자료구조] 해시 법 + (오픈 주소 법)

해시 법 설명 : [Python 자료구조] 해시 법 + (체인 법) :: 코딩 연구소 (tistory.com)

 

💡 해시 충돌 - 오픈 주소법

오픈 주소법은 충돌이 발생했을 시 재해시 ( rehashing ) 을 수행하여 빈 버킷을 찾는 방법을 말하며 닫힌 해시 법 ( closed hashing ) 이라고도 합니다.

 

66 이라는 숫자를 추가하려 했지만, 충돌이 발생했습니다.

충돌이 발생했을 시 재해시를 수행합니다.

 

재해시를 위한 식으로 ( 66 + 1 ) % 4 로 77 나누기 4를 진행한 19 를 얻었습니다. 

오픈 주소법에서 재해시를 위한 식은 (원소 + 1) % (버킷) 진행한 나머지 값 = 인덱스

 

만약 들어 가려 하는 버킷이 또 충돌이 발생할 경우 66+1이 아닌 1을 더했던 67을 기준으로 +1 진행 

 

해시 법 + 체인법에서 사용한 해시 함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용되었고,

17을 8로 나눈 나머지는 1 이므로 x[1]에 17을 저장했습니다.

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

 

 

💡 해시 충돌 - 체인 법 (코드)

from enum import Enum
import hashlib

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

"""해시를 구성하는 버킷"""
class Bucket:
    def __init__(self, key, value, stat):
        # 초기화
        self.key = key      # 키
        self.value = value  # 값
        self.stat = stat    # 속성

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

    def set_status(self, stat):
        self.stat = stat
        
"""오픈 주소법을 구현하는 해시 클래스"""
class OpenHash:
    def __init__(self, capacity):
        self.capacity = capacity                 # 해시 테이블의 크기를 지정
        self.table = [Bucket()] * self.capacity  # 해시 테이블

    # 해시값 구하기
    def hash_value(self, key):
        if isinstance(key, int):
            return key % self.capacity
        return(int(hashlib.md5(str(key).encode()).hexdigest(), 16)
                % self.capacity)

    # 재해시값 구하기
    def rehash_value(self, key):
        return(self.hash_value(key) + 1) % self.capacity

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

    # 키가 key이고 값이 value인 요소를 추가
    def add(self, 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                        # 해시 테이블이 가득 참

    # 키가 key인 갖는 요소를 삭제
    def remove(self, key):
        p = self.search_node(key)  # 버킷을 주목
        if p is None:
            return False           # 이 키는 등록되어 있지 않음
        p.set_status(Status.DELETED)
        return True
    
    # 해시 테이블을 덤프
    def dump(self):
        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('-- 삭제 완료 --')