자료구조

Hash Table

Hash Table 개념

Key-value를 사용하되, 가장 큰 Key 만큼의 배열을 생성하여 각각의 key를 인덱스로 사용하는 방식을 Direct Access Table 이라고 한다.
Direct Access Table은 모든 값에 $O(1)$으로 접근할 수 있지만 key가 많아질수록 저장 공간이 많이 소요된다. 즉, 낭비되는 저장공간이 많다.

반면 Hash Table 은 고정된 크기의 배열을 만들고, 해시 함수를 이용하여 key를 원하는 범위의 값으로 리턴한다. 그리고 해시 함수 결과 값 인덱스에 key-value를 모두 저장하는 자료구조이다.

해시 함수의 조건

1. 한 해시 테이블의 해시 함수는 결정론적이어야 한다. 즉, 같은 Key 값을 넣었을 때 항상 같은 결과가 나와야 한다.
2. 결과 해시값이 치우치지 않고 고르게 나온다. 만약 원하는 자연수의 범위가 0~100인 경우, 모든 숫자가 나올 수 있는 확률은 최대한 비슷해야 한다.
3. 빨리 계산할 수 있어야 한다.

해시값 생성 예시)

def hash_function_reminder(key, size):
	"""해시 테이블의 key를 나누기 방법으로 0~size 사이의 자연수로 변환"""
    return key % size
    
def hash_function_multiplication(key, size, a):
    """해시 테이블의 key를 곱셈 방법으로 0~size 사이의 자연수로 변환"""
    temp = a * key # key 와 0<a<1 의 임의의 a를 곱한다.
    temp = temp - int(temp) # 소수점 부분만 저장한다.
    return int(size*temp)

파이썬은 내장된 hash 함수를 통해 해시값을 만들 수 있다. 이 때, 문자열도 임의의 정수로 변환가능하다. 그러나 hash 함수는 불린, 정수, 소수 등의 불변 타입 자료형에만 사용 가능 하다.

Hash Table collision(충돌)과 Chaining

서로 다른 두 개 이상의 key-value에 동일한 해시값이 생성된 경우, 충돌이 일어난다. 이 때, 링크드 리스트를 활용하여 chaining을 한다.

class Node:
    """더블리 링크드 리스트 노드"""
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None
        
class LinkedList:
    """링크드 리스트 클래스"""
    def __init__(self):
        self.head = None
        self.tail = None
        
    def find_node_with_key(self, key):
        """링크드 리스트에서 주어진 데이터를 가진 노드 리턴"""
        iterator = self.head
        
        while iterator is not None:
            if iterator.key == key:
                return iterator
                
            iterator = iterator.next
            
        return None
    
    def append(self, key, value):
        """링크드 리스트 추가 메소드"""
        new_node = None(key, value)
        
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
            
    def __str__(self):
        """링크드 리스트 문자열 표현"""
        _str = ""
        
        iterator = self.head
        
        while iterator is not None:
            _str += f"{iterator.key}: {iterator.value}\n"
            iterator = iterator.next
            
        return _str

Hash Table Chaining의 시간 복잡도

Hash Table 은 순서가 존재하지 않기 때문에 접근 연산이 필요하지 않다.

총 n개의 key-value를 저장하는 경우

• 탐색: Key를 통해 Value를 찾아내는 연산 $O(n)$

  • 해시 함수 계산: $O(1)$
  • 배열 인덱스 접근: $O(1)$
  • 링크드 리스트 노드 탐색: $O(n)$

• 삽입: 새로운 key-value를 저장하는 연산 $O(n)$

  • 해시 함수 계산: $O(1)$
  • 배열 인덱스 접근: $O(1)$
  • 링크드 리스트 노드 탐색: $O(n)$
  • 링크드 리스트 저장/노드 수정: $O(1)$

• 삭제: 특정 key가 주어졌을 때, key-value 삭제 $O(n)$

  • 해시 함수 계산: $O(1)$
  • 배열 인덱스 접근: $O(1)$
  • 링크드 리스트 노드 탐색: $O(n)$
  • 링크드 리스트 노드 삭제: $O(1)$

Chaining을 활용한 Hast Table 연산의 시간 복잡도는 $O(n)$ 이다. 하지만 이는 최악의 상황을 가정한 것이다. 즉, n개의 key-value 가 모두 하나의 해시 값에 저장되는 경우를 말한다. 하지만 이는 매우 드문 경우이기 때문에 평균적인 시간 복잡도를 계산하여, 시간 복잡도를 재평가 해보자.

다음과 같이 가정한다.
1. 해시 테이블의 총 key-value 수: $n$
2. 해시 테이블이 사용하는 전체 배열의 크기: $m$

이 때, 링크드 리스트의 평균 길이는 $\frac n m$으로 볼 수 있다. 해시 테이블의 총 10개의 배열을 가지고 있고, key-value가 5쌍이 있다고 했을 때 평균적인 링크드 리스트의 길이는 0.5이다.

따라서 해시 테이블의 각 연산들에 대한 시간 복잡도는 $O(\frac nm)$ 이다.

여기서, 만약 key-value 의 수와 배열의 크기를 동일하게 유지한다고 하면, $n=m$ 이다. 이를 다시 시간 복잡도에 대입하면 모든 연산에 대한 시간 복잡도는 $O(1)$ 으로 볼 수 있다.

해시 테이블의 탐색, 삽입, 삭제의 연산들은 최악의 경우 $O(n)$ 이 걸리며, 평균적으로는 $O(1)$ 의 시간이 소요된다고 볼 수 있다.

Chaining을 쓰는 해시 테이블을 구현해보면 다음과 같다.

from base import LinkedList  # 해시 테이블에서 사용할 링크드 리스트 임포트

class HashTable:
    def __init__(self, capacity):
        self._capacity = capacity  # 파이썬 리스트 수용 크기 저장
        self._table = [LinkedList() for _ in range(self._capacity)]  # 파이썬 리스트 인덱스에 반 링크드 리스트 저장

    def _hash_function(self, key):
        """
        주어진 key에 나누기 방법을 사용해서 해시된 값을 리턴하는 메소드
        주의: key는 파이썬 불변 타입이여야 한다.
        """
        return hash(key) % self._capacity


    def _get_linked_list_for_key(self, key):
        """주어진 key에 대응하는 인덱스에 저장된 링크드 리스트를 리턴하는 메소드"""
        hashed_index = self._hash_function(key)

        return self._table[hashed_index]


    def _look_up_node(self, key):
        """파라미터로 받은 key를 갖고 있는 노드를 리턴하는 메소드"""
        linked_list = self._get_linked_list_for_key(key)
        return linked_list.find_node_with_key(key)


    def look_up_value(self, key):
        """
        주어진 key에 해당하는 데이터를 리턴하는 메소드
        """
        return self._look_up_node(key).value


    def insert(self, key, value):
        """
        새로운 key - value 쌍을 삽입시켜주는 메소드
        이미 해당 key에 저장된 데이터가 있으면 해당 key에 해당하는 데이터를 바꿔준다
        """
        existing_node = self._look_up_node(key)  # 이미 저장된 key인지 확인한다

        if existing_node is not None:
            existing_node.value = value  # 이미 저장된 key면 데이터만 바꿔주고
        else:
            # 없는 key면 링크드 리스트에 새롭게 삽입시켜준다
            linked_list = self._get_linked_list_for_key(key)
            linked_list.append(key, value)

    def delete_by_key(self, key):
        """주어진 key에 해당하는 key - value 쌍을 삭제하는 메소드"""
        node_to_delete = self._look_up_node(key)
        
        if node_to_delete:
            linked_list = self._get_linked_list_for_key(key)
            linked_list.delete(node_to_delete)

    def __str__(self):
        """해시 테이블 문자열 메소드"""
        res_str = ""

        for linked_list in self._table:
            res_str += str(linked_list)

        return res_str[:-1]

앞서 링크드 리스트에서 다뤘던 기본적인 append, delete 등의 연산이 base.py module 에 존재한다고 가정했을 때, 위와 같이 Chaining 을 사용한 해시 테이블의 메소드를 구현해 볼 수 있다.

Open Addressing을 이용한 충돌 해결

Open Addressing: 충돌이 일어났을 때, 다른 비어 있는 인덱스를 찾아서 저장하는 방식

Open Addressing 방식 중에서도 충돌이 일어났을 때, 한 칸씩 다음 인덱스가 비었는지 확인하는 방식을 선형 탐사(Linear Probing) 이라고 한다.

또다른 방식으로는 제곱 탐사(Quadratic Probing) 이 있다. 이는 인덱스 10에 이미 데이터가 있을 경우 $10 + 1^2 = 11, 11+ 2^2 = 15, 15 + 3^3 = 24$ 등 제곱한 값들을 이용하여 인덱스를 찾는 방식이다.

선형 탐사방식의 삽입/탐색/삭제 연산

어떠한 key 값에 대한 해시 함수값이 20이라고 가정한다.

• 삽입: 인덱스 20에 이미 값이 있는지를 확인하고 존재하는 경우 인덱스를 하나씩 옮겨가면서 빈 인덱스가 나오면 key-value를 삽입한다.
• 탐색: 인덱스 20부터 선형적으로 탐색하되, 비어 있는 인덱스가 나온다면 해당 key-value가 존재하지 않는 것이라고 판단하고 탐색을 종료한다. 그 이유는 정상적으로 append 되었다면 비어 있던 해당 인덱스에 값이 삽입 되었을 것이기 때문이다.
• 삭제: 마찬가지로 인덱스 20부터 확인하여 값을 찾는다. 값을 찾았다고 바로 삭제하지 않고, "DELETED" 와 같이 구분값을 남겨놓는다. 그 이유는 탐색 시에 비어 있는 인덱스를 발견하면 탐색을 종료하기 때문에 중간에 빈 인덱스가 발생하면 실제 그 값이 그 뒤에 있더라고 없다고 판단하게 되기 때문이다.

Open Addressing을 사용하는 해시 테이블은 삽입, 삭제에 모두 탐색 연산이 포함된다. 탐색 연산은 최악의 경우 최초 접근하고자 하는 인덱스 - 1 번째만 비어 있다고 가정했을 때, 총 $n$번 만큼 탐색을 시도해야 하므로 총 $O(n)$의 시간 복잡도를 갖는다. 그러므로 삽입, 삭제 역시 $O(n)$의 시간 복잡도를 갖는다.


이번에도 마찬가지로 Open Addressing을 사용하는 해시 테이블에 대한 평균 시간 복잡도를 구해보자.

앞서 사용했던 링크드 리스트의 평균 길이 $\frac nm$ 를 load factor 라고 한다. load factor $a$ 는 해시 테이블이 사용하는 배열의 크기 $m$ 을 해시 테이블 안의 데이터 쌍 수인 $n$ 으로 나눈 값이다. 즉, $a=\frac nm$ 이다. 해시 테이블이 얼마나 차있는지를 나타내는 변수라고 생각하면 될 것 같다.

수학적인 분석을 했을 때(가슴으로는 이해됨) Open Addressing을 사용하는 해시 테이블에서 평균적으로 탐색해야 하는 횟수는 $\frac 1{1-a}$ 이다.

이는 배열이 총 100칸이고 90개의 key-value 가 있을 때, load factor $(a)=0.9$ 가 나온다. 기대값에 $a$를 대입하면 10이 나온다. 즉, 빈 인덱스를 찾기 위해 평균적으로 인덱스 10개보다 적은 인덱스를 탐색해야 한다는 뜻이다.

해시 테이블이 절반 정도 차있는 상태라면 ($a=0.5$) 기대값은 2보다 작다. 평균적으로 2개의 인덱스만 확인해봐도 빈 칸을 찾을 수 있다는 뜻이다.

따라서 최악의 경우 $O(n)$의 시간 복잡도를 가졌으나 평균적으로는 $O(1)$ 의 시간 복잡도를 갖는다고 할 수 있다. 앞서 봤던 Chaining 과 마찬가지로 탐색, 삽입, 삭제 연산에 평균적으로 모두 $O(1)$ 시간을 갖는다고 할 수 있다. 배열과 링크드 리스트에 비해 매우 효율적인 것을 알 수 있다.