해시 테이블의 이해와 충돌 해결

해시테이블이란?

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다.

예를 들어 우리가 (Key, Value)가 ("John Smith", "521-1234")인 데이터를 크기가 16인 해시 테이블에 저장한다고 하자.

그러면 먼저 index = hash_function("John Smith") % 16 연산을 통해 index 값을 계산한다. 그리고 array[index] = "521-1234" 로 전화번호를 저장하게 된다.

이러한 해싱 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회할 수 있다. 해시테이블의 평균 시간복잡도는 O(1)이다.

해시 테이블의 주요 구성 요소로는 해시 함수, 버킷, 충돌 해결이 있다.

해시함수

입력 데이터(키)를 해시 테이블의 인덱스(주소)로 변환하는 함수이다. 해시 함수는 키를 특정한 배열 인덱스에 매핑하여 데이터를 저장하고 검색할 수 있게 한다.

나머지 연산 해시 함수(Modulus Hash Function)

가장 기본적인 해시 함수로, 키를 해시 테이블의 크기로 나눈 나머지를 사용하여 인덱스를 계산한다.

def hash_function(key, table_size):
    return key % table_size

장점: 간단하고 계산이 빠르다.
단점: 해시 테이블 크기와 키 값의 배수 관계에 따라 충돌이 발생할 수 있다.

곱셈 해시 함수(Multiplication Hash Function)

키에 특정 상수를 곱한 후, 소수 부분을 사용하여 인덱스를 결정한다. 보통 황금 비율과 관련된 상수를 사용한다.

def hash_function(key, table_size):
    A = (5 ** 0.5 - 1) / 2  # A는 황금 비율의 역수
    return int(table_size * ((key * A) % 1))

장점: 균등한 분포를 제공하며, 해시 테이블 크기의 배수에 영향을 받지 않는다.
단점: 계산이 나머지 연산 해시 함수보다 복잡하다.

곱셈 해시 함수 (Multiplicative Hash Function)

이 함수는 키를 상수와 곱한 후, 결과의 비트 패턴을 이용하여 인덱스를 계산한다.

def hash_function(key, table_size):
    # 상수 A를 이용하여 비트 연산으로 해시 값 계산
    return (key * A) & (table_size - 1)

장점: 상수와 비트 연산을 사용하여 계산이 빠르다.
단점: 상수와 비트 연산의 선택이 중요하다.

제곱 탐사 해시 함수 (Quadratic Probing Hash Function)

키를 특정 함수에 따라 해시 값으로 변환한다. 해시 충돌을 해결하기 위한 방법으로 사용되기도 한다.

def hash_function(key, i, table_size):
    return (key + i**2) % table_size

장점: 충돌 해결에 효과적이며, 선형 탐사보다 충돌을 줄일 수 있다.
단점: 테이블의 크기에 따라 특정 충돌 패턴이 발생할 수 있다.

버킷 (Bucket)

해시 테이블에서 키와 값을 저장하는 배열의 각 위치를 버킷이라고 한다.
각 버킷은 여러 개의 키-값 쌍을 저장할 수 있는 공간을 가질 수 있다.

충돌 해결 (Collision Resolution)

서로 다른 키가 동일한 해시 값을 가지면 충돌이 발생한다.
충돌을 해결하는 방법에는 **체이닝(Chaining)**과 오픈 어드레싱(Open Addressing) 등이 있다.

충돌 해결

데이터를 키로 단순화하여 저장하는 것은 효율적인 방법이지만, 서로 다른 데이터가 동일한 키를 가질 경우 문제가 발생한다. 이러한 현상을 해시 충돌(Hash Collision)이라고 부르며, 이는 특정 키에 여러 데이터가 모이게 되는 상황을 의미한다.

과도한 해시 충돌은 해시 테이블의 성능을 저하시키고, 데이터 검색 및 저장 속도를 늦출 수 있다.

체이닝(Chaining)

아래 그림을 보면 John Smith와 Sandra Dee가 같은 버킷의 값을 가지고 있다. 이렇게 버킷이 겹치면, 버켓 내에 연결리스트(Linked List)를 할당하여, 버킷에 데이터를 삽입하다가 해시 충돌이 발생하면 연결 리스트로 데이터들을 연결하는 방식이다.

Sandra Dee라는 사람의 연락처를 삽입할 때, 충돌이 일어나니 버켓 내에서 연결리스트로 데이터를 연결하는 것을 확인할 수 있다.

오픈 어드레싱(Open Addressing)

체이닝의 경우 버킷이 꽉 차더라도 연결리스트로 계속 늘려가기에, 데이터의 주소값은 바뀌지 않는다.(Closed Addressing) 하지만 개방 주소법의 경우에는 다르다.

해시 충돌이 일어나면 다른 버킷에 데이터를 삽입하는 방식을 개방 주소법이라고 한다. 개방 주소법은 대표적으로 3가지가 있다.

아래 그림은 선형 탐사에 대한 예시이다.

선형 탐사(Linear Probing)
- 해시 충돌이 발생하면 정해진 간격(일반적으로 1칸)으로 순차적으로 다음 버킷을 탐색하여 빈 버킷을 찾는 방법이다.
- 탐색과 삽입 속도가 빠르지만, 충돌이 많이 발생하면 클러스터링 문제가 생길 수 있다. 클러스터링은 데이터가 몰려 있는 현상을 말하며, 이는 추가적인 충돌을 유발해 성능을 저하시킬 수 있다.
제곱 탐사(Quadratic Probing)
- 충돌이 발생할 때 탐사 간격이 일정한 크기로 증가하는 것이 아니라, 제곱수의 크기로 증가하는 방식이다.
- 예를 들어, 첫 번째 충돌 시 1칸, 두 번째 충돌 시 4칸, 세 번째 충돌 시 9칸 등으로 점점 더 큰 간격으로 이동하여 충돌 문제를 해결한다.
- 클러스터링 문제를 완화할 수 있지만, 여전히 이차 클러스터링(secondary clustering) 문제가 발생할 수 있다.
이중 해싱(Double Hashing)
- 해시 충돌이 발생했을 때, 두 번째 해시 함수를 사용하여 탐사 간격을 결정하는 방식이다.
- 이중 해싱은 해시 함수의 결과값에 따라 이동할 간격이 달라지므로, 충돌 가능성을 최소화하고 클러스터링 현상을 줄이는 데 매우 효과적이다.
- 해시 함수가 잘 설계되어 있다면, 버킷의 분포가 고르게 되어 성능이 개선된다.

코드 예시

아래 코드에서는 체이닝 방식으로 해시 테이블을 구현한다.

HashNode

HashNode 클래스는 해시 테이블의 각 버킷을 정의하며, 키(key)와 값을 저장하고 해시 충돌을 대비해 next 포인터를 구현하여 다음 노드를 가리킨다.

충돌 시 동일한 인덱스에 여러 키-값 쌍이 저장될 수 있는데, 이를 연결 리스트 형태로 관리하여 효율적으로 데이터를 처리할 수 있게 한다. (해시 체이닝 방식)

class HashNode:
    def __init__(self, key=None, value=None):
        self.key = key      # 노드의 키(key)를 저장
        self.value = value  # 노드의 값(value)을 저장
        self.next = None    # 다음 노드를 가리키는 포인터, 초기값은 None

HashTable

해시 테이블의 크기를 10으로 설정한다. 즉, 이 해시 테이블은 10개의 버킷을 가진다.

class HashTable:
    def __init__(self):
        self.size = 10
        self.table = [None] * self.size

hash_function

나머지 연산 해시 함수를 이용해 해시 함수를 생성한다.

예를 들어, 만약 key가 23이고 self.size가 10이라면, 23 % 10 = 3이 된다. 따라서 이 경우 키 23은 인덱스 3에 해당하는 위치에 저장된다.

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

put

put 메서드는 해시 테이블에 키-값 쌍을 삽입하는 기능을 담당한다. 버킷이 비어있을 경우와 충돌이 발생했을 경우의 두 가지 경우를 구현 해주었다.

해시 인덱스 계산: 입력된 키를 이용하여 _hash_function을 호출해 인덱스를 계산한다.
버킷이 비어있는 경우: 계산된 인덱스에 해당하는 버킷이 비어 있으면, 그 자리에 새로운 HashNode 객체를 생성하고 키-값 쌍을 저장한다.
충돌이 발생한 경우: 이미 해당 인덱스에 다른 노드가 존재하는 경우, 연결 리스트의 끝까지 이동하여 새로운 노드를 추가한다. 이를 통해 같은 인덱스에 여러 키-값 쌍을 저장할 수 있다.

    def put(self, key, value):
        index = self._hash_function(key)
        if self.table[index] is None:
            self.table[index] = HashNode(key, value)
        else:
            node = self.table[index]
            while node.next is not None:
                node = node.next
            node.next = HashNode(key, value)

get

get 메서드는 해시 테이블에서 주어진 키에 해당하는 값을 검색하는 기능을 수행한다. 입력된 키를 이용해 해시 인덱스를 계산하고, 해당 인덱스에서 키와 일치하는 값을 반환한다. 만약 키가 일치하지 않는 경우, next 포인터를 따라 이동하여 검색을 계속한다.

해시 인덱스 계산: 입력된 키를 이용하여 _hash_function을 호출해 해당 키의 해시 인덱스를 계산한다.
노드 탐색 시작: 계산된 인덱스 위치에 있는 첫 번째 노드(node)를 가져온다.
노드 탐색:
- 현재 노드가 None이 아닐 동안 반복한다.
- 만약 현재 노드의 key가 검색하고자 하는 key와 일치하면, 해당 노드의 value를 반환한다.
- 일치하지 않는 경우, 다음 노드로 이동하기 위해 node를 node.next로 업데이트한다.
키 미발견 시 처리: 반복이 끝날 때까지 원하는 키를 찾지 못하면, -1을 반환하여 키가 해시 테이블에 존재하지 않음을 나타낸다.

    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

remove

remove 메서드는 해시 테이블에서 주어진 키에 해당하는 값을 삭제하는 기능을 수행한다. _hash_function을 이용해 인덱스를 계산하고 현재 노드의 key가 삭제하고자 하는 key와 일치하는지를 확인한다.

일치할 경우 첫 번째 노드라면 인덱스를 다음 노드로 업데이트하고, 아닐 경우 이전 노드의 next 포인터를 현재 노드의 다음 노드로 연결하여 삭제한다.

해시 인덱스 계산: 입력된 키를 이용하여 _hash_function을 호출해 해당 키의 해시 인덱스를 계산한다.
노드 탐색 시작: 계산된 인덱스 위치에 있는 첫 번째 노드(node)를 가져온다.
노드 탐색:
- 현재 노드가 None이 아닐 동안 반복한다.
- 만약 현재 노드의 key가 삭제하고자 하는 key와 일치하면,
  - prev_node가 None일 경우: 첫 번째 노드를 삭제하므로 해당 인덱스를 다음 노드(node.next)로 업데이트한다.
  - 그렇지 않으면: 이전 노드(prev_node)의 next 포인터를 현재 노드의 다음 노드(node.next)로 연결하여 삭제한다.
- 노드를 찾은 경우 즉시 메서드를 종료한다.
키 미발견 시 처리: 원하는 키를 찾지 못하면, 메서드는 종료되며 아무 작업도 수행하지 않는다.

    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
                return
            prev_node = node
            node = node.next

전체 코드는 다음과 같다.

class HashNode:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.next = None

class HashTable:
    def __init__(self):
        self.size = 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)
        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

    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
                return
            prev_node = node
            node = node.next

해시 테이블은 데이터 저장 및 검색에 있어 매우 효율적인 자료구조로, 특히 대량의 데이터를 다룰 때 그 강점을 발휘한다.

평균적으로 O(1)의 시간 복잡도로 데이터를 삽입하고 조회할 수 있어, 데이터베이스 인덱싱, 캐싱, 프로그래밍 언어의 객체 관리 등에서 널리 사용된다.

하지만 해시 충돌이 발생할 수 있으며, 이를 효과적으로 해결하기 위한 방법론(체이닝, 오픈 어드레싱 등)을 이해하고 적절히 구현하는 것이 중요하다고 생각한다.

참고

[자료구조] 해시테이블(HashTable)이란? - MangKyu's Diary (tistory.com)

[IT 기술면접 준비자료] 해시(Hash)와 해시충돌(Hash Collision) (tistory.com)

코드 예시

참고

티스토리툴바