[자료구조] 해쉬 테이블(Hash table) (Python)

1. 기본구조와 용어

 

• 해쉬 테이블(Hash Table): Key에 Value를 저장하는 데이터 구조

## 탐색을 할 때 키값을 통해 바로 데이터를 찾을 수 있으므로 탐색 속도가 빠름

## 키값 입력 -> 해싱 함수 연산을 통해 해시 주소를 알아냄 -> 해시 주소를 통해 저장되어 있는 주소를 찾아냄

## Python에서는 Dictionary 타입을 사용하면 된다!

---

• 해쉬(Hash): 임의 값을 고정 길이로 변환
• 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해쉬 값(Hash Value) or 해쉬 주소(Hash Address): Key값을 통해 알아낼 수 있는 찾으려는 데이터가 있는 주소
• 해싱 함수(Hashing Function): Key에 대해 산술연산을 하여 데이터 위치를 찾을 수 있는 함수
• 슬롯(slot): 한 개의 데이터를 저장할 수 있는 공간

2. 장점

• 데이터 저장/읽기 속도가 빠름(Key값으로 찾기 때문)
• 중복 확인이 쉬움

3. 단점

• 일반적으로 저장공간이 많이 필요(테이블을 크게 잡으면 잡을수록 중복의 가능성이 줄어듬)
• 여러 키에 해당하는 주소가 동일할 때 -> 충돌 발생(충돌 방지를 위한 별도의 자료구조가 필요)
• {테이블의 크기 & 탐색 시간}은 trade-off 관계

4. Python list로 간단한 Hash table 구현

#Python에서는 그냥 Dictionary자료형을 사용하는게 편하지만 원리 이해를 위해 코드를 짜 봤습니다.

#hash() 내장함수 활용
hash_table = list([0 for _ in range(10)]) #list comprehension

def get_key(data): #string으로 들어온 key값을 hash값으로
    return hash(data)

def hash_function(key): #key값을 0~7로(hash_table의 인덱스가 0~9임으로)
    return key % 8

def save_data(data, value): #key값을 받으면 0~7의 인덱스값으로 변환해줌, 그 인덱스에 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]

 

save_data('jisu', '01033335555')

이렇게 데이터를 넣어주려고 할 때 작동 순서

1. 'jisu'가 hash() 내장 함수를 통해 해시값을 구한다. ex) -7403018940966764746
2. 해시값을 8로 나눈 나머지 값을 구한다 ex) 6
3. hash_table의 6번째 index에 '01033335555'가 저장된다.