[자료구조] 해쉬 테이블 with python

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 안에 있는 공간을 이용해서 해결하는 방범

open hashing 기법

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

def get_key(data):
    return hash(data)

def hash_fucntion(key):
    return key % 8

def save_data(data,value):
    index_key = get_key(data)
    hash_address = hash_fucntion(index_key)
    if hash_table[hash_address] != 0:
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                hash_table[hash_address][index][1] = value
                return
        hash_table[hash_address].append([index_key, value])
    else:
        hash_table[hash_address] = [[index_key, value]]

def read_data(data):
    index_key = get_key(data)
    hash_address = hash_fucntion(index_key)
    if hash_table[hash_address] != 0:
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                return hash_table[hash_address][index][1]
        return None

save_data('Dd','01021283829')
save_data('David','01031243567')
print(hash_table)
print(read_data('Dd'))

Linear Probing 기법

• 저장공간의 활용도를 높힐 수 있다.

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

def get_key(data):
    return hash(data)

def hash_fucntion(key):
    return key % 8

def save_data(data,value):
    index_key = get_key(data)
    hash_address = hash_fucntion(index_key)
    if hash_table[hash_address] != 0:
        for index in range(hash_address, len(hash_table)):
            if hash_table[index] == 0:
                hash_table[index] = [index, value]
            elif hash_table[index][0] == index_key:
                hash_table[index][1] = value
                return
    else:
        hash_table[hash_address] = [index, value]

def read_data(data):
    index_key = get_key(data)
    hash_address = hash_fucntion(index_key)
    if hash_table[hash_address] != 0:
        for index in range(hash_address, len(hash_table)):
            if hash_table[index] == 0:
                return None
            elif hash_table[index][0] == index_key
                return hash_table[index][1]
    else:
        return None

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

• 해쉬 함수를 재정의 및 해쉬 테이블 저장공간을 확대 / 만약에 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)