Hash 함수

Hash 함수란?

해시 함수(hash function)는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다

 

Hash 함수를 파이썬에선 제공해준다.

가령, Console 창에서 hash("KEY")를 입력한다면 이상한 숫자가 나올 것이다.

주소값이라고 생각하면 된다.

 

파이썬이 좋은 점은 배열, 링크드리스트, 스택, 큐 등등.. 모두 리스트로 구현한다는 점이다.

거기에 더해서 해시함수를 제공하기 때문에 리스트 길이 만큼을 나눠서 나오는 나머지를 리스트의 키로 잡고

해시함수를 만들면 된다.

 

다음과 같이 만들면 된다.

items[hash("apple")] = "사과" 

이를 코드로 짜보면 아래와 같다.  해시함수의 테이블 크기를 8로 두고 만들었을때 다음과 같다.

Dictionary 구조로 만든 다음에 Key값을 조회해서 Value를 뽑는 과정이며, Dictionary크기(리스트) 만큼

hash함수로 나눠서 인덱스를 만든다.

만든 인덱스가 기입한 Key값의 해싱값, 즉 리스트의 Key값이 된다.

 

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

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

   def get(self, key):
       index = hash(key) % len(self.items)
       if self.items[index] is None:
           return "Key is not existed"

       return self.items[index]

 

 

여기서 문제가 있다.

hash함수를 써서 Key를 해싱하여 어떤 특정의 값이 나왔다고 가정하자 (예제에 따르면 8 미만의 값)

만약 Key가 겹친다면..?? 어떻게 조치할 것인가??

방법은 2가지가 있다.

 

1. Chaining

체이닝 방법은 리스트 내에 들어간 K, V 구조를 링크드 리스트로 재구현 하는 것이다.

Dictionary 형태를 튜플로 처리하는 것과 같다.

 

class LinkedTuple:

    def __init__(self):

         self.items = list()

    def add(self, key, value):

         self.items[key].append((key, value))

    def get(self, key):

         for k, v in self.items:

             if key == k:

                 return v

 

class LinkedDict:

      def __init__(self):

          self.items = []

          for i in range(8): # LinkedDict라는 클래스에 객체를 만들때, items라는 리스트를 초기화하고 여기에 8 크기 만큼

              self.items.append(LinkedTuple()) # LinkedTuple을 넣어둔다. (K, V)로 구현된 딕셔너리를 리스트에 넣기

      def put(self, key, value):

           index = hash(key) % len(self.items)

           self.items[index].add(key, value)

      def get(self, key):

           index = hash(key) % len(self.items)

           return self.items[index].get(key)

 

이렇게 하게 된다면, Dictionary구조로 되어 있는 값들이 리스트에 같은 해싱된 키 값으로 들어갈 지라도, 

LinkedTuple이라는 클래스 내 get 함수의 Key로 접근하기 때문에 유일성이 성립된다. 

해시함수로 만든 키는 중복될지언정, 실제 해당 리스트에 들어간 값을 찾는 키는 유일하기 때문에 Overwrite가 될 경우가 없다는 것이다. 

 

2. Open Addressing

이 방법은 해시함수로 구현된 Key값으로 해당 키에 대한 값이 존재하는지, 

여유 공간이 남아 있는지 체크한 후 값을 넣는 방법이기 때문에 Key가 중복되어 Overwrite될 일은 없다.