[Python-알고리즘] 해시테이블

해시테이블 (Hash Table) 정리 및 자주 쓰이는 응용문제

1. 해시테이블이란?

해시테이블은 키(Key)를 해시 함수(Hash Function)를 통해 해시값으로 변환하여, 데이터(값, Value)를 빠르게 저장하고 조회하는 자료구조입니다.
평균적으로 O(1)의 시간 복잡도로 삽입, 삭제, 탐색이 가능해 매우 효율적입니다.
하지만, 서로 다른 키들이 같은 해시값을 가질 수 있는데, 이를 충돌(Collision)이라고 합니다.

2. 충돌 해결 방법 (Collision Resolution)

2-1. 체이닝 (Separate Chaining)

충돌이 발생한 인덱스에 연결 리스트(또는 다른 자료구조)를 두어, 충돌한 데이터를 모두 저장하는 방식입니다.

• 구현이 간단하며, 충돌이 많아도 성능 저하가 완화됨
• 메모리를 동적으로 사용할 수 있어 확장성이 좋음

# 파이썬 예시: 리스트를 이용한 체이닝
class HashTableChaining:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]

    def _hash(self, key):
        return hash(key) % self.size

    def set(self, key, value):
        index = self._hash(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        self.table[index].append((key, value))

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

2-2. 오픈 어드레싱 (Open Addressing)

충돌이 발생하면 해시 테이블 내에서 다른 빈 공간을 찾아 데이터를 저장하는 방식입니다.

• 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등의 기법이 있음
• 테이블이 꽉 차면 성능이 급격히 떨어지므로 적절한 크기 조절이 필요

# 파이썬 예시: 선형 탐사 방식 (Open Addressing - Linear Probing)
class HashTableOpenAddressing:
    def __init__(self, size=10):
        self.size = size
        self.keys = [None] * size
        self.values = [None] * size

    def _hash(self, key):
        return hash(key) % self.size

    def set(self, key, value):
        index = self._hash(key)
        start_index = index

        while self.keys[index] is not None and self.keys[index] != key:
            index = (index + 1) % self.size
            if index == start_index:
                raise Exception("Hash table is full")

        self.keys[index] = key
        self.values[index] = value

    def get(self, key):
        index = self._hash(key)
        start_index = index

        while self.keys[index] is not None:
            if self.keys[index] == key:
                return self.values[index]
            index = (index + 1) % self.size
            if index == start_index:
                break
        return None

3. 해시테이블 기본 구현 (체이닝 방식 예시)

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]

    def _hash(self, key):
        return hash(key) % self.size

    def set(self, key, value):
        index = self._hash(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        self.table[index].append((key, value))

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

    def delete(self, key):
        index = self._hash(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                del self.table[index][i]
                return True
        return False

4. 알고리즘에서 자주 쓰이는 해시테이블 응용 문제

4-1. 두 배열의 교집합 (Intersection of Two Arrays)

두 배열에서 공통으로 등장하는 원소를 찾는 문제입니다.

def intersection(nums1, nums2):
    set1 = set(nums1)
    result = []
    for num in nums2:
        if num in set1:
            result.append(num)
            set1.remove(num)
    return result

4-2. 해시맵을 이용한 두 수 합 문제 (Two Sum)

배열에서 합이 target이 되는 두 수의 인덱스를 찾는 문제입니다.

def two_sum(nums, target):
    hashmap = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hashmap:
            return [hashmap[complement], i]
        hashmap[num] = i
    return []

4-3. 아나그램 그룹핑 (Group Anagrams)

단어들을 아나그램끼리 그룹으로 묶는 문제입니다.

from collections import defaultdict

def group_anagrams(strs):
    hashmap = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))
        hashmap[key].append(s)
    return list(hashmap.values())

4-4. 해시셋으로 연속된 숫자 시퀀스 길이 구하기 (Longest Consecutive Sequence)

def longest_consecutive(nums):
    num_set = set(nums)
    longest = 0

    for num in num_set:
        if num - 1 not in num_set:  # 시작점 찾기
            length = 1
            while num + length in num_set:
                length += 1
            longest = max(longest, length)
    return longest

4-5. 해시맵으로 부분 배열 합 찾기 (Subarray Sum Equals K)

def subarray_sum(nums, k):
    count = 0
    prefix_sum = 0
    hashmap = {0: 1}

    for num in nums:
        prefix_sum += num
        if prefix_sum - k in hashmap:
            count += hashmap[prefix_sum - k]
        hashmap[prefix_sum] = hashmap.get(prefix_sum, 0) + 1
    return count

4-6. 해시맵으로 첫 번째 고유 문자 찾기 (First Unique Character in a String)

def first_unique_char(s):
    hashmap = {}
    for char in s:
        hashmap[char] = hashmap.get(char, 0) + 1

    for i, char in enumerate(s):
        if hashmap[char] == 1:
            return i
    return -1

5. 해시테이블 활용 시 주의사항

• 충돌 발생 시 적절한 충돌 해결 방법을 선택해야 한다.
• 해시 함수는 키를 균등하게 분포시키는 것이 중요하다.
• 메모리 사용량과 성능 사이에 적절한 균형이 필요하다.
• 파이썬의 기본 dict와 set은 내부적으로 해시테이블을 구현하고 있다.