자료구조) 해쉬테이블(2/2)-Collision

지난 게시글에 이어서 해쉬테이블에 대해서 알아보도록 할게요 

지난 게시글에서 해쉬가 검색, 삽입, 삭제에서 O(1)을 보여주며 굉장히 빠르게 작동하지만 해쉬함수에 따라 해쉬값이 겹치는 Collision(충돌)이 일어날 수 있다고 말씀드렸어요.

애초에 해쉬 값이 겹치지 않을 수 있는 해쉬 함수를 만들거나, 해쉬 테이블이 크면 너무 좋겠지만, 현실에서는 그럴수 없는 경우도 있으니까요

 

해쉬테이블의 Collision이 발생해도 처리할 수 있는 방법의 흐름에는 크게 2가지가 있습니다. 

Open Hashing과 Close Hashing이 있어요

 

Open Hashing은 Collision이 일어났을 때, 외부 저장공간(메모리)를 활용하는 방법입니다. 특히 LinkedList나 BST를 이용하지요. 그래서 Seperate Chaining이라고 합니다.

같은 해쉬값을 가질때(해쉬테이블에서의 주소가 같을때) 해당 주소에 링크드 리스트를 만들어(파이썬의 경우 리스트를 만들어) 길게 저장합니다.  그래서 충돌이 발생할때면 검색과 삭제가 O(n)이 걸릴 수 있습니다. (만약에 BST를 이용한다면 최악의 상황 시간복잡도를 O(logn)으로 낮출 수 있습니다.)

한번 구현을 같이 해볼까요 

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

def get_key(key):
	return hash(key)

def hash_function(key):
	returtn key % 8

def save(key, value):
	index_key = get_key(key)
    hash_key = hash_function(index_key)
    if hash_table[hash_key] == 0 : # hash_key 위치에 아무것도 저장되어있지 않다면
    	hash_table[hash_key] = [index_key, value]
    else: # hash_key 위치에 뭔가 저장되어 있다면 
    	for i in range(len(hash_table[hash_key])):
        	if hash_table[hash_key][i][0] == index_key : #수정하고 싶어서 저장했을때
            	hash_table[hash_key][i][1] = value
                return # 수정하고 싶어서 저장한것이니까, 여기서 나가줘야 함 
        hash_table[hash_key].append([index_key, value])

def read(key):
	inde_key = get_key(key)
    hash_key = hash_function(index_key)
    if hash_table[hash_key] != 0 : #뭔가 저장되어 있다면 
    	for i in range(len(hash_table[hash_key])):
        	if hash_table[hash_key][i][0] == index_key : 
            	return hash_table[hash_key][i][1]
        return # linked-list 안에서 못찾았기 때문에 그냥 return 
    else:
    	return : # 전체 list에서 못찾았기 때문에 그냥 return

 

위에서 hash()라는 파이썬 내장함수를 사용했습니다. 

hash()는 str 형태의 데이터의 해쉬값을 손쉽게 만들어 주지만 런타임 환경이 바뀔때마다 값이 바뀌는 단점이 있습니다. 

그래서 SHA 해쉬 함수를 쓰기도 해요

SHA는 Secure Hash Algorithm으로 어떠한 환경에서도 동일한 해쉬 값을 내어 줍니다. 

보통 SHA256을 많이 사용합니다.(SHA1 등 종류가 다양합니다)

import hashlib

def Hash(data):
	encoding_data = data.encode() #바이트로 바꿔주는 것
    hash_function_objecct = hashlib.sha256()#SHA256을 적용할 수 있는 개체를 만들어줌
    hash_function_object.update(encoding_data) # 해쉬값으로 바꿔줌
    hexData = hash_function_object.hexdigest() # 해쉬값을 16진수로 바꿔줌
    intData = int(hexData, 16) # 16진수를 10진수, int로 바꿔줌
    return intData

 

또한 위에서  hash()를 썼음에도 hash_function을 만들어서 따로 %8로 나눠줬는데요,

그 이유는 8개인 hash_table에 저장할 주소로 사용하기 위함입니다. hash()를 쓰게 되면 10자리도 넘는 실수가 나오기 때문에 그 자체를 바로 해쉬값으로 쓰기 무리가 있습니다. 해쉬 테이블이 적은 수로 한정되어 있기 때문이에요

그래서 해쉬값으로 스트링 값을 바꿔주고 해쉬 테이블에 저장하고자 다시 한번 해쉬 펑션을 적용해 줬답니다. 다시한번 말하지만 해쉬 펑션을 통한 해쉬 값은 해쉬테이블에 데이터를 저장하기 위해 주소가 된답니다~

 

Collision을 해결하는 방법을 이어서 알아볼까요

Close Hashing은 Open Hashing과 다르게 Collision이 발생했을때, 남는 내부 슬롯을 이용하는 것입니다. Open Address라고도 합니다. Collision이 발생하면 내부의 다른 슬롯으로 이동하면서, 이동하는 슬롯이 비어있는 곳이 나타날때 저장하게 됩니다. 

그 방법에는 대표적으로 Linear Probing, Quadratic Probing, Double Hashing이 있습니다. 

LinearProbing은 +1, +2등 지정한 수만큼, Quadratic Probing은 2^2, 3^3 처럼 제곱수만큼 슬롯을 이동합니다. 

LinearProbing과 Quadrativ Probing은 충돌 횟수가 많아지면 특정 영역에 데이터가 몰리는 Clustering 현상이 나타날 수 있습니다. 

그 점을 보완하기 위해 Double Hashing이 있습니다. Double Hashing은 해쉬 함수를 2개 사용하는 것인데요, 하나의 해쉬 함수는 해쉬 값(해쉬주소)을 얻기 위해, 또다른 해쉬 함수는 콜리젼이 발생했을때 건너뛸 간격을 얻기 위함입니다. 

 

한번 리니어 프로빙을 구현 해볼까요

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

def get_key(key):
	return hash(key)

def hash_function(key):
	returtn key % 8
    
def save(key, value):
	index_key = get_key(key)
    hash_key = hash_function(index_key)
    if hash_table[hash_key] == 0 :
    	hash_table[hash_key] = [index_key, value]
    else : 
    	for i in range(hash_key, hash_key + len(hash_table)): # 해쉬 키 이외에 전체 순회 하기 위해 
        	j = 0
            if i <= len(hash_table): 
            	if hash_table[i] == 0 :
                	hash_table[i] = [index_key, value]
                elif hash_table[i][0] ==index_key : # 데이터를 수정하기 위해 저장한 경우 
                	hash_table[i][1] = value
                    return
            elif i > len(hash_table): # 
            	if hash_table[j] ==0 :
                	hash_table[j] = [index_key, value]
                    j += 1
                elif hash_table[j][0] ==index_key :
                	hash_table[j][1] = value
                    return

def read(key): 
	index_key = get_key(key)
    hash_key = hash_function(index_key)
    if hash_table[hash_key] == 0 :
    	return None
    elif hash_table[hash_key][0] ==  index_key: 
    	return hash_table[hash_key][1] 
    elif hash_table[hash_key][0] !=  index_key: 
        for i in range(hash_key, hash_key + len(hash_table)): # 해쉬 키 이외에 전체 순회 하기 위해 
            j = 0
            if i <= len(hash_table): 
                hash_table[i][0] ==index_key : # 데이터를 수정하기 위해 저장한 경우 
                return hash_table[i][1]
            elif i > len(hash_table): # 
                return hash_table[j][1]
        return None # 전체를 뒤져도 못찾을 경우

----

해쉬 테이블도 끝났네요! 

해쉬테이블도 제게 약간 안개에 쌓여있는 존재 같았는데 한번 쫙 정리하니까 마음이 편하네요