자료구조 해쉬 테이블3

1. 충돌(Collision) 해결 알고리즘 (좋은 해쉬 함수 사용하기)

해쉬 테이블의 가장 큰 문제는 충돌(Collision)의 경우입니다. 이 문제를 충돌(Collision) 또는 해쉬 충돌(Hash Collision)이라고 부릅니다.
*충돌(Collision) : 한개 이상의 데이터가 동일한 해쉬어드레스에 저장이 되어야 할 경우

6.1. Chaining 기법

• 개방 해슁 또는 Open Hashing 기법 중 하나: 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
• 충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법

 

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

* hash(값) << 파이썬 내장함수 값을 숫자값으로 리턴 (매번 다름)

print (hash('Dave') % 8)
print (hash('Dbb') % 8)
print (hash('Data') % 8)

1

3

3

save_data('Dbb', '123')
save_data('Data', '456')
read_data('Data')

'456'

hash_table

 

6.2. Linear Probing 기법

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

링크드 리스트로 값을 저장하는 것이 아니라 다음 빈 공간에 값을 넣는다. 

 

연습3: 연습1의 해쉬 테이블 코드에 Linear Probling 기법으로 충돌해결 코드를 추가해보기
1. 해쉬 함수: key % 8
2. 해쉬 키 생성: 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

6.3. 빈번한 충돌을 개선하는 기법

최대한 충돌이 일어나지 않게 하는것이 해쉬코드를 쓰는 이유

• 해쉬 함수을 재정의 및 해쉬 테이블 저장공간을 확대
• 예:

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

def hash_function(key): 
	return key % 16

공간을 늘리면 충돌이 줄어들어 탐색시간도 줄어드는 기법이다.

참고: 해쉬 함수와 키 생성 함수

• 파이썬의 hash() 함수는 실행할 때마다, 값이 달라질 수 있음
• 유명한 해쉬 함수들이 있음: SHA(Secure Hash Algorithm, 안전한 해시 알고리즘)
  • 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬 함수로 유용하게 활용 가능
  • SHA-256은 실제로 블록체인에서 사용하는 기법

SHA-1 사용방법

* hashlib이 동작이 안된다면 pip install hashlib

import hashlib

#'test'라는 데이터를 String  sha1()알고리즘을 쓰고싶다
data = 'test'.encode()  
hash_object = hashlib.sha1()

#encode()는 값을 Byte로 바꾼다는 소리
#값을 바이트로 바꾼다음에 update를 해줘야 hash값이 추출이된다.
hash_object.update(data) #or update(b'test')

#hash_object를 몇진수로 추출하고 싶으냐hexdigest (여기선 16)
hex_dig = hash_object.hexdigest()
print (hex_dig)

a94a8fe5ccb19ba61c4c0873d391e987982fbbd3  << 'test'의 hash값을 16진수로 한것이 이값

 

SHA-256 사용방법

import hashlib

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

9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08

* 출력된 값으로 어떤 값을 입력한건지 추론은 불가능

 

어떤 데이터가 오던간에 고정된 길이로 일관된 값이 나온다.

 

연습4: 연습2의 Chaining 기법을 적용한 해쉬 테이블 코드에 키 생성 함수를 sha256 해쉬 알고리즘을 사용하도록 변경해보기
1. 해쉬 함수: key % 8
2. 해쉬 키 생성: hash(data)

 

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()
        
        # hex_dig 이 9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08
        # 와 같이 16진수 문자열이기 때문에 key % 8을 할수가 없다.
        # 그래서 int 로 바꾸고 16진수의 문자열을 10진수 정수로 만든다는 뜻
        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

 

7. 시간 복잡도

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

해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에, 시간 복잡도는 O(1) 이라고 말할 수 있음

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

• 16개의 배열에 데이터를 저장하고, 검색할 때 O(n) << 배열의 사이즈에 따라 검색하고 순회를 해야한다.
• 16개의 데이터 저장공간을 가진 위의 해쉬 테이블에 데이터를 저장하고, 검색할 때 O(1)

저장과 검색에 있어서 굉장히 효율적인 자료 구조이다.