https://vibeee.tistory.com/284
검색 알고리즘 - 해시법
해시법해시법을 이용하면 검색과 더불어 데이터의 추가·삭제도 효율적으로 수행할 수 있다.해시법은 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 말한다. 원소 갯수가 13
vibeee.tistory.com
지난 포스팅에서 소개했던 것처럼 해시 충돌이 발생할 때 해결하는 방법으로 체인법 외 오픈주소법이 있다.
오픈 주소법
오픈 주소법은 충돌이 발생했을 때 재해시(rehashing)를 수행하여 빈 버킷을 찾는 방법을 말하며 닫힌 해시법(closed hashing)이라고도 한다.
원소 추가하기
아래 그림은 18을 추가하는 과정에서 충돌이 발생하는 상태를 보여준다.
이럴 때 재해시를 수행할 수 있다. 재해시를 위한 해시 함수는 자유롭게 정할 수 있으며, 여기서는 키에 1을 더해 13으로 나눈 나머지를 사용한다.
재해시를 위한 식 (18 + 1) % 13으로 나머지 6을 얻었는데, 인덱스 6인 버킷도 값이 채워져 있으므로 재해시를 한다.
이번에는 (19 + 1) % 13을 통해 7을 얻으므로 인덱스 7인 버킷에 18을 추가한다.
이처럼 오픈 주소법은 빈 버킷이 나올 때까지 재해시를 반복하므로 선형 탐사법이라고도 한다.
원소 삭제하기
5를 삭제하는 과정을 살펴본다.
인덱스가 5인 버킷을 비우기만 하면 될 것 같지만 실제로는 그렇지 않다.
이유는 해시값이 같은 18을 검색할 때 해시값이 5인 데이터는 존재하지 않는다고 착각하여 검색에 실패하기 때문이다.
이러한 오류를 방지하기 위해서 각 버킷에 다음과 같은 속성을 부여한다.
- 데이터가 저장되어 있음(숫자)
- 비어 있음(-)
- 삭제 완료(★)
이와 같이 버킷이 비어 있는 상태를 -으로, 삭제 완료된 상태를 ★로 나타냈다. 예를 들어 5를 삭제하면 그 위치 버킷에 삭제 완료임을 나타내는 속성 ★을 저장한다.
원소 검색하기
17을 검색한다고 가정했을 때, 해시값이 4인 버킷을 들여다보면 속성은 비어 있음(-)이므로 검색 실패라고 판단할 수 있다.
그렇다면 18을 검색하는 경우를 생각해봤을 때, 18의 해시값이 5인 버킷의 속성은 삭제 완료(★)이다.
그래서 재해시하여 해시값이 6인 버킷의 속성을 살펴보지만, 6이 저장되어 있으므로 다시 재해시하여 7인 버킷을 들여다본다. 검색하는 값 18이 저장되어 있으므로 검색 성공이다.
오픈 주소법을 구현하는 프로그램(3개의 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:
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('-- 삭제 완료 --')
열거형 Bucket 클래스의 필드 stat는 Bucket 형인 각 버킷의 속성인 저장(OCCUPIED), 비어있음(EMPTY), 삭제 완료(DELETED)를 나타낸다. OpenHash 클래스의 rehash_value( ) 함수는 재해시값을 구한다. 해시값에 1을 더하여 재해시한 식으로 새로운 해시값을 얻는다.
오픈 주소법으로 구현한 Openhash 클래스를 사용하는 프로그램(open_hash_test.py)
# 오픈 주소법을 구현하는 해시 클래스 Openhash 사용
from enum import Enum
from open_hash import OpenHash
Menu = Enum('Menu', ['추가', '삭제', '검색', '덤프', '종료']) # 메뉴를 선언
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) # 크기가 13인 해시 테이블 생성
while True:
menu = select_menu() # 메뉴 선택
if menu == Menu.추가: # 추가
key = int(input('추가할 키를 입력하세요.: '))
val = input('추가할 값을 입력하세요.: ')
if not hash.add(key, val):
print('추가를 실패했습니다!')
elif menu == Menu.삭제: # 삭제
key = int(input('삭제할 키를 입력하세요.: '))
if not hash.remove(key):
print('삭제를 실패했습니다!')
elif menu == Menu.검색: # 검색
key = int(input('검색할 키를 입력하세요.: '))
t = hash.search(key)
if t is not None:
print(f'검색한 키를 갖는 값은 {t}입니다.')
else:
print('검색할 데이터가 없습니다.')
elif menu == Menu.덤프: # 덤프
hash.dump()
else: # 종료
break
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 1
추가할 키를 입력하세요.: 1
추가할 값을 입력하세요.: 수연
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 1
추가할 키를 입력하세요.: 5
추가할 값을 입력하세요.: 동혁
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 1
추가할 키를 입력하세요.: 10
추가할 값을 입력하세요.: 예지
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 1
추가할 키를 입력하세요.: 12
추가할 값을 입력하세요.: 원준
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 1
추가할 키를 입력하세요.: 14
추가할 값을 입력하세요.: 민서
추가를 실패했습니다!
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 3
검색할 키를 입력하세요.: 5
검색한 키를 갖는 값은 동혁입니다.
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 4
0 -- 미등록 --
1 1 (수연)
2 -- 미등록 --
3 -- 미등록 --
4 -- 미등록 --
5 5 (동혁)
6 -- 미등록 --
7 -- 미등록 --
8 -- 미등록 --
9 -- 미등록 --
10 10 (예지)
11 -- 미등록 --
12 12 (원준)
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 2
삭제할 키를 입력하세요.: 14
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 4
0 -- 미등록 --
1 -- 삭제 완료 --
2 -- 미등록 --
3 -- 미등록 --
4 -- 미등록 --
5 5 (동혁)
6 -- 미등록 --
7 -- 미등록 --
8 -- 미등록 --
9 -- 미등록 --
10 10 (예지)
11 -- 미등록 --
12 12 (원준)
(1)추가 (2)삭제 (3)검색 (4)덤프 (5)종료: 5
Process finished with exit code 0'자료구조, 알고리즘 입문 > 검색 알고리즘' 카테고리의 다른 글
| 검색 알고리즘 - 해시법 (0) | 2024.08.08 |
|---|---|
| 검색 알고리즘 - 이진 검색 (0) | 2024.08.06 |
| 검색 알고리즘 - 선형 검색 (0) | 2024.08.01 |