python_해시법

해시법(hashing)

'데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구한는 것

해시 테이블(hash table)

해시값을 인덱스로 한 배열

해시 함수(hash function)

키를 해시값으로 변환하는 과정

버킷(bucket)

해시 테이블에서 만들어진 원소

해시값(hash value)

배열의 키를 원소 개수로 나눈 나머지

해시 충돌(collision)

버킷이 중복되는 현상

충돌 대처법에는 체인법, 오픈 주소법이 있다.

체인법 (chaining)

해시값이 같은 데이터를 체인모양의 연결리스트로 연결하는 방법

*참조: b=a를 실행하면 a가 참조하는 객체를 b도 참조한다.

노드(Node) 클래스

자기 참조형 클래스 (next가 자신과 같은 자료형인 인스턴스 참조)
key, value, next(뒤쪽 노드를 참조)를 포함함

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

해시 클래스

init함수로 초기화

capacity

해시 테이블의 크기 (원소 수)

table

해시 테이블을 저장하는 list 배열

#키에 대응하는 해시값 구하기
class ChainedHash:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.table = [None] * self.capacity #None인 list형 배열 생성
        
    def hash_value(self, key: Any) -> int:
        if isinstance(key, int): #key가 int형인가
            return key % self.capacity #%는 나머지 반환
        return (int(hashlib.sha256(str(key).encode())hexdigest(), 16) % self.capacity)

search()

key인 원소 검색 함수
앞에서부터 차례로 스캔

def search(self, key: Any) -> Any:
    hash = self.hash_value(key) #해시값
    p = self.table[hash] #해시값을 인덱스로
    
    while p is not None: #p가 None이 아니라면
        if p.key == key: #해시값 인덱스가 key와 같다면
            return p.value #검색 성공
        p = p.next #다음 노드
    return None #검색 실패 

add()

끝까지 발견되지 않으면 노드 추가

def add(self, key: Any, value: Any) -> bool:
	hash = self.hash_value(key) #추가하는 해시값
    p = self.table[hash] #노드
        
    while p is not None: #p가 None이 아니라면
        if p.key == key: #p.key랑 key가 같으면 / 값 있으면 안됨
            return False #실패
        p = p.next #다음 노드
            
    temp = Node(key, value, self.table[hash])  #노드 생성
    self.table[hash] = temp #추가
    return True #성공

remove()

def remove(self, key: Any) -> bool:
	hash = self.hash_value(key) #key 해시값
	p = self.table[hash] #노드
    pp = None #다음 노드 None
        
    while p is not None: #p가 None이 아니면
       if p.key == key: #같을 때
          if pp is None: #pp가 None
             self.table[hash] = p.next #해시값이 다음 노드 참조
          else:
          	pp.next = p.next
          return True #삭제 시 return을 만나 함수 종료
            #3개 연결, 중간 값 삭제하고 싶을 때
            #첫 번째 값은 key가 같지 않으므로 실행 x
            #첫 번째 노드가 pp가 됨 == 동시에 p
            #따라서 p.next가 두 번째 값
            #다시 key 값 검사
       pp = p 
       p = p.next
    return False

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()

오픈 주소법(open addressing)

충돌 시 재해시를 수행하여 빈 버킷을 찾는 방법
찾지 못하면 해시 +1을 수행한다.

[원소 표시]

• 데이터 저장되어 있음 -> 숫자
• 비어 있음 -> (-) : 같은 데이터는 존재하지 않습니다.
• 삭제 완료 -> * : 같은 데이터는 다른 버킷에 저장되어 있습니다.

버킷 속성

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    # 속성, 비어있음으로 설정

set()

모든 필드에 값 설정

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: #Status 지정
    self.stat = stat

OpenHash class

class OpenHash:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity #크기
        self.table = [Bucket()] * self.capacity #테이블

hash_value()

해시값 구함

def hash_value(self, key: Any) -> int:
	if isinstance(key, int): #key가 int type이면
       return key % self.capacity #계산
    return(int(hashlib.md5(str(key).encode()).hexdigest(), 16) % self.capacity)

rehash_value()

재해시값

def rehash_value(self, key: Any) -> int:
	return(self.hash_value(key) + 1) % self.capacity 
    #재해시는 해시값 +1

search

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: #데이터가 있거나 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: #p가 값이 있다면
       return p.value #값 리턴
    else:
       return None

add()

 def add(self, key: Any, value: Any) -> bool:
	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 

remove()

def remove(self, key: Any) -> int:
	p = self.search_node(key) #버킷
	if p is None: #등록되지 않은 값
		return False
    p.set_status(Status.DELETED)
    return True

dump()

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('-- 삭제 완료 --')