파이썬 hash (Python 해쉬)

hash 개념

Hash는 추가, 삭제, 검색을 거의 O(1)의 성능으로 수행할 수 있는 자료구조입니다. 

Array와 list의 특징을 합친 자료구조이며, 성능이 좋으면서도 구현이 단순합니다. 

 

collision

특정 key 값으로 value를 저장하게 되는데, 이 때 중복된 key가 존재할 수 있습니다. 이런 중복된 key가 존재하는 경우 collision이라고 하며 hash 자료구조에서는 이러한 collision을 해결하기 위한 두 가지 방법을 제공합니다. 

 

linear probing (open addressing)

collision이 발생한 slot부터 linear하게 증가하며 empty slot을 찾는 방법입니다. 

충돌 시 순차적으로 빈 곳을 찾게 되며 입력 자료의 2배 이상의 크기를 지니고 있어야 효과적인 알고리즘 입니다. 

또한 순차적으로 slot을 검색하기 때문에 HDD와 같이 disk처럼 연속적으로 데이터가 저장되는 medium에서 효과를 발휘합니다. 

separate chaning

linked list의 array로 구현해서 list에 계속 추가합니다. 충돌 상황 발생 시 바로 추가하게 되며 작은 hash table도 가능하나 탐색 시간이 증가할 수 있습니다. 

 

시간 복잡도

두 방식 모두 성능은 비삿합니다. 그러나 linear probing의 경우 space complexity가 더 높다는 단점이 존재합니다. 

 

Hash 알고리즘의 주요 구성

• hash function
  • key 값을 자연수로 변환하는 함수
• hash table
  • 여러 bucket 들의 모음
  • hash 함수를 통해 나온 결과를 저장하는 역할을 bucket이 수행
• performance
  • hash function의 성능이 hash 자료구조의 성능에 가장 크게 영향을 끼침
• collision
  • 서로 다른 key가 hash function 연산에서 같은 결과를 주는 경우임
  • 앞서 살펴본 linear probing과 seperate chaning 방법으로 해결함

 

hash 함수의 작성 룰

1) 자주 발생하는 키와 인접 키를 멀어지게 해야 합니다. 

1-1) 카값에 멱등하여 값을 크게 합니다. 

2) hash table의 size는 prime number로 정하는 것이 좋습니다. 

2-1) 적어도 20 이하의 약수는 사용하지 않습니다. 

 

구현

linear probing 방식의 구현

class Node:
    def __init__(self):
        self.key   = None
        self.value = None
        self.state = 'EMPTY'    # EMPTY, FILLED, DELETED

class HashMap:
    def __init__(self, size, fp_hash):
        self.table_size = size
        self.table = [Node() for i in range(size)]
        self.n = 0
        self.fp_hash = fp_hash

    def __next(self, key):
        return 1

    def insert(self, key, value):
        index = start = self.fp_hash(key) % self.table_size
        while self.table[index].state == 'FILLED':
            index = (index + self.__next(key)) % self.table_size
            if index == start:  # table is full
                return False
        self.table[index].state = 'FILLED'
        self.table[index].key   = key
        self.table[index].value = value
        self.n += 1
        return True

    def find(self, key):
        index = start = self.fp_hash(key) % self.table_size
        while self.table[index] != 'EMPTY':
            if self.table[index].state == 'FILLED' and self.table[index].key == key:
                return index
            index = (index + self.__next(key)) % self.table_size
            if index == start:
                return -1
        return -1

    def get(self, key):
        index = self.find(key)
        if -1 == index:
            return -1
        return self.table[index].value

    def remove(self, key):
        index = self.find(key)
        if -1 == index:
            return False
        self.remove_at(index)
        return True

    def remove_at(self, pos):
        if pos < 0 or pos >= self.table_size or self.n == 0:
            return False
        if self.table[pos].state != 'FILLED':
            return False
        self.table[pos].state = 'DELETED'
        self.n -= 1
        return True

seperate chaining 방식의 구현

class Node:
    def __init__(self, key, value):
        self.key   = key
        self.value = value

class Hash_sc:
    def __init__(self, size, fp_hash):
        self.table_size = size
        self.table = [[] for i in range(size)]
        self.n = 0
        self.fp_hash = fp_hash

    def insert(self, key, value):
        index = self.fp_hash(key) % self.table_size
        self.table[index].insert(0, Node(key, value))
        #self.table[index][0:] = Node(key, value) # <- X
        return True

    def find(self, key):
        index = self.fp_hash(key) % self.table_size
        for node in self.table[index]:
            if node.key == key:
                return True
        return False

    def remove_at(self, key):
        index = self.fp_hash(key) % self.table_size
        i = 0
        found = False
        for node in self.table[index]:
            if node.key == key:
                found = True
                break
            i += 1
        if True == found:
            del self.table[index][i]
            return True
        return False