파이썬 해쉬 hash 간단구현 !!!

해쉬 테이블이란??

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

해시 테이블은 해시 함수를 사용하여 index를 버킷이나 슬롯의 배열로 계산한다. 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다.

 

해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

 

 

예를 들어 우리가 (Key, Value)가 ("kim", "1234")인 데이터를 크기가 16인 해시 테이블에 저장한다고 하자. 그러면 먼저 index = hash_function("kim) % 16 연산을 통해 index 값을 계산한다. 그리고 array[index] = "1234" 로 저장하게 된다.

파이썬의 딕셔너리를 해쉬 테이블이라고 부르기도 한다.

사실 놀랍게도 이 딕셔너리도 내부적으로는 배열을 사용하고 있다.

 

 

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

    def put(self, key, value):
        self.items[hash(key) % 8] = value
        return
    def get(self, key):
        return self.items[hash(key) % 8]

 

 

크기가 8인 해시테이블을 만들었다고 가정할 때 위와 같이 생성이 된다.

우리가 사용한 방식은 Division Method이다.

 

 Division Method : 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.( 주소 = 입력값 % 테이블의 크기) 

 

하지만 인덱스가 같다면 어떻할까? 해시값을 8로 나누었을 때 값이 겹치면 덮어버리게 되기에 이를 방지해주어야 한다. 그럼 같을 때 리스트를 사용하여 해결해보도록하자. 이 방법은 분리 연결법이라고 한다

 

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

    def add(self,key,value):
        self.items.append((key,value))
    def get(self,key):
        for i,j in self.items:
            if i == key:
                print(j)


class LinkedDict():
    def __init__(self):
        self.items = []
        for i in range(8):
            self.items.append(LinkedTuple())

    def add(self, key, value):
        idx = hash(key) % 8
        self.items[idx].add(key,value)

    def get(self, key):
        idx = hash(key) % 8
        self.items[idx].get(key)

 

 

먼저 LinkedTuple이라는 클래스를 만들어주었다. 이는 해쉬 테이블의 각 요소가 된다.

호출이 되면 리스트 하나를 만든다. 그리고 add 메서드와 get메서드를 정의해주자.

add메서드는 리스트에 튜플을 생성하여 더하는 기능을 수행하고

get메서드는 반복문 안에서 튜플의 0번째 인덱스의 값과 키 값이 일치하는 value값을 print해주는 역할을 한다.

 

그리고 LinkedDict에서도 마찬가지로 호출이 되면

8개의 LinkedTuple을 가진 배열을 만들었다.

 

그리고 add를 하면 idx값을 찾아서 그에 해당하는 linkedtuple의 add메서드를 사용

key값과, value를 추가해주었다.

 

get메서드는 마찬가지로 idx를 찾아 그 값에 해당하는 linkedtuple의 0번째 인덱스 와 받은 key값이 일치하면 일치하는 value의 값을 호출한다.

 

만약 linkeddict의 idx값이 2가 두번이 나왔다고 가정하면

               0                         1                         2

[ LinkedTuple, LinkedTuple, LinkedTuple, ...]

 

                              2(LinkedTuple)

[('abc',1),('hi',456),('gogo',123)]

 

여기에 값을 계속 추가해 나가는 방식이고, 반복문을통해 key값에 해당하는 value를 가져오는 것이다.