5. 해쉬 테이블(Hash Table)

해쉬 테이블(Hash Table)

해쉬 구조

• key에 value를 저장하는 데이터 구조
• 파이썬에서는 딕셔너리 타입을 사용하면 돼서 구현할 이유가 없음

 

용어

• Hash : 임의 값을 고정 길이로 변환하는 것
• 해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해싱 함수 : key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해쉬 값 또는 해쉬 주소 : key를 해싱 함수로 연산해서, 해시 값을 알아내고, 이를 기반으로 해시 테이블에서 해당 key 에 대한 데이터 위치를 일관성 있게 찾을 수 있음
• 슬롯 : 한 개의 데이터를 저장 할 수 있는 공간
• 저장할 데이터에 대해 key를 추출할 수 있는 별도 함수도 존재할 수 있음

 

예

hash_table = list([i for i in range(10)])
print(hash_table)

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

• 간단한 해시 함수 만들기

def hash_func(key) :
  return key % 5

# ord : 아스키코드 변환 메소드
print (ord(data1[0]), ord(data2[0]), ord(data3[0]))
print (ord(data1[0]), hash_func(ord(data1[0])))
print (ord(data1[0]), ord(data4[0]))

65 68 84
65 0
65 65

 

• 값 저장

def storage_data(data, value) :
  key = ord(data[0])
  hash_address = hash_func(key)
  hash_table[hash_address] = value

 

• 값 읽기

def get_data(data) :
  key = ord(data[0])
  hash_address = hash_func(key)
  return hash_table[hash_address]

 

해쉬 테이블 장단점

• 장점
  • 데이터 저장, 읽기 속도가 빠르다
  • 키에 대한 데이터가 있는지 중복 확인이 쉬움
• 단점
  • 일반적으로 저장 공간이 좀 더 많이 필요함
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함
• 주요 용도
  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐쉬 구현 시(중복 확인이 쉬움)

 

연습

• 리스트 변수를 사용해서 해쉬 테이블 구현하기
  • 해쉬 함수 : key % 8
  • 해쉬 키생성 : hash(data)

hash_table = list([0 for i in range(8)]) 
  
def get_key(data) :
  return hash(data)

def hash_function(key) :
  return key % 8

def save_data(data, value) :
  hash_address = hash_function(get_key(data))
  hash_table[hash_address] = value
  
def read_data(data) :
  hash_address = hash_function(get_key(data))
  return hash_table[hash_address]

 

충돌 collision 해결 알고리즘

• chaining 기법
  • 개방 해슁 또는 open hashing 기법 중 하나 : 해쉬 테이블 저장공간 외의 공간을 활용하는 방법
  • 충돌이 일어나면, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법

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

def get_key(data) :
  return hash(data)

def hash_function(key) :
  return key % 8

def save_data(data, value) :
  index_key = get_key(data)
  hash_address = hash_function(index_key)
  if hash_table[hash_address] != 0 :
    for index in range(len(hash_table[hash_address])) :
      if hash_table[hash_address][index][0]  == index_key :
        hash_table[hash_address][index][1] = value
        return
    hash_table[hash_address].append([index_key,value])
  else : 
    hash_table[hash_address] = [[index_key, value]]

def read_data(data) :
  index_key = get_key(data)
  hash_address = hash_function(index_key)
  
  if hash_table[hash_address] != 0 :
    for index in range(len(hash_table[hash_address])) :
      if hash_table[hahs)address][index][0] == index_key :
        return hash_table[hash_address][index][1]
    return None
  else : return None

 

• Linear Probing 기법
  • 폐쇄 해싱 또는 close hashing 기법 중 하나 : 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
  • 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법

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

def get_key(data):
  return hash(data)

def hash_function(key) :
  return key % 8

def save_data(data,value) :
  index_key = get_key(data)
  hash_address = hash_function(index_key)
  if hash_table[hash_address] != 0 :
    for index in range(hash_address, len(hash_table)) :
      if hash_table[index] == 0 :
        hash_table[index] = [index_key, value]
        return
      elif hash_table[index][0] == index_key :
        hash_table[index][1] = value
        return
  else :
    hash_table[hash_address] = [index_key, value]

def read_data(data) :
  index_key = get_key(data)
  hash_address = hash_function(index_key)  
  if hash_table[hash_address] != 0 :
    for index in range(hash_address, len(hash_table)) :
      if hash_table[index] == 0 :
        return None
      elif hash_table[index][0] == index_key :
        return hash_table[index][1]
  else : return None

 

시간복잡도

• 일반적인 경우 O(1)
• 최악의 경우 O(n)