[자료구조/Data Structure] 파이썬으로 해시 테이블(Hash Table) 자료구조 알아보기

해시 테이블이란?

• Key, Value 형태로 데이터를 저장하는 자료구조
• 파이썬 딕셔너리 타입이 해시 테이블의 예
• 보통 배열로 Hash Table 사이즈 만큼 생성 후에 사용한다.

 

용어들

• 해시(Hash) : 임의의 값을 고정된 길이로 변환하는 것
• 해시 테이블(Hash Table) : 키 값의 연산에 의해 직접적으로 접근이 가능한 자료구조
• 해싱 함수(Hashing Function) : 키에 대해 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해시 값(Hash Value) 또는 해시 주소(Hash Address) : 키를 해싱 함수로 연산해서, 해시 값을 알아내고, 이를 기반으로 해시 테이블에서 해당 키에 대한 위치를 일관성 있게 찾을 수 있다.
• 슬롯(Slot) : 한 개의 데이터를 저장할 수 있는 공간

 

 

해시 테이블의 장단점

• 장점
  • 데이터 저장 및 읽기 속도가 빠르다.
  • 키에 대한 중복이 있는지 확인하기 쉽다.
• 단점
  • 일반적으로 다른 자료구조보다 저장공간이 더 필요하다.
  • 여러 키에 해당하는 주소가 동일한 경우 충돌(Collision)이 발생하고, 이를 해결하기 위한 별도 자료구조 또는 함수가 필요하다.

 

해시 테이블의 주용도

• 검색이 많이 필요할 경우
• 저장, 삭제, 읽기가 빈번하게 일어나는 경우
• 캐시를 구현할 경우 (중복 확인이 쉽기 때문에)

 

충돌을 해결하는 알고리즘

 

1. Chaining 방법

• 해시 테이블 저장공간 이외의 공간을 활용하는 방법
• 충돌이 일어나면 연결 리스트 자료구조를 통해 데이터를 추가로 뒤에 연결시켜서 저장하는 방법

2. Linear Probing 기법

• 해시 테이블 저장공간 안에서 충돌을 해결하는 방법
• 충돌이 일어나면 해당 해시 주소의 다음 주소부터 맨 처음 나오는 주소에 데이터를 저장하는 방법 
  

  

 

파이썬으로 간단히 구현한 해시 테이블

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


def change_to_hash(key):
    return hash(key)


def hash_function(key):
    return key % 8


def save_data(key, value):
    hash_address = hash_function(change_to_hash(key))
    hash_table[hash_address] = value


def read_data(key):
    hash_address = hash_function(change_to_hash(key))
    return hash_table[hash_address]


save_data("dave", 2123132)
save_data("hong", 112312)
print(read_data("hong"))


# 결과
# >>> 112312

매우 간단하게 구현한 해시 테이블이다.

우선 삽입 흐름은 key, value를 입력 받으면 key를 파이썬 내장 함수인 hash()를 통해 hash 값을 받고 

또 그 값을 hash_function()(여기서는 간단히 key % 8을 했다)을 통해 hash_address를 만들어내고 해당 hash_address

를 index로 하여 value를 삽입한다.

 

데이터를 읽는 것은 간단하게 key를 입력 받으면 데이터 삽입 때와 마찬가지로 hash_address로 변환하고 해당 hash_address

로 hash_table에서 데이터를 읽는다.

 

참고

• https://www.fun-coding.org/Chapter09-hashtable.html