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

1. 해쉬 구조

• Hash Table: 키(key)에 데이터를(value)를 저장하는 데이터 구조
  • key를 통해 데이터를 받아와 속도가 굉장히 빨라진다.
  • 파이썬 딕셔너리가 hash table에 해당된다.

2. 용어

• 해쉬(hash) : 임의 값을 고정 길이로 변환
• 해쉬 테이블(hash table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해싱 함수(hashing function): key에 대해 데이터 위치를 찾을 수 있는 함수
• 해쉬 값(hash value) 또는 해쉬 주소(hash address): key를 해싱 함수로 연산해, 해쉬 테이블에서 key에 대한 위치를 찾을 수 있음.
• 슬롯(slot): 한 개의 데이터를 저장할 수 있는 공간
• 저장할 데이터에 대해 key를 추출할 수 있는 별도 함수 존재할 수 있음.
•  

hash table 만들기

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

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

해쉬 함수

• 해쉬 함수는 다양한 방식으로 만들 수 있으며, 가장 간단한 방식은 Division 법이다.

def hash_func(key):
    return key % 5 # 고정된 길이로 나옴

데이터 저장

data1 = 'Estus Flask'
data2 = 'Ashen Estus Flask'
data3 = 'Homeward Bone'

# ord(): 문자의 ASCII코드 리턴, 이것을 key로 이용하기 위함.
print(ord(data1[0]), ord(data2[0]), ord(data3[0]))
print(ord(data1[0]), hash_func(ord(data1[0])))

69 65 72
69 4

데이터 저장

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

storage_data('Estus Flask', '5')
storage_data('Ashen Estus Flask', '3')
storage_data('Undead Bone Shard', '4')

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

get_data('Estus Flask')

'5'

장단점과 주요 용도

• 장점
  • 데이터 저장/읽기 속도 빠르다.
  • 키에 대한 데이터가 있는지 (중복) 확인이 쉽다.
• 단점
  • 저장공간이 많이 필요하다.
  • 주소가 동일할 경우 충돌을 피하기 위한 별도의 자료 구조가 필요하다.
• 주요 용도
  • 검색이 많이 필요할 때
  • 저장, 삭제, 읽기를 자주 해야 할 때
  • 캐시를 구현할 때

# hash(data) 잘 쓰지는 않음.
hash_table = list([0 for i in range(8)])

def get_key(data):
    return hash(data)

def hash_func(key):
    return key % 8

def storage_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]

storage_data('Ashen Estus Flask', '7')
storage_data('Braille Divine Tome of Carim', '1')
read_data('Ashen Estus Flask')

'7'

read_data('Braille Divine Tome of Carim')

'1'

hash_table

[0, 0, '1', '7', 0, 0, 0, 0]

충돌(Collision) 해결 알고리즘

해쉬 테이블의 가장 큰 문제는 충돌이다.

Chaining 기법

• 개방 해슁 또는 Open Hashing 기법 중 하나 : 충돌하는 데이터에 대해서 추가적인 데이터 공간 (링크드 리스트)에 저장하는 것.

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

def get_key(data):
    return hash(data)

def hash_func(key):
    return key % 8

def storage_data(data, value):
    index_key = get_key(data) # key값과 데이터를 함께 저장하기 위함.
    hash_address = hash_func(index_key)
    if hash_table[hash_address] != 0:
        for index in range(len(hash_table[hash_address])): # 리스트에 append 하기 위해서, 데이터가 몇개 들어가 있는지 확인
            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_func(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
    else:
        return None

print(hash_func(hash('Db')))
print(hash_func(hash('D')))

5
5

storage_data('Db', '1234')
storage_data('D', '4321')
read_data('Db')

'1234'

read_data('D')

'4321'

hash_table

[0,
 0,
 0,
 0,
 0,
 [[1153917651641321117, '1234'], [-8357136605090786331, '4321']],
 0,
 0]

 

linear probing 기법

• 폐쇄 해슁 또는 Close Hashing 기법 중 하나 : 해쉬 테이블 안에 비어있는 공간에 저장
  • 저장 공간의 활용도를 높일 수 있는 장점이 있다.

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

def get_key(data):
    return hash(data)

def hash_func(key):
    return key % 8

def storage_data(data, value):
    index_key = get_key(data)
    hash_address = hash_func(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_key, value]
                return
            elif hash_table[index][0] == index_key: # 똑같은 키를 가졌을 때 데이터 업데이트
                hash_table[index][1] = value
                return
    else:
        hash_table[hash_address] = [index_key, value]

def read_data(data):
    index_key = get_key(data)
    hash_address = hash_func(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

빈번한 충돌을 피하는 법

• 해쉬 테이블의 저장공간을 2배로 늘려서 저장한다.
• hash_function도 저장 공간에 따라서 수정한다.

참고: 해쉬 함수와 키 생성 함수

• hash() 함수는 실행할 때마다 값이 달라질 수 있다.
• SHA(Secure Hash Algorithm) : 유일한 고정된 크기의 값을 리턴해주어 해쉬 함수로 유용하게 쓸 수 있다.

SHA-1

import hashlib

data = 'Estus Flask'.encode() # 바이트로 바꿔준다.
hash_object = hashlib.sha1()
hash_object.update(data) # or hash_object.update(b'test')
hex_dig = hash_object.hexdigest() #보통 16진수로 추출함
print(hex_dig)

9aa790a4258fe70a4f238d5d8cd829a8433dafd8

SHA-256

import hashlib

data = 'Estus Flask'.encode() # 바이트로 바꿔준다.
hash_object = hashlib.sha256()
hash_object.update(data) # or hash_object.update(b'test')
hex_dig = hash_object.hexdigest() #보통 16진수로 추출함
print(hex_dig)

fb90c3b4c383052303ae2af73cbac65b1446fdfd3c3ee570560be63c95f4ef3b

결과를 가지고 원래 값을 찾을 수 없다. SHA-256은 비트코인에서도 사용된다.

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

def get_key(data):
    hash_object = hashlib.sha256()
    hash_object.update(data.encode())
    hex_dig = hash_object.hexdigest()
    return int(hex_dig, 16)

def hash_func(key):
    return key % 8

def storage_data(data, value):
    index_key = get_key(data)
    hash_address = hash_func(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_key, value]
                return
            elif hash_table[index][0] == index_key: # 똑같은 키를 가졌을 때 데이터 업데이트
                hash_table[index][1] = value
                return
    else:
        hash_table[hash_address] = [index_key, value]

def read_data(data):
    index_key = get_key(data)
    hash_address = hash_func(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

시간 복잡도

• 일반적인 경우 (충돌이 없는 경우): O(1)
• 최악의 경우(충돌이 모두 발생하는 경우): O(n)