[자료구조] #6_2 해시 테이블

** 충돌(Collision) 해결 알고리즘

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

---

 

2) Linear Probing 기법

• Close 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(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

 

+) 빈번한 충돌을 개선하는 기법

hash_table = list([None for i in range(16)]) # 해시 테이블 저장공간 확대

def hash_function(key): 

       return key % 16 # 해시 함수 재정의

---

 

 

** 파이썬과 해시 함수

• 파이썬의 hash() 함수는 실행할 때마다, 값이 달라질 수 있음
• SHA(Secure Hash Algorithm): 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴

---

ex) SHA-1

import hashlib

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

print (hex_dig) # a94a8fe5ccb19ba61c4c0873d391e987982fbbd3

 

ex) SHA-256

import hashlib

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

print (hex_dig) # 9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08

---

 

 

** 응용

• Chaining 기법을 적용한 해시 테이블 관리 + sha256 해시 알고리즘을 사용한 키 생성 함수

---

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

---

 

 

** 시간 복잡도

• 일반적인 경우(충돌이 발생하지 않음): O(1)
• 최악의 경우(충돌이 모두 발생): O(n)

 

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