[자료구조] 해쉬 테이블(Hash Table) -Data Structure with 파이썬

테이블이란?

표와 같은것으로 모든표를 가리켜 테이블이라 하지않는다.

따라서 저장된 데이터의 형태가 키(key)와 값(value)로 하나의 쌍을 이룰때에만 테이블로 구분짓는다.

이때 키는 데이터를 구분하는 기준이 되기 때문에 모든 키는 중복 되지않고 키가 존재하지 않는 값은 저장할 수 없다.

 

 

해쉬 테이블이란?

• Key와 Value로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조
• 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 인덱스 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하여 검색을 빠르게 하기 위한 자료 구조

위에서 말했던 테이블과 다른점은 해쉬함수를 이용한다는 것이다.

 

예) 파이썬 사전(Dictionary) 자료형 - Key를 가지고 바로 데이터(Value)를 꺼냄

 

보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용

• 파이썬에서는 해쉬를 별도 구현할 이유가 없음 왜? 딕셔너리 타입을 사용하면 됨

https://www.fun-coding.org/00_Images/hash.png

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

 

장단점, 용도

• 장점
  • 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
  • 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
• 단점
  • 일반적으로 저장공간이 좀더 많이 필요하다.
  • 여러 키에 해당하는 주소가 동일할 경우 충돌(Collision)을 해결하기 위한 별도 자료구조가 필요함
• 주요 용도
  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐쉬 구현시 (중복 확인이 쉽기 때문)

 

클래스로 해쉬테이블 구현하기.

# Hash Table
class HashTable:
    def __init__(self, table_size):
        self.size = table_size
        self.hash_table = [0 for _ in range(self.size)]
        
    def getKey(self, data):
        self.key = ord(data[0])
        return self.key
    
    def hashFunction(self, key):
        return key % self.size

    def getAddress(self, key):
        myKey = self.getKey(key)
        hash_address = self.hashFunction(myKey)
        return hash_address
    
    def save(self, key, value):
        hash_address = self.getAddress(key)
        self.hash_table[hash_address] = value
        
    def read(self, key):
        hash_address = self.getAddress(key)
        return self.hash_table[hash_address]
    
    def delete(self, key):
        hash_address = self.getAddress(key)
        
        if self.hash_table[hash_address] != 0:
            self.hash_table[hash_address] = 0
            return True
        else:
            return False

 

클래스가 아닌 것으로 구현하기

# hash table 만들기
hash_table = list([0 for i in range(8)])

# 해쉬 함수 만들기
def hash_function(key):
    return key % 8
    
# 해쉬 테이블에 값 저장
def save_data(data, value):
    hash_address = hash_function(get_key(data))
    hash_table[hash_address] = value

# 해쉬 테이블의 값 읽기 키를 입력 받아서
def read_data(data):
    hash_address = hash_function(get_key(data))
    return hash_table[hash_address]

# 해쉬함수를 거친 키 값 생성
def get_key(data):
    return hash(data) #키를 생성할때 내장함수인 hash를 쓸 수 있다.
    
save_data('Dave', '0102030200')
save_data('Andy', '01033232200')
read_data('Dave')
# '0102030200'

 해쉬 테이블 시간 복잡도

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

 

충돌이 발생하는 이유

서로 다른 두 개의 입력값(키)에 대해 해시 함수가 동일한 출력값을 내면 해쉬주소가 겹치게 된다 이때 그 해쉬주소에 slot이 하나만 있다면 하나의 값만 저장할 수 있게 된다. 그러면 새로운값으로 덮어쓰게 되면 기존 값은 사라지게 되기 때문이다. 이것을 Collision인 충돌이 발생한다라고 한다.

 

충돌이 발생하면 해시 함수를 이용한 자료구조나 알고리즘의 효율성을 떨어뜨리며, 따라서 해시 함수는 해시 충돌이 자주 발생하지 않도록 구성되어야 한다 출처

 

 

충돌(Collision) 해결 알고리즘

1. Chaining 기법

• 개방 해슁 또는 Open Hashing 기법 중 하나: 해쉬 테이블 저장공간 외의 공간을 활용하는 기법

- Linked List를 이용하는 방법으로 저장하려는 해시테이블에 이미 같은 키값의 데이터가 있다면, 노드를 추가하여 다음 노드를 가르키는 방식으로 구현하는 것

즉 충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법

Chaining

예

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 address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법 ( 저장공간 활용도를 높이기 위한 기법 )

 

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

 

유명한 해쉬 함수 - SHA(Secure Hash Algorithm, 안전한 해시 알고리즘)

why? 파이썬의 hash() 함수는 실행할 때마다, 값이 달라질 수 있음

사용의 예

import hashlib

data = 'test'.encode()
hash_object = hashlib.sha1()
hash_object.update(data) # 바이트코드로 변환
hex_dig = hash_object.hexdigest() #16진수로 바꾸어줌
print (hex_dig)
# a94a8fe5ccb19ba61c4c0873d391e987982fbbd3

import hashlib

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


# 파이썬의 hash함수가 아닌 sha256이용
def get_key(data):
        hash_object = hashlib.sha256()
        hash_object.update(data.encode())
        hex_dig = hash_object.hexdigest()
        return int(hex_dig, 16)

코드 참고 : 패스트캠퍼스 알고리즘/기술면접