Hash Table(해쉬 테이블)

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

Hash Table의 특징

• 키(Key)를 통해 바로 데이터(value)를 받아올 수 있으므로, 속도가 획기적으로 빠름
• Python의 딕셔너리(Dictonary)타입이 해쉬 테이블
• 보통 배열로 미리 Hash Table 사이즈 만큼 생성 후에 사용

Hash Table의 기능

• Hashing Function(해쉬 함수): 키(Key)에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• Hash Value(해쉬 값) 또는 Hash address(해쉬 주소): Key를 해싱 함수로 연산해서, 해쉬 값(또는 해쉬 주소)을 알아내고, 이를 기반으로 해당 Key에 대한 데이터(value)를 찾음
  즉, 데이터(value)가 저장된 메모리 주소
• Slot(슬롯): 한 개의 데이터를 저장할 수 있는 공간
• 저장할 데이터에 대해 Key를 추출할 수 있는 별도 함소도 존재함
  

Chaining 기법

• hash table이 데이터를 저장 시, 충돌(collision) 해결하기 위한 기법
• 개방 해슁(Open Hashing)기법 중 하나
• hash table 저장공간 이외의 공간을 활용하는 기법
• 충돌이 일어나면, 링크드 리스트라는 자료 구조를 이용하여, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법

Linear Probing 기법

• 패쇄 해슁(Close Hashing)기법 중 하나
• hash table 저장공간 안에서 충돌 문제를 해결하는 기법
• 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈 공간에 데이터를 저장하는 기법
• 저장공간 활용도를 높이기 위한 기법

Hash Table의 장점

• 데이터 저장/읽기 속도가 빠르다
  (검색 속도가 빠르다)
• 해쉬는 키에 대한 데이터가 있는지(중복여부) 확인이 쉽다

Hash Table의 단점

• 일반적으로 저장공간이 좀 더 많이 필요
• 여러 키에 해당하는 주소가 동일할 경우 출동을 해결하기 위한 별도 자료구조가 필요함

Hash Table 시간 복잡도

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

When To Use Hash Table

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

---

Hash Table의 구현 with Python

Division(나누기)를 이용한 Hash Table 예제

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

# hash function
def hash_func(key):
	return key % 5

# 키(key) 저장
data1 = 'Andy'
data2 = 'Dave'
data3 = 'Trump'
data4 = 'Anthor'

# 해쉬 ord()
print (ord(data1[0]), ord(data2[0]), ord(data3[0]))
print (ord(data1[0]), hash_func(ord(data1[0])))
print (ord(data1[0]), ord(data4[0]))
65 68 84
65 0
65 65

• ord(): 문자의 ASCII(아스키)코드 리턴

# 데이터 저장 function
def storage_data(data, value):
    key = ord(data[0])
    hash_address = hash_func(key)
    hash_table[hash_address] = value
    
# 키(key)에 해당하는 데이터(value) 저장
storage_data('Andy', '01055553333')
storage_data('Dave', '01044443333')
storage_data('Trump', '01022223333')

# 데이터 확인 function
def get_data(data):
	key = ord(data[0])
    hash_address = hash_func(key)
    return hash_table[hash_address]

# get data: 'Andy'
get_data('Andy')
'01055553333'

hash()를 이용한 hash table 예제

# hash table list 생성
hash_table = list([i for i in range(8)])

# hash()를 이용한 key 생성 function
def get_key(data):
	return hash(data)

# hash function
def hash_function(key):
	return key % 8

# 데이터 저장 function
def save_data(data, value):
	hash_address = hash_function(get_key(data))
    hash_table[hash_address] = value

# 데이터 확인 function
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'

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

Chaining 기법을 이용한 hash table 예제

• 해쉬 함수 : key % 8
• 해쉬키 생성 : hash(data)

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):
    index_key = get_key(data)
    hash_address = hash_function(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_function(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

# 만약 key가 같다면...
print (hash('Dave') % 8)
print (hash('Dd') % 8)
print (hash('Data') % 8)
2
2
2

# 데이터 저장
save_data('Dd', '1201023010')
save_data('Data', '3301023010')

# 데이터 확인
read_data('Dd')
'1201023010'

# print hash_table
hash_table
[0,
 0,
 [[-1173540137483533318, '1201023010'], [7235455213596750242, '3301023010']],
 0,
 0,
 0,
 0,
 0]

Linear Probing 기법을 이용한 hash table 예제

• 해쉬 함수 : key % 8
• 해쉬키 생성 : hash(data)

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):
    index_key = get_key(data)
    hash_address = hash_function(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_function(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

# key 확인
print (hash('dk') % 8)
print (hash('da') % 8)
print (hash('dc') % 8)
1
0
1

# 데이터 저장
save_data('dk', '01200123123')
save_data('da', '3333333333')

# 데이터 확인
read_data('da')
'3333333333'

# print hash_table
hash_table
[[-3728427293267935576, '3333333333'],
 [-851086707681499591, '01200123123'],
 0,
 0,
 0,
 0,
 0,
 0]

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

• 해쉬 함수를 재정의 및 해쉬 테이블 저장공간을 확대
• e.g.

hash_table = list([None for i in range(16)])

def hash_function(key):
    return key % 16

sha-1

import hashlib

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

print (hex_dig)
a94a8fe5ccb19ba61c4c0873d391e987982fbbd3

sha-256

import hashlib

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

print (hex_dig)
9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08

sha-256과 Chaining 기법을 이용한 hash table 예제

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_function(key):
    return key % 8

def save_data(data, value):
    index_key = get_key(data)
    hash_address = hash_function(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_function(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

# 해쉬 키 확인
print (get_key('db') % 8)
print (get_key('da') % 8)
print (get_key('dh') % 8)
1
2
2

# 데이터 저장
save_data('da', '01200123123')
save_data('dh', '3333333333')

# 데이터 확인
read_data('dh')
'3333333333'

# print hash_table
hash_table
[0,
 0,
 [77049896039817716104633086125973601665927154587286664305423403838091909979274,
  '01200123123'],
 [25902807790238191969936164090115518991880572428612380032453909518048593055890,
  '3333333333'],
 0,
 0,
 0,
 0]