[자료구조] 해시 테이블(Hash Table)(w/파이썬)

---

키를 해시함수에 넣으면 데이터가 저장되어 있는 위치를 알 수 있다. 

파이썬의 딕셔너리, 고언어의 맵, 자바스크립트의 오브젝트가 해시함수다!

 

해시 테이블 안에 데이터들이 들어가 있다.

각각의 데이터들은 키로 연결 돼 있는데 키를 해시함수에 넣으면 주소를 반환해준다.

이 주소를 해쉬 값 이라고 한다.

 

---

용어 정리

해시: 임의 값을 고정 길이로 변환하는 것

해시 테이블: 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조

해싱 함수: 키에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수

해시 값, 해시 주소: 키를 해싱 함수로 연산해서 해쉬 값을 알아내고 이를 기반으로 해쉬 테이블에서 해당 키에 대한 데이터 위치를 일관성 있게 찾을 수 있음

슬롯: 한 개의 데이터를 저장할 수 있는 공간

저장할 데이터에 대해 키를 추출할 수 있는 별도 함수도 존재할 수 있음

 

위키피디아

---

hash table 만들기

 

슬롯이 있어야 하고 슬롯을 지칭할 수 있는 해쉬 주소가 있어야 함

아래의 것은 인덱스를 각각 가지고 있기 때문에 해쉬 테이블이 맞다.

hash_table = list([i for i in range(10)])
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

division법을 이용한 해쉬 함수(나누기를 통한 나머지 값을 사용하는 기법)

def hash_func(key):
	return key % 5

 

해쉬 테이블에 저장하기

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

data1 = 'andy'
data2 = 'dave'
data3 = 'trump'

# ord(): 문자의 아스키 코드 리턴
print(ord(data1[0]), ord(data2[0]), ord(data3[0]))

 

해쉬 테이블에 값 저장 예

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

 

data와 data에 해당하는 값을 넣음.

data를 key로 만들고 key로 hash func를 통해 hash address를 만들고 address로 슬롯에 가서 value를 넣는다.

storage_data('Andy', '12')
storage_data('Dave', '2')
storage_data('Jason', '52')

 

값 읽기 예

def get_data(data):	# 위 데이터 기준 Andy를 넣으면 된다.
    key = ord(data[0])
    hash_address = hash_func(key)
    return hash_table[hash_address]

 

---

배열과 비교해보는 왜 해쉬함수가 더 빠른 서치를 하는가

 

배열로 Andy의 나이를 찾는 방법:

인덱스 처음부터 Andy를(일일이) 찾는다.

그리고 Andy의 나이를 추출한다

 

해쉬함수로 Andy의 나이를 찾는 방법:

Andy의 A로 키를 만들었었기 때문에 키를 만든다.

키를 해쉬함수에 넣고 주소를 얻는다.

주소로 바로 Andy의 나이를 추출한다

 

검색을 하나 데이터를 저장하나 해시가 아주 빠르다. 

 

샘플

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

def get_key(data):
    return hash(data)	# hash는 내장함수임

def hash_func(data):
    return data % 8

def save_data(data, value):
    hash_address = hash_func(get_key(data))
    hash_table[hash_address] = value

def read_data(data):
    hash_address = hash_func(get_key(data))
    return hash_table[hash_address]

---

출처:

패스트 캠퍼스 알고리즘 자료구조 강의