해시법
해시법을 이용하면 검색과 더불어 데이터의 추가·삭제도 효율적으로 수행할 수 있다.
해시법은 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 말한다.
원소 갯수가 13인 경우 키를 원소 갯수에 나누면 아래와 같이 해시값을 구할 수 있다.
위 표에서 해시값 부분에서 새로 원소를 구해 저장한 배열을 해시 테이블이라고 하며, 해시 테이블은 아래와 같이 구해지게 된다.
이와 같이 키를 해시값으로 변환하는 과정을 해시 함수라고 하며, 일반적으로 해시 함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용한다.
해시 테이블에서 만들어진 원소를 버킷(Bucket)이라고 한다.(위 그림에서 0~12의 인덱스를 가진 배열)
해시 충돌
위 해시 테이블에 18이라는 값을 추가하려고 할 때, 18을 13으로 나눈 나머지는 5이므로 저장할 곳은 버킷 x[5]이지만, 이곳에는 이미 값이 들어있는 상태이다.
키와 해시값의 대응 관계가 꼭 1:1일 필요는 없으며, 키와 해시값은 일반적으로 다대 1(n:1)이다.
이처럼 저장할 버킷이 중복되는 현상을 충돌이라고 한다.
해시법에서 충돌이 발생하는 경우 다음 2가지 방법으로 대처할 수 있다.
- 체인법: 해시값이 같은 원소를 연결 리스트로 관리한다.
- 오픈 주소법: 빈 버킷을 찾을 때까지 해시를 반복한다.(재해시 = rehashing)
1. 체인법
해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결하는 방법을 말하며 오픈 해시법이라고도 한다.
체인법에서는 해시값이 같은 데이터를 연결 리스트에 의해 체인 모양으로 연결한다.
배열의 각 버킷(해시 테이블)에 저장하는 것은 인덱스를 해시값으로 하는 연결 리스트의 앞쪽 노드를 참조하게 된다.
예를 들어 69(69 % 13)와 17(17 % 13)의 해시값은 둘 다 4이며, 이들을 연결하는 연결 리스트의 앞쪽 노드를 참조하여 table[4]에 저장한다.
참고로 해시값 0이나 2처럼 데이터가 하나도 없는 버킷의 값을 None이라고 한다.
(table[4]는 버킷 69를 참조하는 것이며, 버킷 69의 뒤쪽 포인터는 17을 참조하는 것이다. 또한 버킷 17의 뒤쪽 포인터는 뒤쪽 노드가 존재하지 않음을 알려주는 None이다.)
체인법으로 구현한 해시 프로그램(Node 클래스와 ChainedHash 클래스가 정의되어 있음)
# 체인법으로 해시 함수 구현하기
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 # 뒤쪽 노드를 참조
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)
Node 클래스 만들기
Node 클래스는 개별 버킷을 나타낸다. 이 클래스에는 다음과 같이 필드가 3개 있다.
- key: 키(임의의 자료형)
- value: 값(임의의 자료형)
- next: 뒤쪽 노드를 참조(Node형)
Node 클래스는 키와 값이 짝을 이루는 구조이며, 키에 해시 함수를 적용하여 해시값을 구한다.
Node형 인스턴스를 초기화하는 __init__( ) 함수는 3개의 인수 key, value, next를 전달받아 각각 대응하는 필드인
self.key, self.value, self.next에 대입한다.
ChainedHash 클래스 만들기
ChainedHash 해시 클래스는 필드 2개로 구성된다.
- capacity: 해시 테이블의 크기(배열 table의 원소 수)를 나타낸다.
- table: 해시 테이블을 저장하는 list형 배열을 나타낸다.
__init__( ) 함수로 초기화하기
__init__( ) 함수는 빈 해시 테이블을 생성한다. 매개변수 capacity에 전달받는 것은 해시 테이블의 크기이다. 원소 수가 capacity인 list형의 배열 table을 생성하고 모든 원소를 None으로 한다.
만약 해시 테이블의 길이가 10이라면 capacity가 10이 될 것이고, 실제 접근 가능한 길이는 table[capacity - 1]일 것이다.
이와 같이 해시 테이블의 각 버킷은 맨 앞부터 table[0], table[1], ..., table[capacity - 1] 순으로 접근할 수 있다.
__init__( ) 함수가 호출된 직후 배열 table의 모든 원소는 None이고 전체 버킷이 빈 상태가 된다.
hash_value( ) 해시 함수 만들기
hash_value( ) 해시 함수는 인수 key에 대응하는 해시값을 구하는 함수이다.
해시 테이블의 충돌을 피하려면 해시 함수가 해시 테이블 크기보다 작거나 같은 정수를 고르게 생성해야 한다. 따라서 해시 테이블의 크기는 소수를 선호한다. ChainedHash 클래스의 hash_value 함수는 해시값을 다음과 같이 key가 int형인 경우와 아닌 경우로 구한다.
key가 int형인 경우
key를 해시의 크기 capacity로 나눈 나머지를 해시값으로 한다.
key가 int형이 아닌 경우(문자열, 리스트, 클래스형 등)
그 값으로는 바로 나눌 수 없다. 그래서 표준 라이브러리로 형 변환을 해야 해시값을 얻을 수 있다.
- sha256 알고리즘: hashlib 모듈에서 제공하는 sha256은 RSA의 FIPS 알고리즘을 바탕으로 하며, 주어진 바이트(byte) 문자열의 해시값을 구하는 해시 알고리즘의 생성자이다. hashlib 모듈은 sha256 외에도 MD5 알고리즘인 md5 등 다양한 해시 알고리즘을 제공한다.
- encode( ) 함수: hashlib.sha256에는 바이트 문자열의 인수를 전달해야 한다. 그래서 key를 str형 문자열로 변환한 뒤 그 문자열을 encode( ) 함수에 전달하여 바이트 문자열을 생성한다.
- hexdigest( ) 함수: sha256 알고리즘에서 해시값을 16진수 문자열로 꺼낸다.
- int( ) 함수: hexdigest( ) 함수로 꺼낸 문자열을 16진수 문자열로 하는 int형으로 변환한다.
키로 원소를 검색하는 search( ) 함수
search( ) 함수로 원소를 검색하는 과정은 아래 그림과 같다.
33 검색하기
33의 해시값은 7이므로 table[7]이 가리키는 연결 리스트를 찾아간다.
20 → 33으로 찾아가면 검색에 성공한다.
26 검색하기
26의 해시값은 0이다. table[0]이 None이므로 검색에 실패한다.
search( ) 함수가 원소를 검색하는 과정은 다음과 같이 정리할 수 있다.
- 해시 함수를 이용하여 키를 해시값으로 변환한다.
- 해시값을 인덱스로 하는 버킷에 주목한다.
- 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 스캔하는데, 키와 같은 값이 발견되면 검색에 성공하고 원소의 맨 끝까지 스캔해서 발견되지 않으면 검색에 실패한다.
def search(self, key: Any) -> Any:
"""키가 key인 원소를 검색하여 값을 반환"""
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 # 검색 실패
def add(self, key: Any, value: Any) -> bool:
"""키가 key이고 값이 value인 원소를 추가"""
hash = self.hash_value(key) # 추가하는 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 # 추가 성공
원소를 추가하는 add( ) 함수
add( ) 함수는 키가 key이고 값이 value인 원소를 추가한다.
13 추가하기
먼저 13의 해시값은 0이고 table[0]은 None이다. 13을 저장하는 노드를 새로 생성하고, 그 노드에 대한 참조를 table[0]에 대입한다.
46 추가하기
46의 해시값은 7이고 table[7] 버킷에는 20과 33을 연결한 연결 리스트에 대한 참조가 저장되어 있다. 이 리스트 안에 46은 존재하지 않으므로 연결 리스트의 맨 앞에 46을 추가한다. 구체적으로는 46을 저장하는 노드를 새로 생성하고, 그 노드에 대한 참조를 table[7]에 대입한다. 또 추가한 노드의 뒤쪽 포인터인 next가 20을 저장한 노드를 주목하도록 업데이트 한다.
add( ) 함수가 원소를 추가하는 과정은 다음과 같이 정리할 수 있다.
- 해시 함수를 사용하여 키를 해시값으로 변환한다.
- 해시값을 인덱스로 하는 버킷에 주목한다.
- 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 선형 검색을 한다. 키와 같은 값이 발견되면 키가 이미 등록된 경우이므로 추가에 실패한다. 원소의 맨 끝까지 발견되지 않으면 해시값인 리스트의 맨 앞에 노드를 추가한다.
원소를 삭제하는 remove( ) 함수
remove( ) 함수는 키가 key인 원소를 삭제한다.
69 삭제하기
69의 해시값은 4이다. table[4]의 버킷에 저장되어 있는 참조하는 곳의 리스트를 선형 검색하면 69를 발견할 수 있다. 이 노드의 뒤쪽 노드는 17을 저장한다. 그러므로 17을 저장한 노드에 대한 참조를 table[4] 버킷에 대입하면 노드가 삭제된다.
remove( ) 함수로 원소를 삭제하는 과정은 다음과 같이 정리할 수 있다.
- 해시 함수를 사용하여 키를 해시값으로 변환한다.
- 해시값을 인덱스로 하는 버킷에 주목한다.
- 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 선형 검색한다. 키와 같은 값이 발견되면 그 노드를 리스트에서 삭제한다. 그렇지 않으면 삭제에 실패한다.
def remove(self, key: Any) -> bool:
"""키가 key인 원소를 삭제"""
hash = self.hash_value(key) # 삭제할 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가 존재하지 않음)
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()
원소를 출력하는 dump( ) 함수
dump( ) 함수는 모든 원소를 덤프하는 것, 즉 해시 테이블의 내용을 한꺼번에 통째로 출력한다. 해시 테이블의 모든 원소인 table[0] ~ table[capacity - 1]까지 뒤쪽 노드를 찾아가면서 각 노드의 키와 값을 출력하는 작업을 반복한다.
이 함수를 실행하면 해시값이 같은 버킷이 연결 리스트에 의해 체인 모양으로 묶인 모습을 확인할 수 있다.
ChainedHash 클래스를 사용하는 프로그램(chained_hash_test.py)
# 체인법을 구현하는 해시 클래스 ChainedHash의 사용
from enum import Enum
from chained_hash import ChainedHash
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 = ChainedHash(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
'자료구조, 알고리즘 입문 > 검색 알고리즘' 카테고리의 다른 글
| 검색 알고리즘 - 오픈주소법 (0) | 2024.08.11 |
|---|---|
| 검색 알고리즘 - 이진 검색 (0) | 2024.08.06 |
| 검색 알고리즘 - 선형 검색 (0) | 2024.08.01 |