3. 자료구조 - 해쉬 테이블

1. 해쉬 테이블

   : Key와 Value를 저장하는 데이터 구조

   : Key값을 해시 함수에 적용한 결과를 통해 저장한 데이터(Value)에 접근할 수 있음

   : 장점) 데이터 접근/검색 속도가 굉장히 빠름 -> 충돌이 없는 경우, 시간 복잡도 = O(1) ,

            특정 Key에 대한 데이터가 있는지/중복을 확인하기 쉬움

   : 단점) 보통 배열로 미리 해쉬 테이블 사이즈만큼을 생성 후 사용 (공간과 탐색 시간의 trade-off),

            여러 키에 해당하는 해쉬 주소가 동일할 경우, 충돌을 해결하기 위한 별도의 자료구조가 필요

             (ex- 링크드 리스트)

   : 활용) 검색/저장/삭제/읽기가 빈번하게 필요한 경우, 캐시 구현 (중복 확인이 쉽기 때문)

 

     ex - 파이썬의 딕셔너리 구조

 

   : Key값에 해싱 함수(Hashing Function)를 적용하여 고정 길이의 해쉬 주소(Hash Address)를 알아내고,

    이 주소 값을 통해 Value가 저장되어 있는 슬롯(Slot)의 위치를 일관성 있게 찾을 수 있음 

 

                 Key -> Hashing Function -> Hash Address -> Slot to save Data

   

  : 단, 저장할 데이터에 대해 Key를 추출할 수 있는 별도의 함수가 존재할 수 있음 

      - ex) python 내장 함수 hash() : 컴퓨터를 껐다 킬 때마다 주어지는 키 값이 다르므로 사용을 권장하진 않음

 

2. 간단한 해쉬 테이블 구현

 - Example: 리스트 타입 활용

   1) 해쉬 함수 : Key %8

   2) 해쉬 키 생성 : 파이썬 내장 함수 hash() 사용

 

myhash = list([0 for i in range(8)])    # 8 element list initialized as 0 

def get_key(data):					# Use data to get key
   key  = hash(data)	
   return key

def hashing_func(key):					# Use calculated key to get hash address
   hash_addr = key %8
   return hash_addr
   
def insert(data, value):				# data is for making key, value is real data
   hash_addr = hashing_func(get_key(data))
   myhash[hash_addr] = value

def getdata(data):
   hash_addr = hashing_func(get_key(data))
   return myhash[hash_addr]                    # return value

 

3. 충돌 (Collision) 해결 알고리즘

   : 여러 Unique 키의 해당하는 주소 값이 같은 경우를 해쉬 충돌이라고 함. -> 이런 경우, 별도의 자료 구조가 필요

 

   1) Chaining 기법

       : Open Hashing 기법 중 하나. 즉, 기존의 해쉬 테이블 저장 공간이 아닌 새로운 공간을 활용하는 기법

         -> 주로 "링크드 리스트"를 활용하여 해당 주소에 데이터를 연결

 

myhash = list([0 for i in range(8)])

def get_key(data):
   return hash(data)

def hashing_func(key):
   return key%8

def write_data(data,value):
   index_key = get_key(data)
   hash_addr = hashing_func(index_key)
   if myhash[hash_addr] != 0:           # 해쉬 테이블의 해당 주소에 값이 있는 경우
      for index in range(len(myhash[hash_addr])):     #여러 값이 저장되어 있는 경우
         if myhash[hash_addr][index][0] == index_key:     # 키 값이 index_key와 같으면 값을 갱신
            myhash[hash_addr][index][1] = value
            return
      myhash[hash_addr].append([index_key, value])  # 해당 주소의 값을들 모두 체크했음에도 해당 index_key를 가진 데이터는 없는 경우 -> 그 주소의 리스트에 더해줌
   else:
      myhash[hash_addr] = [index_key, value]     # 저장된 값이 없다면, 새로 저장
  
def read_data(data):
   index_key = get_key(data)
   hash_addr = hashing_func(index_key)
   if myhash[hash_addr] !=0:
      for index in range(len(myhash[hash_addr])):
         if myhash[hash_addr][index][0] == index_key:
            return myhash[hash_addr][index][1]
      return None                               # 해당 주소의 리스트를 다 돌았음에도 해당 데이터가 없음
   else:                                        # 해당 주소에 저장되어있는 데이터가 없음
      return None
   

 

   2) Linear Probing 기법

       : Close Hashing 기법 중 하나. 기존의 해쉬 테이블 저장 공간 안에서 충돌 문제를 해결하는 기법

       : 충돌이 발생하면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈 공간에 저장하는 기법

         -> 저장 공간의 효율을 높일 수 있음

         -> 해당 address에 저장된 값이 있으면, index key에 의해 애초에 배정받은 address인지

             충돌에 의해 저장되어 있는 데이터인지 확인 필요

 

myhash = list([0 for i in range(8)])

def get_key(data):
   return hash(data)

def hashing_func(key):
   return key%8

def write_data(data,value):
   index_key = get_key(data)
   hash_addr = hashing_func(index_key)
   if myhash[hash_addr] != 0:           # 해쉬 테이블의 해당 주소에 값이 있는 경우
      for index in range(hash_addr, len(myhash)):   # 현재 주소부터 테이블 끝까지 빈 공간 탐색
         if myhash[index] == 0:          # 빈 공간에 저장
            myhash[index] = [index_key, value]
            return
         elif myhash[index][0] == index_key:     # index_key가 같은 경우 값을 갱신
            myhash[index][1] = value
            return
   else:                                # 해당 주소에 저장된 값이 없는 경우
      myhash[hash_addr] = [index_key, value]
      return
      
def read_data(data):
   index_key = get_key(data)
   hash_addr = hashing_func(index_key)
   if myhash[hash_addr] !=0:
      for index in range(hash_addr, len(myhash)):
         if myhash[index][0] == index_key:
            return myhash[index][1]
      return None                               # 해당 주소의 리스트를 다 돌았음에도 해당 데이터가 없음
   else:                                        # 해당 주소에 저장되어있는 데이터가 없음
      return None
   

 

   3) 충돌을 개선하는 방법

       : 해쉬 함수를 재정의하거나 해쉬 테이블 저장 공간을 확대

   

   4) 해쉬 함수와 키 생성 함수

       - SHA (Secure Hash Algorithm) : 어떤 데이터도 유일하고 고정된 크기의 값을 리턴

          ex) SHA-1, SHA-256 (길이가 더 긺)

     

import hashlib         # must import library

def get_key(data):
   hash_object = hashlib.sha256()    # SHA-1: just change to "sha1"
   hash_object.update(data.encode())   # data.encode: change to "byte"
   hex_dig = hash_object.hexdigest()    # change to hexadecimal
   return int(hex_dig, 16)           # output as int16

 

더 공부해서 익숙해지자.