해시 알고리즘 (Hash Algorithm)

해시를 모르는 상태에서
사진에 나와있는것처럼 a 배열에 35 추가한다고 가정해보자
x의 원소 수는 13이고 앞에서부터 10개의 데이트가 오름차순으로 저장되어 있음

히히 책에서 가져왔떠염 뿌우 >.<

원소를 추가하는 과정은 다음과 같다
1. x[5]와 x[6] 사이에 값이 추가되도록 이진 검색을 이용하고
2. b 원소 처럼 x[6] 이후의 모든 원소를 한 칸씩 뒤로 이동 시키고
3. x[6]에 35를 대입함

결과론적으로 봤을땐 추가한것 맞지만 추가하면서 생기는 복잡도는O(n)이고 비용도 작지 않음
물로 삭제를 할때도 똑같은 비용을 발생시킴 왜냐!?

모든 데이터는 공백을 허용하지 않아요

너무 복잡해서..

눈물이 나네..

그래서 우리가 알아볼 해시법을 알아보자... let`s get it!

해시법

해시법(hashing)은 '데이터를 저장할 위치 == index' 를 간단한 연산으로 구하는 것을 말함
이 방법은 원소의 검색뿐 아니라 추가 . 삭제도 효율적으로 수행할 수 있음

예시를 보여주기 위해 a 나타낸 배열의 키(원소의 값)를 원소 개수를 13으로 나눈 나머지를 만들어봄

히히 책에서 봣떠염 뿌우 >.< [표 1-1]

배열의 키를 나눠서 나머지 값을 해시값(hash value)라고 함 이 해시값은 데이터에 접근할 때 기준이 됨
지금 해당 [표1-1]에서 구한 해시값을 인덱스로 하여 원소를 새로 저장한 배열이 해시 테이블이라고 하는거임

고러면 이 해당 표에 해시값을 구한 인덱스로 배열에 저장을 다시 보여주면 다음과 같다라는거임..
예를 들어 내가 35라는 원소를 추가한다고 가정하면

1. 내가 추가한 원소(35) 를 배열 총 원소 개수(13)을 나눈 나머지를 구하고
2. 그 구한 나머지가 인덱스 번호로 저장하면 된다...

삐뚤뺴둘 양해점 히.. [표 2-2]

그러면 아까와 달리 원소의 이동없이 원소를 추가하면 되니 얼마나 저렴하고 얼마나 쉽고 얼마나 단순한가..!

주모 샷다 내려!!

이렇게 키를 해시값으로 변환하는 과정을 해시 함수(hash function)이라고 함 또한
일반적으로 해시 함수는 나머지를 구하는 연산 또는 그 연산을 응용할때 많이 씀 해시 테이블에서 만들어진 원소를 버킷이라고함

해시 충돌

우리가 앞에서 만든 해시 테이블[표 2-2]에 원소 18을 추가한다고 해보자.
아까와 같은 과정으로 18에다가 13을 나눈 나머지 5을 원소 5번째 위치에 추가하자 ㅈ..잠깐...!

값이 있잖아..?

이미 5번째는 5라는 값이 저장되어 있다 하지만 걱정마라... 키와 해시값을 대응관계가 꼭 1:1 일 필요는 없다는점..

키와 해시값은 일반적으로 다대일 관계이다.. 이처럼 저장할 버킷이 중복되는 현상을 해시충돌이라고한다..

그러면 이렇게 충돌되는 값은 어떻게 해결해야하나? 2가지 방법이 있는데
1. 체인법 : 해시값이 같은 원소를 연결 리스트로 관리한다..
2. 오픈 주소법 : 빈 버킷을 찾을 때 까지 해시를 반복한다

일단 첫번째로 체인법에 대해서 알아보자.

체인법

체인법(chaining)이란 해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결하는 방법을 말하며 오픈 해시법(open hashing)이라고함
일단그림으로 어떻게 저장되어 관리 되는지 ... 보자.. 주렁주렁 매달릴꺼다..

이것이 곶감인겨!

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

즉 한마디로 같은 나이대 사람이 일렬로 쭉 있어서 앞사람을 참조해서 그 대열을 유지한다고 보면됨


구현을 해보자...

# 체인법으로 해시 함수 구현하기

from __future__ import annotations

import hashlib
from typing import Any, Type


class Node:
    """해시를 구성하는 노드"""
    
    def __init__(self, key: Any, value: Any, next: Node) -> None:
        self.key = key       # 키
        self.value = value   # 값
        self.next = next     # 뒤쪽 노드 참조

일단 Node class 를 만드는데 이 Node 클래스는 개별 버킷을 나타낸다. 이 클래스는 3가지 필드가 있음

1. key : 키(임의의 자료형)
2. value : 값(임의의 자료형)
3. next : 뒤쪽 노드를 참조 (Node)

Node class 는 키와 값이 짝을 이루는 구조라고 볼 수 있음 키에 해시 함수를 적용하여 해시값을 구함 참조한다는걸
다음과같이설명 가능

참조 물론 파이썬 변수는 객체 참조로 이루어진거임 Node 만 참조한다는건 아님 ㅇㅇ

class ChaineHash:
    """체인법으로 해시 클래스 구현"""
    
    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)

본격적으로 해시를 만들텐데 해시 클래스는 2개로 구성할 수 있음

1. capacity = 해시 테이블 크기를 나타냄
2. table = 해시 테이블을 저장하는 list형 배열

__init__( ) 함수로 초기화 하기

__init__ 함수는 capacity 에 의해 빈 해시 테이블을 생성함 매개변수 capacity에 전달받는 것은 해시 테이블의 크기
원소 수가 capacity 인 list형 배열 table을 생성하고 모든 원소를 None 으로 함 왜냐!?
해시 테이블의 각 버킷은 맨 앞부터 n-1 까지 접근할 수 있음

어떤 자료형이 들어갈지 어째알어

hash_value

많은 설명 필요 없이 해당 key를 해시를 만들기 위한 작업

키로 원소를 검색하는 search()함수

키를 어떻게 검색하냐.. 위쪽 그림을 끌고와서 설명하면..

이것이 곶감인겨!

33 을 검색하고 싶다..!
33의 해시값은 7이니깐.. 테이블이 가리키는 연결 리스트를 찾아감.. 20 --> 33 으로 찾아가서 성공함

26을 하고싶다..!
26의 해시값은 0임 값이 없기에 None 이므로 검색 실패함

그러면 검색을 하려면 다음 3가지의 결과로 도출할 수 있는데.

1. 해시 함수를 사용하며 키를 해시값으로 변환한다.
2. 해시값을 인덱스로 하는 버킷에 주목함
3. 버킷에 참조하는 연결 리스트를 맨 앞부터 차례로 스캔함 키와 같은 값이 발견되면 검색에 성공 아니면 실패

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

이쯤되면 눈치 빠른 사람들은 감이 올텐데 그 감이 맞는감 맛있는 감일꺼임

예를 들어 원소 13을 추가하고싶다면 먼저 해시값 변환하면 값은 0 그러면 13을 저장하는 노드를 새로 생성하고
그 노드에 대한 참조를 table[0]에 대입함

46을 추가하고싶다..
46의 해시값은 7인데 이미 있네? 뭐가 20과 33을 연결한 연결리스트에 대한 참조가 저장되어 있음
근데 46은 존재하지 않으니 연결 리스트 맨앞에 추가함

구체적으로 말하면
46을 저장하는 노드를 생성하고 그 노드 에 대한 참조를 table[7]번째로 대입 그다음 다 연결시키면 끝이다 이거임 ㄹㅇㅇ ㅋㅋ

결론을 도출하면 다음과같음

1. 해시 함수 변환
2. 해시값을 인덱스로 하는 버킷에 주목함
3. 선형 검색을 진행해서 키와 같은 값이 발견되면 이미 등록되어 있으므로 저장 실패 원소의 맨 끝까지 발견되지 않았으면 리스트의 맨 앞에 노드를 추가함

    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       # 노드 추가

원소를 삭제하는 remove()함수

키가 key인 원소를 삭제함 예를 들어
69의 해시값은 4임 69가 저장되어 있은 table[4]의 버킷에 저장되어 있는 참조하는 곳의 리스트를 선형 검색하면 69를발견할 수 있음
이 노드의 뒤쪽 노드는 17을 저장함 즉 참조구간에서 앞쪽 노드를 지우고 뒤쪽 노드를 저장했다.. 라고보면됨

1. 해시 변환
2. 버킷 주목
3. 버킷이 참조하는 연결 리스트를 맨 앞부터 선형 검색 키와 같은 값이 발견되면 리스트에서 그렇지 않으면 실패..

 
    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:
                if pp is None:
                    self.table[hash] = p.next 
                else:
                    pp.next = p.next 
                return True
            
            pp = p
            p = p.next     # 뒤쪽 노드를 주목 
        return False

해시에 대해서 알아보았다.. 재미있으면 추천..!