[자료구조] Hash Table

1. 해쉬 구조

• key에 value를 저장하는 데이터 구조.
• 파이썬의 딕셔너리가 해쉬 테이블의 예이다.
• 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용
• 파이썬에서는 해쉬를 별도 구현 할 필요가 없음.

2. 용어

• 해쉬 : 임의 값을 고정 길이로 변환
• 해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해싱 함수: key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수.
• 해쉬 값: key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 key에 대한 데이터 위치를 일관성 있게 찾을 수 있음
• 슬롯: 한 개의 데이터를 저장 할 수 있는 공간.

# 예제

# 8개의 hashTable을 생성했다
hash_table = list([0 for i in range(8)])

# key를 만드는 함수인데 hash라는 함수를 써서 구함
def get_key(data):
    return hash(data)

# key를 받아서 8로 나눈 나머지 값을 return 
def hash_fucntion(key):
    return key % 8

# data의 value를 저장하는 함수
def save_data(data,value):
    hash_address = hash_fucntion(get_key(data)) # hash를 위에 만든 함수들을 거쳐 hash_address 에 넣는다
    hash_table[hash_address] = value # value를 지정함

# value를 읽는 함수
def read_data(data):
    hash_address = hash_fucntion(get_key(data))
    return hash_table[hash_address]

save_data('Dave','01021283829')
save_data('kkkk','01031243567')
print(read_data('Dave'))

01021283829

3. 자료구조 해쉬 테이블의 장/ 단점

장점

• 데이터 저장/ 읽기 속도가 빠르다
• 중복 처리 / 확인이 쉽다.

단점

• 여러 키에 해당하는 주소가 동일할 경우 충돌! 해결하기 위해서 별도의 자료구조가 필요합니다.

용도

• 검색이 많이 필요한 경우
• 저장, 삭제, 읽기가 빈번한 경우
• 캐쉬 구현시 (중복 확인이 쉽기 때문)

4. 충돌을 해결하는 알고리즘

해쉬테이블의 단점을 고안하는 방법

• open hashing: 해쉬 테이블 저장공간 외의 공간을 활용하는 기법 (Channing 기법) / 중복되는 data들을 linked_list 자료구조로 저장 한다.
• close hashing: hashTable 안에 있는 공간을 이용해서 해결하는 방범

빈번한 충돌을 개선하는 방법

• 해쉬 함수를 재정의 및 해쉬 테이블 저장공간을 확대 / 만약에 8 개 저장하려면 16개 이상으로 만든다.

• 유명한 해쉬 함수들이 있음: SHA , SHA-256

import hashlib

data = 'test'.encode()
hash_object = hashlib.sha1()
hash_object.update(data)
hex_dig = hash_object.hexdigest()
print(hex_dig)