[자료구조] 해시 테이블

들어가며

해시 테이블이란 무엇인가? 해시 테이블 개념 같은 경우에는 정말 쉽다. 우선 해시 테이블은 우리 주변의 물건을 생각해 보면 쉽다. 각자의 방에는 다양한 물건이 있을건데 물건을 찾을 때마다 방안을 뒤지기엔 힘들니까 물건을 상자안에 넣어서 보관하게 되면 이 상자가 바로 해시 테이블 같은 거다.

해시 테이블의 마법

해시 테이블의 가장 큰 장점은 바로 ‘빠른 찾기’이다. 물건 상자에 이름표를 붙이면 원하는 물건을 바로 찾을 수 있다. 해시 테블은 이렇게 동작한다 우리가 무언가를 저장하면, 그 무언가에 특별한 이름표를 붙이고 그리고 나중에 그 이름표만 가지고 빠르게 찾을 수 있다.

‘해시 함수’

그런데, 이 이름표는 어떻게 만들어질까? 라고 고민해봐야 한다. 여기서 ‘해시 함수’가 등장한다. 무언가를 해시 테이블에 넣을 때, 해시 함수는 그것에 대한 특별한 이름표를 만들어준다. 이 이름표는 해시 테이블 안에서 그 물건의 위치를 알려준다.

해시 테이블의 한계

하지만 모든 일에는 제한이 있듯이, 해시 테이블도 완벽하지 않다. 가끔은 같은 이름표가 만들어질 수 있다. 이럴 때는 다른 방법을 사용해서 문제를 해결해야 한다. 그렇지만 대부분의 경우에는 해시 테이블은 정말 빠르게 도와주는건 사실이다.

해시 함수(Hash Function)

기능: 키를 입력받아 고정된 크기의 배열 인덱스를 반환한다.

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

해시(Hash)값이 충돌하는 경우

해시 테이블에서 가장 큰 문제는 두 개 이상의 키가 같은 위치(index)에 저장되려고 할 때 발생하는 ‘충돌’이다.

분리 연결법(Separate Chaining) 충돌이 발생하면, 연결 리스트를 사용하여 같은 인덱스에 여러 키-값 쌍을 저장한다.

class HashTableSeparateChaining:
    def __init__(self, table_size):
        self.table = [[] for _ in range(table_size)]
        self.table_size = table_size

    def insert(self, key, value):
        index = hash_function(key, self.table_size)
        self.table[index].append((key, value))

    def get(self, key):
        index = hash_function(key, self.table_size)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

개방 주소법(Open Addressing) 충돌이 발생하면, 다른 인덱스를 찾아 이동하며 빈 공간을 찾아 저장한다.

좀더 자세한 내용은 What is primary and secondary clustering in hash? 이곳을 확인하면 좋을거 같다.

class HashTableOpenAddressing:
    def __init__(self, table_size):
        self.table = [None] * table_size
        self.table_size = table_size

    def insert(self, key, value):
        index = hash_function(key, self.table_size)
        while self.table[index] is not None:
            index = (index + 1) % self.table_size
        self.table[index] = (key, value)

    def get(self, key):
        index = hash_function(key, self.table_size)
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.table_size
        return None

시간복잡도

평균적인 경우 삽입: O(1) 조회: O(1) 최악의 경우 (모든 키가 충돌할 때) 삽입: O(n) 조회: O(n)

주의: 실제로 해시 테이블을 구현할 때는 해시 함수를 잘 선택하고, 충돌 해결 메커니즘이 필요하다. 위의 코드는 단순한 예제를 보여주기 위한 것이므로 실제 환경에서는 효율적인 해시 함수와 추가적인 로직이 필요할 수 있다.

결론

해시 테이블은 컴퓨터 과학 및 실제 응용 프로그램에서 광범위하게 사용되는 자료 구조 중 하나이다. 그 이유는 그 효율성과 속도 때문이다.

효율성: 해시 테이블은 키-값 쌍을 저장하고 검색하는 데 매우 효율적이다. 평균적인 경우에 O(1)의 시간 복잡도로 데이터를 검색할 수 있다. 이는 대규모 데이터 집합에서도 데이터를 거의 즉시 찾을 수 있다는 것을 의미한다.

해시 함수: 해시 테이블의 핵심은 키를 배열의 인덱스로 변환하는 해시 함수이다. 좋은 해시 함수는 데이터를 배열 전체에 고르게 분포시켜 충돌의 가능성을 최소화 한다.

충돌 해결: 그러나 충돌은 불가피하다. 분리 연결법과 개방 주소법은 충돌을 해결하는 두 가지 대표적인 방법 중 일부이다. 분리 연결법은 연결 리스트를 사용하여 같은 인덱스에 여러 키-값 쌍을 저장하는 반면, 개방 주소법은 다른 인덱스로 이동하여 빈 공간을 찾아 데이터를 저장한다.

용도: 해시 테이블은 데이터베이스, 캐싱, 고성능 검색 기능 및 많은 다른 응용 프로그램에서 사용된다. 그들의 빠른 검색 기능은 실시간 응용 프로그램에서 특히 중요하다.

제한사항: 해시 테이블은 메모리를 많이 사용할 수 있으며, 좋은 해시 함수를 선택하지 않으면 성능이 저하될 수 있다. 또한, 데이터의 삽입, 삭제, 검색 순서에 따라 성능이 일관되지 않을 수 있다.

향후 고려사항: 해시 테이블을 구현하고 사용할 때에는 충돌 해결 전략, 해시 함수의 선택, 배열의 크기 조정 등 다양한 요소를 고려해야 한다. 그렇게 함으로써 최적의 성능을 달성할 수 있다.

전체적으로 볼 때, 해시 테이블은 데이터 관리 및 검색에 있어서 막강한 도구이다. 그러나 그 효과를 최대화하기 위해서는 내부 원리와 구현 방식에 대한 깊은 이해가 필요하다. 이를 통해, 해시 테이블을 효과적으로 사용하면서 그 장점을 최대한 활용할 수 있게 된다.

맨 위로 올라가기