해시 테이블(Hash Table)

해시 테이블(Hash Table)

1. 개념

해시 테이블은 키(key)를 값(value)에 매핑할 수 있는 구조인 연관 배열(associative array) 추상 자료형을 구현하는 자료구조입니다. 해시 테이블은 해시 함수를 사용하여 키를 배열의 인덱스로 변환하고, 이 인덱스를 사용하여 값을 저장하거나 검색합니다.

2. 핵심 구성 요소

2.1. 해시 함수(Hash Function)

• 정의: 임의의 크기를 가진 데이터를 고정된 크기의 값(해시 값)으로 변환하는 함수
• 특징:
  • 같은 입력에 대해 항상 같은 출력을 생성해야 함
  • 서로 다른 입력에 대해 다른 출력을 생성하는 것이 이상적임
  • 계산이 빠르고 효율적이어야 함
• 예시 해시 함수:

  def simple_hash(key, table_size):    return sum(ord(c) for c in str(key)) % table_size
  

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

키가 서로 다르지만 해시 함수가 동일한 인덱스를 반환하는 상황을 **충돌(collision)**이라고 합니다. 충돌을 해결하기 위한 주요 방법은 다음과 같습니다:

2.2.1. 체이닝(Chaining)

• 개념: 각 버킷에 연결 리스트를 사용하여 충돌이 발생한 항목들을 저장
• 장점: 구현이 간단하고, 테이블 크기에 제한이 없음
• 단점: 최악의 경우 O(n) 시간 복잡도를 가질 수 있음

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

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [None] * size
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def put(self, key, value):
        index = self._hash(key)
        if self.table[index] is None:
            self.table[index] = Node(key, value)
        else:
            current = self.table[index]
            while current:
                if current.key == key:
                    current.value = value
                    return
                if current.next is None:
                    break
                current = current.next
            current.next = Node(key, value)
    
    def get(self, key):
        index = self._hash(key)
        current = self.table[index]
        while current:
            if current.key == key:
                return current.value
            current = current.next
        return None

2.2.2. 개방 주소법(Open Addressing)

• 개념: 충돌이 발생하면 다른 빈 버킷을 찾아 항목을 저장
• 주요 방식:
  1. 선형 탐사(Linear Probing): 충돌 시 순차적으로 다음 버킷을 확인
  2. 이차 탐사(Quadratic Probing): 충돌 시 1, 4, 9, 16... 단위로 이동하여 확인
  3. 이중 해싱(Double Hashing): 두 번째 해시 함수를 사용하여 이동 폭을 결정

# 선형 탐사를 사용한 해시 테이블
class HashTable:
    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 put(self, key, value):
        index = self._hash(key)
        
        # 이미 키가 존재하는 경우
        if self.keys[index] == key:
            self.values[index] = value
            return
        
        # 빈 슬롯을 찾음
        while self.keys[index] is not None:
            index = (index + 1) % self.size
        
        self.keys[index] = key
        self.values[index] = value
    
    def get(self, key):
        index = self._hash(key)
        
        # 키를 찾거나 빈 슬롯을 만날 때까지 탐색
        while self.keys[index] is not None:
            if self.keys[index] == key:
                return self.values[index]
            index = (index + 1) % self.size
        
        return None

3. 해시 테이블의 성능

3.1. 시간 복잡도

연산	평균	최악
삽입	O(1)	O(n)
검색	O(1)	O(n)
삭제	O(1)	O(n)

3.2. 공간 복잡도

• O(n) - 저장된 항목 수에 비례

3.3. 로드 팩터(Load Factor)

• 정의: 해시 테이블에 저장된 항목 수를 테이블 크기로 나눈 값
• 의미: 해시 테이블이 얼마나 채워져 있는지를 나타냄
• 리해싱(Rehashing): 로드 팩터가 특정 임계값(일반적으로 0.7 또는 0.75)을 초과하면 테이블 크기를 늘리고 모든 항목을 다시 해싱하여 성능 저하를 방지

def rehash(self):
    old_size = self.size
    self.size = 2 * old_size
    old_keys = self.keys
    old_values = self.values
    
    self.keys = [None] * self.size
    self.values = [None] * self.size
    
    for i in range(old_size):
        if old_keys[i] is not None:
            self.put(old_keys[i], old_values[i])

4. 해시 함수 종류

4.1. 나눗셈 방식(Division Method)

• 방식: h(k) = k mod m (여기서 m은 테이블 크기)
• 특징: 구현이 간단하지만, m 값이 중요 (소수를 사용하는 것이 좋음)

4.2. 곱셈 방식(Multiplication Method)

• 방식: h(k) = ⌊m(kA mod 1)⌋ (여기서 A는 0과 1 사이의 상수, 보통 (√5-1)/2 ≈ 0.618 사용)
• 특징: 테이블 크기에 덜 민감함

4.3. 유니버설 해싱(Universal Hashing)

• 방식: 여러 해시 함수 집합에서 무작위로 함수를 선택
• 특징: 최악의 경우 성능을 보장할 수 있음

5. 파이썬에서의 해시 테이블

파이썬의 dict 자료형은 해시 테이블로 구현되어 있습니다.

# 딕셔너리 생성
my_dict = {}

# 삽입
my_dict["key1"] = "value1"
my_dict["key2"] = "value2"

# 검색
print(my_dict["key1"])  # 출력: value1

# 삭제
del my_dict["key1"]

# 키 존재 여부 확인
print("key1" in my_dict)  # 출력: False

6. 해시 테이블 응용

6.1. 캐싱(Caching)

• 계산 결과를 저장하여 중복 계산을 방지
• 예: 메모이제이션(Memoization), 웹 캐시

def fibonacci_with_cache(n, cache={}):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fibonacci_with_cache(n-1, cache) + fibonacci_with_cache(n-2, cache)
    return cache[n]

6.2. 데이터베이스 인덱싱

• 데이터 검색 속도 향상을 위해 사용

6.3. 중복 제거

• 집합(Set) 구현에 사용

# 리스트에서 중복 제거
unique_items = list(set([1, 2, 2, 3, 3, 3]))
print(unique_items)  # 출력: [1, 2, 3]

6.4. 블룸 필터(Bloom Filter)

• 요소가 집합에 포함되었는지 확인하는 공간 효율적인 확률적 자료구조

7. 주요 해시 알고리즘

7.1. MD5 (Message Digest Algorithm 5)

• 128비트 해시 값을 생성
• 암호학적으로 안전하지 않음

import hashlib

md5_hash = hashlib.md5("hello world".encode()).hexdigest()
print(md5_hash)  # 출력: 5eb63bbbe01eeed093cb22bb8f5acdc3

7.2. SHA-256 (Secure Hash Algorithm 256-bit)

• 256비트 해시 값을 생성
• 암호학적으로 안전함

import hashlib

sha256_hash = hashlib.sha256("hello world".encode()).hexdigest()
print(sha256_hash)  # 출력: b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9

8. 해시 테이블 구현 예제

8.1. 간단한 해시 테이블 구현

class SimpleHashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def insert(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
        raise KeyError(key)
    
    def remove(self, key):
        index = self._hash(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                del self.table[index][i]
                return
        raise KeyError(key)
    
    def __str__(self):
        items = []
        for bucket in self.table:
            for key, value in bucket:
                items.append(f"{key}: {value}")
        return "{" + ", ".join(items) + "}"

# 사용 예제
ht = SimpleHashTable()
ht.insert("apple", 5)
ht.insert("orange", 10)
ht.insert("banana", 15)
print(ht)  # 출력: {apple: 5, orange: 10, banana: 15}
print(ht.get("apple"))  # 출력: 5
ht.remove("apple")
print(ht)  # 출력: {orange: 10, banana: 15}

9. 해시 테이블 관련 문제

9.1. 두 수의 합 (Two Sum)

문제: 정수 배열과 타겟 값이 주어지면, 배열 내 두 수의 합이 타겟 값과 같은 두 수의 인덱스를 반환하세요.

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

# 예시
print(two_sum([2, 7, 11, 15], 9))  # 출력: [0, 1]

9.2. 중복 문자 없는 가장 긴 부분 문자열

문제: 문자열이 주어지면, 중복 문자가 없는 가장 긴 부분 문자열의 길이를 반환하세요.

def length_of_longest_substring(s):
    char_dict = {}
    max_length = start = 0
    
    for i, char in enumerate(s):
        if char in char_dict and start <= char_dict[char]:
            start = char_dict[char] + 1
        else:
            max_length = max(max_length, i - start + 1)
        
        char_dict[char] = i
    
    return max_length

# 예시
print(length_of_longest_substring("abcabcbb"))  # 출력: 3

10. 해시 테이블 성능 최적화

10.1. 해시 함수 선택

해시 테이블의 성능은 해시 함수의 질에 크게 의존합니다. 좋은 해시 함수는 다음과 같은 특성을 가져야 합니다:

• 균등 분포(Uniform Distribution): 키를 테이블 전체에 고르게 분포시킴
• 결정적(Deterministic): 같은 키는 항상 같은 해시 값을 생성
• 효율적(Efficient): 계산이 빠름
• 연속적(Avalanche Effect): 입력의 작은 변화가 출력에 큰 변화를 일으킴

10.2. 로드 팩터 관리

• 로드 팩터(α)는 테이블의 항목 수(n)를 버킷 수(m)로 나눈 값(α = n/m)
• 로드 팩터가 증가하면 충돌 확률이 높아져 성능이 저하됨
• 일반적으로 로드 팩터를 0.7 이하로 유지하는 것이 좋음
• 로드 팩터가 임계값을 초과하면 테이블 크기를 늘리고 재해싱을 수행

10.3. 충돌 해결 전략 최적화

체이닝(Chaining)의 경우:

• 연결 리스트 대신 균형 이진 검색 트리(예: AVL 트리, 레드-블랙 트리)를 사용하여 최악의 경우 시간 복잡도를 O(log n)으로 개선
• 연결 리스트에서 자주 액세스되는 항목을 앞쪽으로 이동시켜 평균 검색 시간 단축

개방 주소법(Open Addressing)의 경우:

• 선형 탐사보다 이차 탐사나 이중 해싱을 사용하여 클러스터링(clustering) 문제 완화
• 삭제 시 특별한 처리(지연 삭제 등)를 통해 검색 알고리즘의 정확성 유지

10.4. 테이블 크기 선택

• 소수(prime number)를 테이블 크기로 사용하면 충돌 가능성이 줄어듦
• 2의 거듭제곱보다는 소수를 사용하는 것이 더 효과적
• 재해싱 시 일반적으로 현재 크기의 2배 이상인 다음 소수로 크기 확장

11. 해시 테이블 변형 및 특수 용도

11.1. 카운팅 해시 테이블(Counting Hash Table)

• 키의 발생 빈도를 추적하는 데 사용
• 예: 문자열에서 각 문자의 빈도 계산

def count_characters(s):
    char_count = {}
    for char in s:
        if char in char_count:
            char_count[char] += 1
        else:
            char_count[char] = 1
    return char_count

# 예시
print(count_characters("hello"))  # 출력: {'h': 1, 'e': 1, 'l': 2, 'o': 1}

11.2. 양방향 해시 테이블(Bidirectional Hash Table)

• 키와 값 모두로 검색이 가능한 자료구조
• 예: 키-값 쌍과 값-키 쌍을 동시에 유지

class BidirectionalHashTable:
    def __init__(self):
        self.key_to_val = {}
        self.val_to_key = {}
    
    def insert(self, key, value):
        if key in self.key_to_val:
            old_value = self.key_to_val[key]
            del self.val_to_key[old_value]
        
        if value in self.val_to_key:
            old_key = self.val_to_key[value]
            del self.key_to_val[old_key]
        
        self.key_to_val[key] = value
        self.val_to_key[value] = key
    
    def get_value(self, key):
        return self.key_to_val.get(key)
    
    def get_key(self, value):
        return self.val_to_key.get(value)
    
    def remove(self, key=None, value=None):
        if key is not None:
            if key in self.key_to_val:
                val = self.key_to_val[key]
                del self.key_to_val[key]
                del self.val_to_key[val]
        elif value is not None:
            if value in self.val_to_key:
                key = self.val_to_key[value]
                del self.val_to_key[value]
                del self.key_to_val[key]

11.3. 일치 해시(Consistent Hashing)

• 분산 해시 테이블에서 노드 추가/제거 시 재해싱을 최소화하는 기법
• 웹 캐싱, 분산 데이터베이스 등에서 사용

import hashlib
import bisect

class ConsistentHash:
    def __init__(self, nodes=None, replicas=3):
        self.replicas = replicas
        self.ring = {}
        self.sorted_keys = []
        
        if nodes:
            for node in nodes:
                self.add_node(node)
    
    def add_node(self, node):
        for i in range(self.replicas):
            key = self._hash(f"{node}:{i}")
            self.ring[key] = node
            bisect.insort(self.sorted_keys, key)
    
    def remove_node(self, node):
        for i in range(self.replicas):
            key = self._hash(f"{node}:{i}")
            if key in self.ring:
                del self.ring[key]
                self.sorted_keys.remove(key)
    
    def get_node(self, key):
        if not self.ring:
            return None
        
        hash_key = self._hash(key)
        
        # 이진 검색으로 해시 키보다 크거나 같은 첫 번째 키 찾기
        idx = bisect.bisect_left(self.sorted_keys, hash_key) % len(self.sorted_keys)
        return self.ring[self.sorted_keys[idx]]
    
    def _hash(self, key):
        return int(hashlib.md5(str(key).encode()).hexdigest(), 16)

12. 실제 개발에서의 해시 테이블 활용

12.1. 캐싱 시스템

• 웹 서버에서 자주 요청되는 페이지나 데이터를 캐싱
• 데이터베이스 쿼리 결과 캐싱으로 성능 향상

class SimpleCache:
    def __init__(self, capacity=100):
        self.capacity = capacity
        self.cache = {}
    
    def get(self, key):
        if key in self.cache:
            return self.cache[key]
        return None
    
    def put(self, key, value):
        if len(self.cache) >= self.capacity:
            # 가장 오래된 항목 제거 (실제로는 LRU 같은 더 복잡한 전략 사용)
            self.cache.pop(next(iter(self.cache)))
        self.cache[key] = value

12.2. 데이터 중복 제거

• 대용량 데이터에서 중복 항목 제거
• 파일 시스템에서 중복 파일 식별

def deduplicate(items):
    seen = set()
    result = []
    
    for item in items:
        if item not in seen:
            seen.add(item)
            result.append(item)
    
    return result

12.3. 인메모리 데이터베이스

• 키-값 저장소 구현
• Redis, Memcached 등의 기본 구조

class InMemoryDB:
    def __init__(self):
        self.data = {}
    
    def set(self, key, value):
        self.data[key] = value
        return True
    
    def get(self, key):
        return self.data.get(key)
    
    def delete(self, key):
        if key in self.data:
            del self.data[key]
            return True
        return False
    
    def scan(self, pattern):
        # 간단한 구현을 위해 실제로는 패턴 매칭 대신 키 시작 부분 확인
        return [k for k in self.data if k.startswith(pattern)]

13. 해시 테이블 관련 고급 문제

13.1. LRU 캐시 구현

문제: 최근 가장 적게 사용된(Least Recently Used) 항목을 제거하는 캐시 구현

class LRUCache:
    class Node:
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.prev = None
            self.next = None
    
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> Node
        self.head = self.Node(0, 0)  # 더미 헤드
        self.tail = self.Node(0, 0)  # 더미 테일
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _add_node(self, node):
        # 항상 헤드 다음에 새 노드 추가
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def _remove_node(self, node):
        # 리스트에서 노드 제거
        prev = node.prev
        new = node.next
        prev.next = new
        new.prev = prev
    
    def _move_to_head(self, node):
        # 노드를 제거하고 헤드로 이동
        self._remove_node(node)
        self._add_node(node)
    
    def _pop_tail(self):
        # 테일 노드 제거 및 반환
        res = self.tail.prev
        self._remove_node(res)
        return res
    
    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            self._move_to_head(node)
            return node.value
        return -1
    
    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)
        else:
            node = self.Node(key, value)
            self.cache[key] = node
            self._add_node(node)
            
            if len(self.cache) > self.capacity:
                tail = self._pop_tail()
                del self.cache[tail.key]

13.2. 그룹 애너그램(Group Anagrams)

문제: 문자열 배열이 주어졌을 때, 애너그램끼리 그룹화하세요.

def group_anagrams(strs):
    groups = {}
    for s in strs:
        # 정렬된 문자열을 키로 사용
        key = ''.join(sorted(s))
        if key in groups:
            groups[key].append(s)
        else:
            groups[key] = [s]
    
    return list(groups.values())

# 예시
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
# 출력: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

14. 결론

해시 테이블은 평균적으로 O(1) 시간 복잡도로 데이터를 삽입, 검색, 삭제할 수 있는 강력한 자료구조입니다. 적절한 해시 함수와 충돌 해결 전략을 선택하면 대부분의 실제 애플리케이션에서 효율적으로 동작합니다. 파이썬의 딕셔너리와 집합은 해시 테이블을 기반으로 구현되어 있어, 많은 알고리즘 문제를 효율적으로 해결하는 데 도움이 됩니다.

효과적인 해시 테이블 사용을 위해서는 다음 사항을 고려해야 합니다:

1. 문제에 적합한 해시 함수 선택
2. 적절한 충돌 해결 전략 구현
3. 로드 팩터 관리 및 재해싱 시점 결정
4. 키-값 쌍의 특성을 고려한 메모리 효율성 최적화

해시 테이블은 캐싱, 데이터베이스 인덱싱, 중복 제거 등 다양한 실제 애플리케이션에서 널리 사용되는 기본적이면서도 강력한 자료구조입니다.