5. 파이썬의 해시 테이블

#1. 해시 테이블(Hash Table)
* 키(key)에 데이터(value)를 저장하는 데이터 구조
* 파이썬에서는 해시를 별도 구현할 필요가 없음
* 파이썬 딕셔너리(Dictionary) 타입이 해시 테이블의 예
* key를 통해 데이터를 바로 찾을 수 있으므로 검색 속도가 빨라짐
* 보통 배열로 미리 hash table 사이즈 만큼 생성 후에 사용


#2. 알아둘 용어
* 해시(Hash): 임의 값을 고정 길이로 변환하는 것
* 해시 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
* 해시 함수(Hashing Function): key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
* 해시 값(Hash Value) 또는 해시 주소(Hash Address): key를 해싱 함수로 연산해서 해시 값을 알아내고 이를 기반으로 해시 테이블에 해당 key에 대한 데이터 위치를 일관성 있게 찾을 수 있음
* 슬롯(Slot): 한 개의 데이터를 저장할 수 있는 공간


#3. 간단한 해시 테이블 만들기
hash_table = list([i for i in range(10)])
print(hash_table)

-->
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]


1)
#3-3. 해시 테이블에 저장하기

data1 = 'apple'
data2 = 'banana'
data3 = 'orange'
data4 = 'melon'

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

-->
97
98
111
109

print(hash_func(ord(data1[0])))
-->
2

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

storage_data('apple', '김사과')
storage_data('banana', '반하나')
storage_data('orange', '오렌지')

hash_table
-->
[0, '오렌지', '김사과', '반하나', 4, 5, 6, 7, 8, 9]

 

# 문제
키를 전달받아 저장된 값을 읽어오는 함수를 작성해보자

```
def get_data(key):
    pass
```

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

-->

print(get_data('banana'))
print(get_data('orange'))

-->
반하나
오렌지

 

# **4. 해시 테이블의 장단점**
* 장점
    * 검색 속도가 빠름
    * 해시는 키에 대한 데이터가 있는지 확인이 쉬움(중복)
* 단점
    * 일반적으로 저장공간이 많이 필요함
    * 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도의 자료구조가 필요함

 

 

#5. 충돌 해결 알고리즘
#5-1. 선형 탐색 기법(Linear Probling)
* 해시 충돌이 발생했을 경우, 충돌이 발생한 자리에 데이터를 저장하지 못하므로 바로 옆의 빈 자리를 찾는 방법

* 배열에서 빈 자리를 선형적으로 탐색하면서 데이터를 삽입

* 방법
    * 데이터를 해시 함수로 인덱스를 계산하여 삽입
    * 만약 해당 자리에 이미 다른 데이터가 있다면, 그 다음(혹은 몇 번째 이후) 자리를 이동하면서 빈 자리를 찾음
    * 빈 자리를 찾으면 그 자리에 데이터를 저장

* 장단점
    * 장점
         * 구현이 간단함
        * 메모리 공간을 효율적으로 사용함

    * 단점
        * 클러스터링 현상이 발생할 수 있음
        * 충돌이 계속 발생하면 해시 테이블의 특정 영역에 데이터가 몰리면서 탐색 속도가 느려질 수 있음

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

-->
[0, 0, 0, 0, 0, 0, 0, 0]


# hash
# 객체의 고유한 해시 값을 정수로 반환하는 함수
# 동일한 객체는 동일한 해시 값을 가짐
def get_key(key):
    print(hash(key))
    return hash(key)

def hash_function(key):
    return key % 8

def save_data(key, value):
    hash_address = hash_function(get_key(key))
    hash_table[hash_address] = value


save_data('melon', '이메론')
-5367591237972981187

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

def get_key(key):
    return hash(key)

def hash_function(key):
    return key % 8

def save_data(key, value):
    index_key = get_key(key)
    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(key):
    index_key = get_key(key)
    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

save_data('apple', '김사과')
save_data('melon', '이메론')
save_data('banana', '반하나')

print(hash('apple') % 8)
print(hash('avocado') % 8)
print(hash('cherry') % 8)
print(hash('orange') % 8)
print(hash('melon') % 8)
hash_table

-->
[0,
 0,
 0,
 [2162330361090163163, '김사과'],
 [763027516017398140, '반하나'],
 [-5367591237972981187, '이메론'],
 0,
 0]
 
 
save_data('orange', '오렌지')
hash_table

-->
[0,
 0,
 0,
 [2162330361090163163, '김사과'],
 [763027516017398140, '반하나'],
 [-5367591237972981187, '이메론'],
 [-2731970246574427341, '오렌지'],
 0]
 
 
read_data('orange')
오렌지

 

# 5-2. 체이닝 기법(Chaining)
* 해시 충돌이 발생했을 경우, 배열의 각 인덱스에서 데이터를 단순히 저장하는 대신, 연결 리스트나 다른 데이터 구조를 사용해 여러 개의 데이터를 저장하는 방법
* 방법
    * 데이터를 해시 함수로 인덱스를 계산하여 삽입
    * 만약 해당 자리에 이미 다른 데이터가 있다면, 그 자리에 새로운 데이터를 추가하는 대신, 해당 자리를 하나의 '체인(주로 연결 리스트)'으로 만들어서 여러 데이터를 이어 붙임
* 장단점
    * 장점
        * 충돌이 발생해도 테이블에 데이터를 추가하는 데 문제가 없음
        * 클러스터링 문제가 없음
        * 해시 테이블의 크기가 꽉 차더라도 리스트 확장으로 데이터를 계속 추가할 수 있음
    * 단점
        * 메모리 사용이 비효율적일 수 있음
        * 연결 리스트를 유지하기 위한 추가 메모리가 필요함
        * 최악의 경우 모든 데이터가 하나의 연결 리스트에 몰리면 탐색 시간이 매우 느려질 수 있음

 

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

def get_key(key):
    return hash(key)

def hash_function(key):
    return key % 8

def save_data(key, value):
    index_key = get_key(key)
    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(key):
    index_key = get_key(key)
    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]
    else:
        return None
 
save_data('apple', '김사과')
save_data('melon', '이메론')
save_data('banana', '반하나')
 
hash_table

-->

[0,
 0,
 0,
 [[2162330361090163163, '김사과']],
 [[763027516017398140, '반하나']],
 [[-5367591237972981187, '이메론']],
 0,
 0]
 
 
print(hash('apple') % 8)
print(hash('avocado') % 8)
print(hash('cherry') % 8)
print(hash('orange') % 8)
print(hash('melon') % 8)
-->
3
1
6
3
5

save_data('orange', '오렌지')
hash_table
-->
[0,
 0,
 0,
 [[2162330361090163163, '김사과'], [-2731970246574427341, '오렌지']],
 [[763027516017398140, '반하나']],
 [[-5367591237972981187, '이메론']],
 0,
 0]

 

# 6. 해시 함수와 키 생성 함수
* hash 함수는 실행할 때마다 값이 달라질 수 있음
* SHA(Secure Hash Algorithm, 안전한 해시 알고리즘)와 같은 유명한 해시 알고리즘이 있음
* 어떤 데이터도 유일한 고정된 크기의 고정값을 반환해주므로 해시 함수로 유용하게 활용 가능


### 6-2. SHA-256
* SHA 알고리즘의 한 종류로 256비트로 구성되어 64자리 문자열을 반환
* SHA-2 계열 중 하나이며 블록체인에서 가장 많이 채택하여 사용

 

import hashlib
import sys

data = 'test'.encode()
print(data)
hash_object = hashlib.sha256()
print(hash_object)
hash_object.update(data)
hex_dig = hash_object.hexdigest() # 16진수로 고정된 해시값
print(hex_dig)
print(int(hex_dig, 16)) # 10진수로 고정된 해시값
-->
b'test'
<sha256 _hashlib.HASH object @ 0x7bd2eb8067b0>
9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08
72155939486846849509759369733266486982821795810448245423168957390607644363272

 

### 문제2
체이닝 기법(Chaining) 적용한 해시 테이블 코드에 키 생성함수로 sha256 해시 알고리즘을 사용하여 변경해보자
1. 해시함수: key % 8
2. 총 8개의 슬롯
3. 해시키 생성: sha256

import hashlib

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

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

def hash_function(key):
    return key % 8

def save_data(key, value):
    index_key = get_key(key)
    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(key):
    index_key = get_key(key)
    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]
    else:
        return None
        
save_data('apple', '김사과')
save_data('melon', '이메론')
save_data('banana', '반하나')
hash_table
-->

[0,
 0,
 0,
 [[26452929773915387181124022930352263286101059613432915788569047929437325971227,
   '김사과']],
 0,
 0,
 [[81677505976092492256788526045794788656350341275302681754807117191827310239310,
   '반하나']],
 [[75635856040252375081268883667212387409410230564410600651936135151777611054631,
   '이메론']]]
  
  
print(get_key('apple') % 8)
print(get_key('banana') % 8)
print(get_key('avocado') % 8)
print(get_key('cherry') % 8)
print(get_key('orange') % 8)
print(get_key('melon') % 8)
-->
3
6
0
6
4
7


save_data('cherry', '채리')
hash_table
-->
[0,
 0,
 0,
 [[26452929773915387181124022930352263286101059613432915788569047929437325971227,
   '김사과']],
 0,
 0,
 [[81677505976092492256788526045794788656350341275302681754807117191827310239310,
   '반하나'],
  [20663375971449343567437890939728808532354865817022289781333181590448322644526,
   '채리']],
 [[75635856040252375081268883667212387409410230564410600651936135151777611054631,
   '이메론']]]