[자료구조] 해시테이블 체이닝 기법 개념 및 구현 with 파이썬(Python)

해시테이블이란 key에 data를 저장하는 데이터 구조이다. 파이썬의 딕셔너리 구조와 동일하다. key를 통해 data를 찾아가는 과정은 다음과 같다. key를 hash 함수에 넣고 일정한 길이의 해시 코드를 얻게 된다. 이후 3으로 나눈 나머지인 0, 1, 1이 index가 되며 이를 통해 data를 찾을 수 있다.

 

해시 테이블의 장점은 저장/읽기의 속도가 빠르다는 것이다. 따라서 검색, 조회가 빈번한 작업인 경우에 해시테이블을 활용하면 빠르게 데이터를 관리하는 효과를 얻을 수 있다.

하지만 장점이 있으면 단점이 있는법! index가 중복되는 경우 저장시에 충돌이 발생한다는 것이 단점이다. 해시 함수가 10을 나눈 나머지를 구하는 것이라고 가정해보자. 이러면 숫자 28을 10으로 나누면 8이 나머지이다. 이를 인덱스가 8번인 해시테이블에 28을 저장하여 관리하는 방식이 해시 테이블이다. 하지만 18의 나머지도 8이기 때문에 28과 18 데이터를 저장할테 충돌(collision) 이 발생하게 된다. 이를 해결하는 방법에는 링크드리스트 자료 구조를 사용하는 채이닝 기법과 빈공간을 찾아 저장하는 클로즈 기법이 있다.

 

 

---

채이닝 기법

같은 해시 함수의 결과를 갖는 18, 28의 경우 함께 저장할 수 없어 먼저 저장된 28번 뒤에 18번을 저장한다. 이때 자료구조는 링크드리스트를 사용한다.  링크드리스트 자료구조는 아래의 URL를 참고!

 

[자료구조] 링크드리스트 파이썬으로 구현

hash_address가 같은 경우에 저장을 코드로 구현해보자. 

Ddae 와 Date는 같은 7이라는 동일한 주소를 갖고 있다. 

print(hash('Doave') % 8)
print(hash('Ddae') % 8)
print(hash('Date') % 8)

4
7
7

 

채이닝 기법으로 해시테이블을 관리하는 코드이다.

# 0으로 채운 해시 테이블 생성
hash_table = list([0 for i in range(8)])

# 데이터에서 key값을 추출하기 위한 함수
def get_key(data):
  return hash(data)

# key값에서 데이터를 저장할 index를 가져온다.특정 숫자를 나눈 나머지가 index 가 된다. (0~9) 
def hash_function(key):
  return key % 8

# 체이닝 기법으로 데이터 저장
def save_data(data, value):
  # 데이터로 key를 만들고
  key = get_key(data)
  # key를 통해 value를 저장할 index를 구한다. (0~9)
  hash_address = hash_function(key)
  # index에 이미 데이터가 있다면
  if hash_table[hash_address] != 0:
    # len 함수를 링크드리스트의 길이를 파악한다. 파악하는 이유는 같은 index에 몇 개의 값이 저장되어 있는지 확인하기 위함이다.
    for index in range(len(hash_table[hash_address])):
      # 링크드리스트에 key가 있다면 value를 저장한다.
      if hash_table[hash_address][index][0] == key:
        hash_table[hash_address][index][1] = value
        return
    # 링크드리스트에 key의 값이 없다면 새롭게 추가한다.
    hash_table[hash_address].append([key, value])
  # index에 데이터가 없다면 링크드리스트를 만들어 key, value를 저장
  else:
    hash_table[hash_address] = [[key, value]]

def read_data(data):
  key = get_key(data)
  hash_address = hash_function(key)
  # 해당되는 hash_address에 데이터가 있는지 확인
  if hash_table[hash_address] !=0:
    # 링크드리스트를 순회하며 해당 key가 있다면 value를 리턴한다.
    for index in range(len(hash_table[hash_address])):
      if hash_table[hash_address][index][0] == key:
        return hash_table[hash_address][index][1]
    return None
  else:
    return None

 

잘 되었는지 테스트를 해보면 같은 주소를 갖은 Ddae, Date가 정상적으로 저장되어 read까지 되는 것을 확인 할 수 있다.

save_data('Doave', '해시테이블')
save_data('Ddae', '채이닝 기법')
save_data('Date', '굿')

print(read_data('Doave'))
print(read_data('Ddae'))
print(read_data('Date'))

해시테이블
채이닝 기법
굿