[자료구조] #6_1 해시 테이블

** 해시 테이블(Hash Table) 구조

- 키(Key)에 데이터(Value)를 저장하는 데이터 구조

- 장점: 키를 통해 바로 데이터에 접근할 수 있음

- 보통 배열로 미리 해쉬 테이블 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법)

- 파이썬의 딕셔너리(Dictionary) 타입

 

 

 

** 관련 용어

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

 

 

해시 테이블 접근 과정

 

 

 

** 간단한 해시 구현

1) 해시 테이블 생성

---

hash_table = list([i for i in range(10)])
hash_table # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

---

2) 해시 함수 정의

- 다양한 해시 함수 고안 기법이 있으며, 가장 간단한 방식이 Division 법 (나누기를 통한 나머지 값을 사용)

---

def hash_func(key):
    return key % 5

---

3) 해시 테이블에 값 저장

- 데이터에 따라 필요시 키 생성 방법 정의가 필요함

---

data1 = 'Andy'
data2 = 'Dave'
data3 = 'Trump'
data4 = 'Anthor'

# ord(): 문자의 ASCII(아스키)코드 리턴
print (ord(data1[0]), ord(data2[0]), ord(data3[0])) # 65 68 84
print (ord(data1[0]), hash_func(ord(data1[0]))) # 65 0
print (ord(data1[0]), ord(data4[0])) # 65 65 (충돌)

 

def storage_data(data, value):
    key = ord(data[0]) # 해당 데이터에 대한 키를 찾음
    hash_address = hash_func(key) # 키에 대응하는 해시주소
    hash_table[hash_address] = value # 값 저장

 

storage_data('Andy', '01055553333')
storage_data('Dave', '01044443333')
storage_data('Trump', '01022223333')

---

4) 해시 테이블 데이터 접근

---

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

 

get_data('Andy') # '01055553333'

---

 

 

** 해시 테이블 장단점

• 장점

  1) 데이터 저장/읽기(검색) 속도가 빠름

  2) 데이터의 중복 확인이 쉬움

 

• 단점

  1) 일반적으로 저장공간이 더 많이 필요함

  2) 여러 키가 같은 주소를 가리킬 경우, 충돌을 해결하기 위한 별도의 자료구조가 필요함

 

• 주요 용도

  1) 검색이 많이 필요한 경우

  2) 저장, 삭제, 읽기가 빈번한 경우

  3) 캐쉬 구현시 (중복 확인이 쉽기 때문)

 

 

 

** 해시 테이블 구현

---

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]

 

---

 

# 테스트

save_data('Dave', '0102030200')
save_data('Andy', '01033232200')
read_data('Dave') # '0102030200'

 

hash_table # ['0102030200', 0, 0, 0, 0, 0, 0, '01033232200']

---