[자료 구조] 해시테이블 (Hash Table)

해시테이블이란?

• 해시테이블이란 해시함수를 이용해 키를 값에 매핑하는 자료구조

구현

충돌

• 아무리 좋은 해시 함수라도 충돌을 피하기는 어렵다.
• 예측 가능한 범위 내에서 해시값이 나오고, 데이터와 짝지어지는 것이기 때문에 해시값이 중복될 수 있다.
  👉 입력값이 달라도 똑같은 결과가 나오면 충돌
• 이를 다루는 방식은 체이닝(Chaining), 오픈 어드레싱(Open Addressing) 이 있다.
• 오픈 어드레싱은 탐사를 통해 ‘빈 공간을 찾아나서는’ 방식
• 체이닝은 충돌 발생 시 ‘연결’해가는 것

 

• 오픈 어드레싱 O(1)
  
• 체이닝 O(n)

 

• 오픈 어드레싱은 값이 뭉치는 클러스터링 이 발생할 수 있고,
• 체이닝은 메모리 오버헤드와 길어질 경우 탐색이 느려진다는 단점
•  C++, Java, Go는 체이닝을 택하고 Python, Ruby는 오픈 어드레싱을 택하고 있다.

구현 (Python)

• 체이닝 방식의 해시테이블

# test.py

ht = HashTable()

ht.put(1, 1)
ht.put(2, 2)
assert ht.get(1) == 1
assert ht.get(2) == 2
assert ht.get(3) == -1

ht.put(12, 1)
ht.put(22, 2)
ht.put(32, 3)
assert ht.get(12) == 1
assert ht.get(22) == 2
assert ht.get(32) == 3

ht.remove(12)
assert ht.get(2) == 2
assert ht.get(12) == -1
assert ht.get(22) == 2
assert ht.get(32) == 3

ht.get(2)

# structures.py


class HashTable:
    def __init__(self):
        self.size = 10 # 해시테이블의 사이즈 (10으로 나눈 나머지이기떄문에 10으로 설정)
        self.table = [None] * self.size

    def _hash_function(self, key):
        return key % self.size

    def put(self, key, value):

        index = self._hash_function(key) # 키를 넣었을 때 결과값

        if self.table[index] is None: # 값이 없을 때 (푸시한적이 없는 해싱값일 때)
            self.table[index] = HashNode(key, value)#next=None

        else: # 이미 값이 있을 때 (푸시한적이 있는 해싱값일 때) - 체이닝방식이므로 같은 값은 맨 끝에 계속 붙여주면 됨
            node = self.table[index] 
            while node.next is not None: # 다음 노드가 없을 때 까지(맨끝까지)
                node = node.next
            node.next = HashNode(key, value)

    def get(self, key):

        index = self._hash_function(key)
        node = self.table[index]

        while node is not None: #노드에 배정된 키가 있을 동안
            if node.key == key: #내가 원하는 값(내가 넣은 키라면)
                return node.value #값 반환
            node = node.next #원하는 노드가 아니면 옮기자
        return -1 # 배정된 게 없다면 -1 반환하자

    def remove(self, key):

        index = self._hash_function(key)
        node = self.table[index]
        prev_node = None

        while node is not None:
            if node.key == key:

                if prev_node is None: # 이전 노드가 없다 - 첫번째꺼다 - 지금거를 다음걸로 바꾼다
                    self.table[index] = node.next
                else:
                    prev_node.next = node.next # 이전 노드의 next를 지금거의 다음걸로 넘긴다 (가운데를 빼는 느낌)
                return

            prev_node = node # 이전 노드를 지금 노드로 넘긴다
            node = node.next