해쉬 - 해쉬 테이블, 해쉬 함수, 체이닝, 개방 주소법

👀 해쉬란?

👉 해쉬 알고리즘을 통해서 문자열을 고정된 길이의 데이터로 만드는 방식

(미니 프로젝트에서 비밀번호 암호화 할 때 사용한 게 해쉬였다!)

해쉬를 사용하면 블록체인이라는 기술에서도 쓰이기도 하고, 효율적인 자료구조인 딕셔너리를 만들 때도 사용 됩니다!

 

👀 딕셔너리란?

👉 사전형 데이터를 의미하며, key와 value를 1대1로 대응시킨 형태입니다.

(참고 사이트 http://tcpschool.com/python/types_dictionary)

---

👀 해쉬 테이블이란?

컴퓨팅에서 키를 값에 매핑 할 수 있는 구조인, 연관 배열 추가에 사용되는 자료구조이다.

해쉬 테이블은 해쉬 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열에 계산합니다.

데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행됩니다.

 

파이썬에서 딕셔너리를 사용 해보신 적이 있나요!?

키로 데이터를 저장하고 찾을 수 있는 방법이죠!

딕셔너리를 해쉬 테이블이라고 부르기도 합니다.

즉, 딕셔너리, 해쉬 테이블! 같다고 봐도 무방합니다.

dict = {"fast" : "빠른", "slow" : "느린"}

키를 통해 바로 데이터를 받아 올 수 있어서 속도가 획기적으로 빨라집니다.

 

찾는 데이터가 있는 배열을 다 둘러보지 않아도

키에 대해서 검색하면 바로 값을 조회 할 수 있는 아주 좋은 자료구조입니다.

 

그런데 이 딕셔너리가 사실 내부적으로는 배열을 사용한다는 사실!

class Dict:
    def __init__(self):
        self.items = [None] * 8

 

❓ 그러면 "fast" 와 "slow" 의 값인 "빠른"과 "느린" 이 배열 어딘가에 있다고 할게요.

그럼 그 인덱스를 몇번에 넣어야 하는지, 몇번에서 찾아야 하는지 어떻게 찾아주는 걸까요?

바로 해쉬 함수라는 걸 이용합니다.

 

👀 해쉬 함수(Hash Function)이란?

임의의 길이를 갖는 메세지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수입니다.

(이미 파이썬에서는 hash(Object)를 제공하고 있습니다!)

>>> hash("fast")
-146084012848775433
>>> hash("slow")
7051061338400740146

❓ 엇 그러면 이 값들을 이용해서 어떻게 배열에 넣을까요??

 

마이너스 값도 있고, 무지막지하게 큰 값도 있는데..

 

바로, 배열의 길이로 나눈 나머지 값을 쓰면 됩니다.

 

예를 들어 배열의 길이가 8이라면,

8로 나눈 나머지는 0~7이기 때문에

무조건 배열 내부의 인덱스로 연결될 것이라는 걸 알 수 있습니다!

 

그럼 이 개념을 가지고 한 번 간단하게 딕셔너리를 구현해보겠습니다.

딕셔너리에는 put과 get 함수가 필요합니다!

 

👉 put(key, value) : key 에 value 저장하기

def put(self, key, value):
    index = hash(key) % len(self.items)
    self.items[index] = value

👉 get(key) : key 에 해당하는 value 가져오기

def get(self, key):
    index = hash(key) % len(self.items)
    return self.items[index]

 

그러나 만약 해쉬의 값이 같다면 같은 어레이의 인덱스로 매핑이 되어서 데이터를 덮어 써버리는 결과가 발생합니다.

이를 충돌(collision)이라고 합니다!

 

👉 충돌을 해결하는 첫번째 방법은 링크드 리스트를 사용하는 방식입니다.

이 방식을 연결 지어서 해결한다고 해서 체이닝(Chaining)이라고 합니다.

class LinkedTuple:
    def __init__(self):
        self.items = []

    def add(self, key, value):
        self.items.append((key, value))

    def get(self, key):
        for k, v in self.items:
            if k == key:
                return v

 

👉 충돌을 해결하는 두번째 방법은 배열의 다음 남는 공간에 넣는 것입니다!

이를 개방 주소법(Open Addressing)이라고 합니다.

---

👨‍🏫 정리하자면!

 

해쉬 테이블(Hash Table)은 "키" 와 "데이터"를 저장함으로써

즉각적으로 데이터를 받아오고 업데이트하고 싶을 때 사용하는 자료구조입니다.

 

해쉬 함수(Hash Function)는 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수입니다.

 

해쉬 테이블의 내부 구현은 키를 해쉬 함수를 통해 임의의 값으로 변경한 뒤

배열의 인덱스로 변환하여 해당하는 값에 데이터를 저장합니다.

 

그렇기 때문에 즉각적으로 데이터를 찾고, 추가할 수 있는 것 입니다.

 

만약, 해쉬 값 혹은 인덱스가 중복되어 충돌이 일어난다면?

체이닝과 개방 주소법 방법으로 해결할 수 있습니다!