출처: Do it! 자료 구조구조와 함께 배우는 알고리즘 입문 - 파이썬 편
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 = Nonde(key,value,self.table[hash])
self.table[hash]= temp #노드를 추가
return True #추가 성공
search 함수()
hash_value를 통해 키를 해시값으로 변환 ->
해당 해시값을 인덱스로 하는 버킷에 주목 ->
버킷이 참조하는 노드들을 맨 앞 부터 스캔 ->
키와 같은 값이 발견되면 검색에 성공, 원소의 맨 끝까지 스캔하여 발견되지 않으면 검색에 실패
만약 33을 검색한다고 했을 때, 33의 해시값은 7이다. table[7]이 가리키는 노드들을 따라 나서면,table[7]이 None 이 아니면, 뒤쪽 노드 20에 주목하여 검색을 성공 할 수 있다.
만약 26을 검색한다고 했을 때, 26의 해시값은 0이고 이는 None이다. None을 반환하므로 검색에 실패한다.
add() 함수
hash_value를 통해 키를 해시값으로 변환 ->
해당 해시값을 인덱스로 하는 버킷에 주목 ->
버킷이 참조하는 리스트를 맨 앞부터 스캔, 키와 같은 값이 발견되면 이미 등록된 경우이므로 추가실패(return False)
맨 끝까지 발견되지 않으면 해시값인 리스트의 맨 앞의 노드를 추가
만약 13을 추가한다고 할때, 해시값은 0 , table[0] = None이다 13을 저장하는 리스트를 새로 생성하고, 노드에 대한 참조를 table[0]에 대입한다.
만약 46을 추가한다고 할때 46의 hash value는 7, table[7] 노드에는 20과 33을 연결한 연결리스트에 대한 참조가 저장되어 있다. 46은 저장되어 있지 않으므로 맨 앞에 46을 저장하는 노드를 생성하고, 참조를 table [7]에 대입한다.
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: #pp가 첫번째 노드인 경우
self.table[hash] = p.next #다음 노드로 업데이트
else:
pp.next = p.next #pp.next를 p.next로 업데이트하여 p 노드를 삭제
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(t,end= '')
while p is not None:
print(f' -> {p.key}({p.value})',end='')
p = p.next
print()
remove() 함수
hash_value를 통해 키를 해시값으로 변환 ->
해당 해시값을 인덱스로 하는 버킷에 주목 ->
버킷이 참조하는 리스트를 맨 앞부터 스캔, 키와 같은 값이 발견되면 그 노드를 리스트에서 삭제
69의 해시값은 4이다. table[4]의 버킷에 저장되어 있는 참조하는 곳의 리스트를 선형검색하면 69를 발견할 수 있고, 뒤쪽노드는 17을 저장한다. 17을 저장한 노드에 대한 참조를 table[4] 버킷에 대입하면 노드가 삭제된다.
dump() 함수
해시테이블의 내용을 한꺼번에 출력한다. 모든원소인 table[0]~table[capacity-1] 까지 뒤쪽 노드를 찾아가면서 각 노드의 키와 값을 출력하는 작업을 반복한다. 이 함수를 실행하면 해시값이 같은 버킷이 연결 리스트에 의해 체인 모양으로 묶인모습을 확인할 수 있다.
00
01 -> 14
02
03 -> 29
04 -> 69 -> 17
05 -> 05
06 -> 06
07 -> 46 -> 20 -> 33
08
09
10
11
12
오픈 주소법
충돌이 발생했을 때 재해시를 수행하여 빈 버킷을 찾는 방법을 말하며 닫힌 해시법이라고도 한다.
원소 추가하기
a에서 18을 추가하여 충돌이 발생했다. 이럴때 재해시를 수행한다. 키에 1을 더하여 13으로 나눈 나머지를 사용한다.
(18+1) % 13으로 나머지 6이 나왔다. 하지만 값이 있으므로 재해시를 통해 (19+1) % 13을 수행한다. 7이 나오므로 인덱스 7인 버킷에 18을 추가한다.
원소 삭제하기
버킷이 비어있는 상태를 -로, 삭제 완료된 상태를 ★로 나타낸다.
원소 검색하기
17을 검색한다고 가정했을때, 해시값이 4인 버킷을 들여다보면 속성은 비어있음(-) 으로 검색실패이다.
18을 검색하는 경우를 봤을 때 5인 버킷의 속성은 삭제완료 ★ 이다. 재해시하여 6인 버킷의 속성을 보면 값이 있으므로 다시 재해시 하여 7인 버킷값을 본다. 검색하는 값 18이 저장되어 있다.
오픈 주소법으로 해시 함수 구현하기
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=Npne, value: Any=Npne, 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 and p.key == key:
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 # 이키는 등록되어 있지 않음
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('-- 삭제 완료--')