해시법

해시법 : 데이터를 저장할 위치 = 인덱스를 간단한 연산으로 구하는것

해시법은 원소의 검색뿐 아니라 추가,삭제도 효율적으로 수행할 수 있다.

해시값 : 키값을 원소의 갯수로 나눈 값

해시 충돌 : 18(키 값)을 원소갯수가 13인 배열에 저장하려고 할 때,여기서 해시값은 5이다.
그럼 이 키 값을 x[5]에 저장해야하는데, 배열x[5]에 이미 값이 있을때 해시 충돌이 일어나는 것이다.

이렇게 해시법에서 충돌이 발생하는경우에 2가지 방법으로 대처할 수 있다.

체인법 : 해시값이 같은 원소를 연결리스트로 관리
오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복

체인법

체인법에서는 해시값이 같은 데이터를 연결리스트에 의해 체인 모양으로 연결한다. 배열의 각 버킷에 저장하는 것은 인덱스를 해시값으로하는 연결 리스트의 앞쪽 노드를 참조하는 것이다.

x[5] - 10 - 11 - 12

#체인법으로 해시 함수 구현하기
from typing import Any, Type
import hashlib

class Node:
    def __init__(self, key:Any, value : Any, next : None) -> None:
        #""초기화""
        self.key = key
        self.value = value
        self.next = next
class Chainhash:
    #""체인법으로 해시 클래스 구현""

    def __init__(self, capacity : int):
        #""초기화""
        self.capacity = capacity
        self.table = [None] * self.capacity

    def hash_value(self, key : Any):
        #""해시값 구하기""
        if instance(key, int):
            return key % self.capacity
        return(int(hashlib.sha256(str(key).encode()).hexdigest(), 16) % self.capacity)

capacity : 해시 테이블의 크기(table의 원소 수)
table : 해시테이블을 저장하는 list형 배열

해시 테이블의 각 버킷은 맨 앞부터 table[0],table[1],table[2] ... table[capacity -1] 순으로 접근 가능하다.

key가 int형인 경우

key를 capacity로 나눈값을 해시로 하여 바로 사용가능하다.

key가 int형이 아닌 경우

key가 정수가 아닌겨우 그 값으로는 바로 나눌 수 없기 때문에 형 변환을 해야 해시값을 구할 수있다.