[Python] Hash Table의 충돌 개선을 위한 SHA-1, SHA-256

학습 내용

• Hash Table의 충돌을 개선하기 위한 공간 확대
• SHA-1, SHA-256 을 사용하여 충돌을 개선하기
• Hash 자료구조의 시간복잡도 계산해보기

📘 해쉬 테이블의 빈번한 충돌을 지우기 위한 방법

해쉬 테이블은 잘 활용하면 속도도 매우 빠르고, 효율적인 자료구조를 구축할 수 있습니다.
하지만 해쉬 테이블 내의 충돌에 대비하지 않으면 매우 비효율적으로 변할 수 있습니다.
충돌을 줄이기 위해서는 일반적으로 공간을 늘리는 방법과 안정적인 해쉬값을 생성하는 방법이 있습니다.

해쉬 함수 재정의 및 저장공간 확대

해쉬 테이블 내 충돌이 발생하는 이유는 구축방식에 따라 다르겠지만,
같은 주소값을 가지는 값들이 서로 충돌하여 발생하는 문제가 큽니다.
따라서 일반적으로는 해쉬 테이블의 공간을 충분히 확보하여 이 문제를 해결할 수 있습니다.

• 테이블 슬롯을 2배로 늘려주는 것이 일반적.

hash_table = list([None for i in range(16)]) # 8 -> 16

def hash_function(key):
    return key % 16 

SHA(Secure Hash Algorithm, 안전한 해쉬 알고리즘) 사용

Python 내의 hash() 함수는 실행시 마다 값이 달라집니다.
따라서 안정적인 고정값을 필요로 할 때는 불안정한 모습을 보이는 데요.
이를 개선하기 위해 SHA-1, SHA-256 라이브러리를 활용합니다.
(pip install hashlib)

SHA-1

import hashlib

data = 'test'.encode() # byte로 변환.
hash_object = hashlib.sha1()
hash_object.update(data) # unicode -> byte -> update
hex_dig = hash_object.hexdigest() # 16진수로 대부분 추출
print (hex_dig)
# a94a8fe5ccb19ba61c4c0873d391e987982fbbd3

SHA-256

• 블록체인에서 많이 사용하는 해쉬 함수

import hashlib

data = 'test'.encode()
hash_object = hashlib.sha256() # SHA-1 보다 개선된 모델
hash_object.update(data)
hex_dig = hash_object.hexdigest()
print (hex_dig)
# 9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08
# 원래 데이터 추론 불가능.

해쉬 함수에 적용해보기

import hashlib

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

# SHA-256 적용
def get_key(data):
        hash_object = hashlib.sha256()
        hash_object.update(data.encode())
        hex_dig = hash_object.hexdigest()

        # 16진수 문자열 -> to Int(10진수)
        return int(hex_dig, 16)

def hash_function(key):
    return key % 8

⏰ 해쉬 테이블의 시간복잡도

해쉬 테이블의 경우 충돌이 나지 않는 다는 가정하에 가장 빠른 자료구조라고 할 수 있습니다.
해당 데이터의 key, address를 구하고, 바로 해당 슬롯에 할당하기 때문에 속도는 O(1)로 표현이 가능합니다.
하지만 충돌이 나게 되면, 앞서 소개한 것 처럼 빈 공간을 찾기 위해 순회를 해야 하는 비효율성이 발생하여,
시간복잡도가 O(n)으로 급격히 증가하게 됩니다.

검색에서 해쉬테이블의 사용 예

• 16개의 배열에 데이터를 저장하고, 검색할 때 O(n)
• 16개의 데이터 저장공간을 가진 위의 해쉬 테이블에 데이터를 저장하고, 검색할 때 O(1)