알고리즘 - 해시법(3)

이번에는 해시법 중에서 오픈 주소법입니다.

 

오픈 주소법은 충돌이 발생했을 때 재해싱으로 빈 곳을 찾는 방법을 말합니다.

 

ㅡ

14

ㅡ

29

ㅡ

5

6

ㅡ

 

이렇게 배열이 있을 때, 칸 하나하나를 버킷이라고 부릅니다.

만약 숫자를 추가해야 하는데 버킷이 이미 다른 숫자가 들어와 있다면 빈 버킷을 찾아 이동하게 만드는 것입니다.

 

오픈 주소법도 체인법과 마찬가지로 파일을 2개로 분리하겠습니다.

 

---

 

open_hash.py

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

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_status(self, stat: Status) -> None:
        self.stat = stat

 

먼저 Status 클래스는 버컷의 속성을 정의합니다.

 

Bucket 클래스는 버킷을 초기화 하고 속성을 설정해줍니다.

 

class OpenHash:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.table = [Bucket()] * self.capacity

    def hash_value(self, key: Any) -> int:
        return key % self.capacity
    
    def rehash_value(self, key: Any) -> int:
        return (self.hash_value(key) + 1) % self.capacity
    
    def search_bucket(self, key: Any) -> Any:
        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:
        p = self.search_bucket(key)
        if p is not None:
            return p.value
        else:
            return None

 

체인법과 크게 다른 부분은 없습니다. 

rehash_value는 해시 값에 +1을 하여 다시 한 번 해싱을 하는 것입니다.

search_bucket은 버켓을 찾는 함수입니다.

 

    def add(self, key: Any, value: Any) -> bool:
        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:
        p = self.search_bucket(key)
        if p is None:
            return False
        p.set_status(Status.DELETED)
        return True

    def printed(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('-- 삭제 완료 --')

 

체인법과 다른 부분이 있다면 버킷의 속성을 확인하고 바꿔주는 것입니다.

 

---

from enum import Enum
from open_hash import OpenHash

Menu = Enum('Menu', ['add', 'remove', 'search', 'printed', 'exit'])

def select_menu() -> Menu:
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep = ' ', end='')
        n = int(input(': '))
        if 1 <= n <= (len(Menu)):
            return Menu(n)

   
hash = OpenHash(13)

while True:
    menu = select_menu()

    if menu == Menu.add:
        key = int(input('추가할 키를 입력하세요.: '))
        val = input('추가할 값을 입력하세요.: ')
        if not hash.add(key, val):
            print('추가를 실패했습니다.')
        else:
            print('추가 성공')

    elif menu == Menu.remove:
        key = int(input('삭제할 키를 입력하세요.: '))
        if not hash.remove(key):
            print('삭제를 실패했습니다.')
        else:
            print('삭제 성공')

    elif menu == Menu.search:
        key = int(input('검색할 키를 입력하세요.: '))
        t = hash.search(key)
        if t is not None:
            print(f'검색한 키를 갖는 값은 {t}입니다.')
        else:
            print('검색할 데이터가 없습니다.')

    elif menu == Menu.printed:
        hash.printed()

    else:
        break

 

체인법과 큰 차이가 없습니다.