파이썬 자료구조 (5) 해시 테이블

1. 해시 테이블(Hash Table)

• 키(Key)에 데이터(Value)를 저장하는 자료구조
• 파이썬에서는 해시를 별도 구현할 필요 없음
• 보톨 배열로 미리 hash table 사이즈 만큼 생성 후 사용
• 예) 파이썬 딕셔너리(Dictionary)타입

 

2. 알아둘 용어

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

 

3. 간단한 해시 테이블 만들기

 

3-1. hash table 만들기

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

 

3-2. hash function 만들기

def hash_func(key):
    return key % 5

 

3-3. hash table에 저장하기

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

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

print(hash_func(ord(data1[0]))) # hash function을 이용해 97을 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('oreange', '오렌지')

hash_table

 

 

문제1

- 키를 전달받아 저장된 값을 읽어오는 함수 만들기

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('apple'))

 

 

4. 해시 테이블의 장단점

• 장점
  • Key를 통해 데이터를 바로 찾을 수 있어서 검색 속도가 빠름
  • Key에 대한 데이터가 있는지 확인이 쉬움 (중복 확인이 쉬움)
• 단점
  • 일반적으로 많은 저장 공간을 필요로 함
  • 중복 데이터로 인한 충돌 시 추가 저장공간이 필요함

 

5. 충돌 해결 알고리즘

 

5-1. 선형 탐색 기법(Linear Probling)

• 해시 충돌이 발생할 경우 충돌 발생 자리에 데이터를 저장할 수 없으므로 바로 옆의 빈 자리를 찾는 방법
• 배열에서 빈 자리를 선형적으로 탐색하며 데이터 삽입
• 장단점
  • 장점
    • 구현이 간단함
    • 메모리 공간을 효율적으로 사용 가능
  • 단점
    • 클러스터링 현상이 발생할 수 있음
    • 충돌이 계속 발생하면 해시 테이블의 특정 영역에 데이터가 몰리면서 탐색 속도가 느려짐
• 방법

• 해시 함수로 데이터의 인덱스를 계산하여 데이터 삽입
• 만약 해당 자리에 이미 데이터가 존재한다면 그 다음(혹은 몇 번째 이후까지) 자리를 이동하며 빈 자리 찾기
• 빈 자리 찾을 시 그 자리에 데이터 저장

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

# hash
# 객체의 고유한 해시 값을 정수로 반환하는 함수
# 동일한 객체는 동일한 해시 값을 가짐
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:                         # table에 데이터가 들어가 있는 상태
        for index in range(hash_address, len(hash_table)):    # 현재 hash_address 슬롯부터 hash_table 길이 만큼 반복하여 빈 자리 찾기
            if hash_table[index] == 0:                        # table에 데이터가 없는 슬롯을 찾으면
                hash_table[index] = [index_key, value]        # [index_key, value] 형태로 저장
                return
            elif hash_table[index][0] == index_key:           # 현재 hash_table의 key와 새로 넣는 key가 동일한 경우
                hash_table[index][1] = value                  # value 값을 새로 덮어쓰기 저장 (파이썬 딕셔너리와 유사)
                return
    else:                                                     # table에 데이터가 없는 상태
        hash_table[hash_address] = [index_key, value]         # [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

# 해시 주소가 같은 키가 있는지 확인
print(hash('apple') % 8)
print(hash('melon') % 8)
print(hash('banana') % 8)

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

hash_table

save_data('apple','사아과')   # '사과' value가 '사아과'로 덮어쓰여 저장
hash_table

 

5-2. 체이닝 기법(Chaining)

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

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]]   # 2차원으로 데이터 넣기

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

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

save_data('avocado','아보카')
hash_table

print(hash('apple') % 8) # 0
print(hash('melon') % 8)
print(hash('banana') % 8)
print(hash('avocado') % 8)
print(hash('cherry') % 8) # 0 '김사과'와 충돌
print(hash('orange') % 8)



# 충돌 데이터 없을 경우
save_data('apple','김사과')
save_data('melon','이메론')
save_data('banana','반하나')

hash_table

# 충돌 데이터 저장 시
save_data('cherry','채리')

hash_table		# [[5999061346037958920, '김사과'], [1564699209004044992, '채리']]

 

 

6. 해시 함수와 키 생성 함수

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

 

6-1. SHA-1

import hashlib
import sys

data = 'test'.encode()
print(data)

hash_object = hashlib.sha1()
print(hash_object)

hash_object.update(data)
hex_dig = hash_object.hexdigest()   # hexdigest(): 16진수로 고정된 해시값 반환
print(hex_dig)
print(int(hex_dig, 16))   # 10진수로 고정된 해시값

 

 

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()   # hexdigest(): 16진수로 고정된 해시값 반환
print(hex_dig)
print(int(hex_dig, 16))   # 10진수로 고정된 해시값

 

문제2

- 위에서 작성한 체이닝 기법(Chaining) 적용한 해시 테이블 코드에 키 생성 함수로 sha256 해시 알고리즘을 사용하여 변경하기

• 해시함수: Key % 8
• 총 8개의 슬롯
• 해시키 생성: sha256

def get_key(key):
    data = key.encode()
    hash_object = hashlib.sha256()
    hash_object.update(data)
    hex_dig = hash_object.hexdigest()
    return int(hex_dig, 16)   # key % 8 에서 십진수인 8로 나누기 위해 16진수를 10진수로 변환

 

 

문제2 전체 코드 및 테스트

import hashlib
import sys

def get_key(key):
    data = key.encode()
    hash_object = hashlib.sha256()
    hash_object.update(data)
    hex_dig = hash_object.hexdigest()
    return int(hex_dig, 16)   # key % 8 에서 십진수인 8로 나누기 위해 16진수를 10진수로 변환

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]]   # 2차원으로 데이터 넣기

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

 

 

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

# 충돌 데이터 없을 경우
save_data('apple','김사과')
save_data('melon','이메론')
save_data('banana','반하나')

hash_table

print(get_key('apple') % 8)
print(get_key('melon') % 8)
print(get_key('banana') % 8)    # 6
print(get_key('avocado') % 8)
print(get_key('cherry') % 8)    # 6 'banana'와 충돌
print(get_key('orange') % 8)

# 충돌 데이터 저장 시
save_data('cherry','채리')

hash_table		# [[8167750...10239310, '반하나'], [2066337...22644526, '채리']]