03-4 해시법
해시법 hashing
- 인덱스(데이터를 저장할 위치)를 간단한 연산으로 구하는 것
- 원소의 검색, 추가, 삭제를 효율적으로 수행
해시값 hash value
배열의 키(원소의 값)를 원소 개수인 n으로 나눈 나머지
해시 테이블 hash table
해시값을 인덱스로 하여 원소를 새로 저장한 배열
해시 함수 hash function
키를 해시값으로 변환하는 과정
나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용
버킷 bucket : 해시 테이블에서 만들어진 원소
해시 충돌
키와 해시 값 = n : 1 관계
충돌 collision 저장할 버킷이 중복되는 현상
대처법
체인법 : 해시값이 같은 원소를 연결 리스트로 관리
오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복
체인법 chaining
체인법 : 해시값이 같은 데이터를 체인 chain 모양의 연결 리스트로 연결하는 방법 = 오픈 해시법 open hashing
해시값이 같은 데이터 저장하기
체인법에서는 해시값이 같은 데이터를 연결 리스트에 의해 체인 모양으로 연결
배열의 각 버킷(해시 테이블)에 저장하는 것 = 인덱스를 해시값으로 하는 연결 리스트의 앞쪽 노드 head node를 참조하는 것
# 체인법으로 해시 함수 구현하기
# 실습 3-5
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 클래스 = 개별 버킷 = 키와 값이 짝을 이루는 구조
- key : 키(임의의 자료형)
- value : 값(임의의 자료형)
- next: 뒤쪽 노드를 참조(Node형)
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)
Chainedhash 해시 클래스 만들기
- capacity: 해시 테이블의 크기(배열 table의 원소 수)
- table: 해시 테이블을 저장하는 list형 배열
__init__() 함수로 초기화하기
__init__() 함수 : 빈 해시 테이블을 생성
매개변수 capacity에 전달받는 것은 해시테이블의 크기
hash_value() 해시 함수 만들기
hash_value() 함수는 인수 key에 대응하는 해시값을 구함
키로 원소를 검색하는 search() 함수
search() 함수가 key인 원소를 검색하는 과정
- 해시 함수를 사용하여 키를 해시값으로 변환
- 해시값을 인덱스로 하는 버킷에 주목
- 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 스캔, 키와 같은 값 발견 => 검색 성공 / 원소의 맨 끝까지 스캔해도 발견되지 않음 => 검색 실패
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 # 검색 실패
원소를 추가하는 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 # 삽입 성공
원소를 삭제하는 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가 존재하지 않음)
원소를 출력하는 dump() 함수
모든 원소를 덤프 => 해시 테이블의 내용을 한꺼번에 통째로 출력
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()
'공부 > TIL' 카테고리의 다른 글
[Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편] 03. 검색 알고리즘-1 (1) | 2024.02.15 |
---|---|
[Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편] 02. 기본 자료구조와 배열 (0) | 2024.02.01 |
[Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편] 01. 알고리즘 기초 (1) | 2024.01.26 |
[한 권으로 읽는 컴퓨터 구조와 프로그래밍] (0) | 2024.01.17 |
[SQL 첫걸음] 32강 - 36강 (0) | 2024.01.15 |