[자료구조] 해시, 해시법(hashing) / Python 파이썬
해시법
해시법(hashing) '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 말한다.
이 방법은 원소의 검색뿐 아니라 추가 · 삭제도 효율적으로 수행할 수 있다. 배열의 키(원소의 값)를 원소 갯수인 7로 나눈 나머지를 해시값(hash value)라고 한다. 해시값은 데이터에 접근할 때 기준이 된다.
11을 7로 나눈 나머지는 4이므로 x[4]에 바로 저장한다. 이렇게 키를 해시값으로 변환하는 과정을 해시 함수(hash function)라고 한다. 또한 일반적으로 해시 함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용한다. 해시 테이블에서 만들어진 원소를 버킷(bucket)이라고 한다.
해시 충돌
앞에서 만든 해시 테이블에 18을 추가하면 7로 나눈 나머지는 4이므로 저장할 곳은 버킷 x[4]이지만, 이곳에는 이미 값이 들어있다. 키와 해시값의 대응 관계가 꼭 1 : 1 일 필요는 없다. 키와 해시값은 일반적으로 다 대 1(n:1)이다. 이처럼 저장할 버킷이 중복되는 현상을 충돌(collision)이라고 한다.
해시 함수는 가능한 한 해시값이 한쪽으로 치우치지 않고 고르게 분산된 값을 출력하도록 만드는 것이 가장 좋다.
이렇게 해시법에서 충돌이 발생하는 경우 다음 2가지 방법으로 대처할 수 있다.
1. 체인법 : 해시값이 같은 원소를 연결 리스트로 관리한다.
2. 오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복한다.
체인법
체인법(chaining)이란 해시값이 같은 데이터를 체인 모양의 연결리스트로 연결하는 방법을 말하며 오픈 해시법(open hashing)이라고도 한다.
1. Node 클래스 만들기
- key : 키 (임의의 자료형)
- value : 값 (임의의 자료형)
- next : 뒤쪽 노드를 참조 (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 클래스는 키와 값이 짝을 이루는 구조이다. 키에 해시 함수를 적용하여 해시값을 구한다. Node형 인스턴스를 초기화하는 __init__( ) 함수는 3개의 인수 key, value, next를 전달받아 각각 대응하는 필드인 self.key, self.value, self.next에 대입한다.
2. ChainedHash 해시 클래스 만들기
- capacity : 해시 테이블의 크기(배열 table의 원소 수)를 나타낸다.
- table : 해시 테이블을 저장하는 list형 배열을 나타낸다.
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)(1) __init__( ) 함수로 초기화하기
__init__( ) 함수는 빈 해시 테이블을 생성한다. 매개변수 capacity에 전달받는 것은 해시 테이블의 크기이다. 원소 수가 capacity인 list형의 배열 table을 생성하고 모든 원소를 None으로 한다.
(2) hash_value( ) 해시 함수 만들기
hash_value( ) 함수는 인수 key에 대응하는 해시값을 구한다.
3. 키로 원소를 검색하는 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 # 검색 실패
4. 원소를 추가하는 add( ) 함수
add( ) 함수는 키가 key이고 값이 value인 원소를 추가한다.
- 해시 함수를 사용하여 키를 해시값으로 변환한다.
- 해시값을 인덱스로 하는 버킷에 주목한다.
- 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 선형 검색을 한다. 키와 같은 값이 발견되면 키가 이미 등록된 경우이므로 추가에 실패한다. 원소의 맨 끝까지 발견되지 않으면 해시값인 리스트의 맨 앞에 노드를 추가한다.
def add(self, key: Any, value: Any) -> bool:
"""키가 key이고 값이 value인 원소를 삽입"""
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 # 삽입 성공
5. 원소를 삭제하는 remove( ) 함수
키가 key인 원소를 삭제한다.
- 해시 함수를 사용하여 키를 해시값으로 변환한다.
- 해시값을 인덱스로 하는 버킷에 주목한다.
- 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 선형 검색을 한다. 키와 같은 값이 발견되면 그 노드를 리스트에서 삭제한다. 그렇지 않으면 삭제에 실패한다.
def remove(self, key: Any) -> bool:
"""키가 key인 원소를 삭제"""
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가 존재하지 않음)
6. 원소를 출력하는 dump( ) 함수
dump( ) 함수는 모든 원소를 덤프하는 것, 즉 해시 테이블의 내용을 한꺼번에 통째로 출력한다. 해시 테이블의 모든 원소인 table[0] ~ table[capacity - 1] 까지 뒤쪽 노드를 찾아가면서 각 노드의 키와 값을 출력하는 작업을 반복한다.
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()
7. 체인법을 구현하는 해시 클래서 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
REFERENCE
do it! 자료구조와 함께 배우는 알고리즘 입문-파이썬 편