해시 테이블 | O(1) 탐색 자료구조 완벽 정리

· 20분 읽기 · 수정 중급 튜토리얼
해시 테이블 | O(1) 탐색 자료구조 완벽 정리

이 글의 핵심

해시 테이블에 대한 실전 가이드입니다. O(1) 탐색 자료구조 완벽 정리 등을 예제와 함께 상세히 설명합니다.

들어가며

해시 테이블이란?

해시 테이블(Hash Table)은 키(Key)-값(Value) 쌍을 저장하는 자료구조로, 평균 O(1)의 시간복잡도(입력이 커질 때 걸리는 시간이 얼마나 늘어나는지)로 검색/삽입/삭제가 가능합니다. 여기서 O(1)은 입력 크기와 거의 무관하게 일정한 시간에 가깝다는 뜻입니다.

다른 이름:

  • Hash Map
  • Dictionary (Python)
  • Associative Array
  • Map (C++, Java)

왜 빠른가?

배열은 인덱스로 O(1) 접근이 가능합니다. 해시 테이블은 해시 함수(키를 고정 길이의 숫자·슬롯 번호로 바꾸는 함수)로 키를 인덱스로 변환하여 배열처럼 빠르게 접근합니다.

# 배열: 인덱스로 접근
arr = [10, 20, 30, 40, 50]
print(arr[2])  # 30 (O(1))

# 해시 테이블: 키로 접근
hash_table = {"apple": 100, "banana": 200}
print(hash_table["apple"])  # 100 (O(1))
# 내부적으로: hash("apple") % size → 인덱스 → 값

시간 복잡도 비교:

자료구조검색삽입삭제
배열 (정렬 안 됨)O(n)O(1)O(n)
배열 (정렬됨)O(log n)O(n)O(n)
연결 리스트O(n)O(1)O(n)
해시 테이블O(1)O(1)O(1)

1. 해시 함수 (Hash Function)

해시 함수란?

해시 함수는 임의 크기의 데이터를 고정 크기의 값(해시값)으로 변환하는 함수입니다.

좋은 해시 함수의 조건:

  1. ✅ 결정적: 같은 입력 → 같은 출력
  2. ✅ 빠른 계산: O(1)
  3. ✅ 균등 분포: 해시값이 골고루 분산
  4. ✅ 충돌 최소화: 다른 입력 → 다른 출력 (이상적)

간단한 해시 함수 예제

해시 함수는 키를 받아 고정된 크기의 슬롯 번호(배열 인덱스)로 바꿉니다. 우편번호로 구역을 나누듯, “이 키는 몇 번 칸에 넣는다”를 한 번에 정해 주는 역할입니다. 같은 키는 항상 같은 칸으로 가야 하므로(결정적) 검색 시에도 같은 인덱스로 찾아갈 수 있습니다.

# 방법 1: Python 내장 hash() + 나머지 연산
def simple_hash(key, size):
    # hash(key): Python 내장 해시 함수
    #   - 문자열, 숫자, 튜플 등에 대해 정수 해시값 반환
    #   - 같은 값은 항상 같은 해시값 (결정적)
    # % size: 배열 크기로 나눈 나머지 (0 ~ size-1)
    #   - 해시값을 배열 인덱스 범위로 변환
    return hash(key) % size

print(simple_hash("apple", 10))   # 8 (인덱스 8에 저장)
print(simple_hash("banana", 10))  # 3 (인덱스 3에 저장)
print(simple_hash("cherry", 10))  # 6 (인덱스 6에 저장)

# 방법 2: 문자열 해시 (직접 구현)
def string_hash(s, size):
    hash_value = 0
    for char in s:
        # ord(char): 문자의 ASCII/유니코드 값
        # 31: 소수(prime number) 사용 (충돌 감소)
        # 각 문자를 31배씩 누적하여 해시값 계산
        hash_value = (hash_value * 31 + ord(char)) % size
    return hash_value

# 예: "abc"의 해시 계산 과정
# 1. hash_value = 0
# 2. 'a': (0 * 31 + 97) % 10 = 97 % 10 = 7
# 3. 'b': (7 * 31 + 98) % 10 = 315 % 10 = 5
# 4. 'c': (5 * 31 + 99) % 10 = 254 % 10 = 4
# 결과: 4

print(string_hash("apple", 10))  # 특정 값

# Python 내장 hash() 함수
print(hash("apple"))   # -6076896708304529682 (예시)
# 실행마다 다를 수 있음 (Python 3.3+는 보안상 랜덤 시드 사용)

print(hash(42))        # 42 (정수는 자기 자신)
print(hash((1, 2)))    # 3713081631934410656 (튜플 해시)

# ❌ 가변 객체는 해시 불가
# print(hash([1, 2]))  # TypeError: unhashable type: 'list'
# 이유: 리스트는 내용이 변할 수 있어 해시값이 달라질 수 있음
# dict의 키는 불변(immutable) 타입만 가능

해시 함수의 역할:

# 해시 테이블 내부 동작 (개념적)
class SimpleHashTable:
    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)  # 해시 함수로 인덱스 계산
        self.table[index] = value  # 배열에 저장
    
    def get(self, key):
        index = self._hash(key)  # 같은 해시 함수로 인덱스 계산
        return self.table[index]  # O(1) 접근

# 사용
ht = SimpleHashTable()
ht.put("apple", 100)   # hash("apple") % 10 = 8 → table[8] = 100
ht.put("banana", 200)  # hash("banana") % 10 = 3 → table[3] = 200
print(ht.get("apple"))  # table[8] 접근 → 100

해시 충돌 (Hash Collision)

충돌은 서로 다른 키가 같은 해시값을 가질 때 발생합니다.

# 충돌 예시
def bad_hash(key, size):
    return len(key) % size  # 길이만 사용 (나쁜 해시 함수)

print(bad_hash("apple", 10))   # 5
print(bad_hash("grape", 10))   # 5 (충돌!)
print(bad_hash("peach", 10))   # 5 (충돌!)

2. Python dict 사용법

언어 차원에서 dict·set 문법과 함께 다루려면 Python 자료형 (리스트, 딕셔너리, 튜플, 세트)를 참고하면 좋습니다.

기본 연산

# 생성
hash_table = {}
hash_table = dict()

# 삽입 O(1)
hash_table["apple"] = 100
hash_table["banana"] = 200
hash_table["cherry"] = 300

# 검색 O(1)
print(hash_table["apple"])  # 100
print(hash_table.get("grape", 0))  # 0 (기본값)

# 수정 O(1)
hash_table["apple"] = 150
print(hash_table["apple"])  # 150

# 삭제 O(1)
del hash_table["apple"]
print("apple" in hash_table)  # False

# 존재 확인 O(1)
if "banana" in hash_table:
    print("있음")

# 순회 O(n)
for key in hash_table:
    print(key, hash_table[key])

for key, value in hash_table.items():
    print(f"{key}: {value}")

# 키/값 리스트
keys = list(hash_table.keys())
values = list(hash_table.values())
print(keys)    # ['banana', 'cherry']
print(values)  # [200, 300]

dict 고급 기능

# setdefault(): 키가 없을 때만 추가
hash_table = {"a": 1}
hash_table.setdefault("b", 2)  # 추가
hash_table.setdefault("a", 100)  # 이미 있으므로 무시
print(hash_table)  # {'a': 1, 'b': 2}

# update(): 병합
hash_table.update({"c": 3, "d": 4})
print(hash_table)  # {'a': 1, 'b': 2, 'c': 3, 'd': 4}

# pop(): 제거 및 반환
value = hash_table.pop("a")
print(value)  # 1
print(hash_table)  # {'b': 2, 'c': 3, 'd': 4}

# popitem(): 마지막 키-값 제거 (Python 3.7+)
last = hash_table.popitem()
print(last)  # ('d', 4)

# clear(): 전체 삭제
hash_table.clear()
print(hash_table)  # {}

3. 해시 충돌 해결 방법

충돌이란?

서로 다른 키가 같은 해시값(인덱스)을 가질 때 충돌(Collision)이 발생합니다.

# 충돌 시뮬레이션
def hash_func(key, size):
    return sum(ord(c) for c in key) % size

# 크기 10인 테이블
size = 10
print(hash_func("abc", size))  # 4
print(hash_func("bca", size))  # 4 (충돌!)
print(hash_func("cab", size))  # 4 (충돌!)

방법 1: Chaining (체이닝)

연결 리스트로 같은 인덱스의 값들을 저장합니다.

시각화:

Index 0: []
Index 1: []
Index 2: [("apple", 100), ("grape", 150)]  ← 충돌 발생
Index 3: [("banana", 200)]
Index 4: []
...

구현:

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 insert(self, key, value):
        idx = self._hash(key)
        
        # 기존 키가 있으면 업데이트
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)
                return
        
        # 없으면 추가
        self.table[idx].append((key, value))
    
    def get(self, key):
        idx = self._hash(key)
        
        # 연결 리스트 순회
        for k, v in self.table[idx]:
            if k == key:
                return v
        
        return None
    
    def delete(self, key):
        idx = self._hash(key)
        
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                del self.table[idx][i]
                return True
        
        return False
    
    def __str__(self):
        result = []
        for i, bucket in enumerate(self.table):
            if bucket:
                result.append(f"Index {i}: {bucket}")
        return "\n".join(result) if result else "Empty"

# 테스트
ht = HashTableChaining(size=5)
ht.insert("apple", 100)
ht.insert("banana", 200)
ht.insert("cherry", 300)
ht.insert("grape", 150)  # 충돌 가능

print(ht)
print(f"\napple: {ht.get('apple')}")  # 100
print(f"banana: {ht.get('banana')}")  # 200

ht.delete("apple")
print(f"\napple 삭제 후: {ht.get('apple')}")  # None

Chaining 시간 복잡도:

  • 평균: O(1) (충돌이 적을 때)
  • 최악: O(n) (모든 키가 같은 인덱스에 충돌)

방법 2: Open Addressing (개방 주소법)

충돌 시 다른 빈 공간을 찾습니다.

2-1. Linear Probing (선형 탐사)

충돌 시 다음 인덱스를 순차적으로 탐색합니다.

class HashTableLinearProbing:
    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 insert(self, key, value):
        idx = self._hash(key)
        
        # 빈 공간 찾기
        while self.keys[idx] is not None:
            if self.keys[idx] == key:  # 기존 키 업데이트
                self.values[idx] = value
                return
            idx = (idx + 1) % self.size  # 다음 인덱스
        
        self.keys[idx] = key
        self.values[idx] = value
    
    def get(self, key):
        idx = self._hash(key)
        
        # 키 찾기
        while self.keys[idx] is not None:
            if self.keys[idx] == key:
                return self.values[idx]
            idx = (idx + 1) % self.size
        
        return None
    
    def delete(self, key):
        idx = self._hash(key)
        
        while self.keys[idx] is not None:
            if self.keys[idx] == key:
                self.keys[idx] = None
                self.values[idx] = None
                return True
            idx = (idx + 1) % self.size
        
        return False
    
    def __str__(self):
        result = []
        for i in range(self.size):
            if self.keys[i] is not None:
                result.append(f"[{i}] {self.keys[i]}: {self.values[i]}")
        return "\n".join(result) if result else "Empty"

# 테스트
ht = HashTableLinearProbing(size=5)
ht.insert("apple", 100)
ht.insert("banana", 200)
ht.insert("cherry", 300)

print(ht)
print(f"\napple: {ht.get('apple')}")  # 100

Linear Probing 문제점:

  • 클러스터링(Clustering): 연속된 공간이 채워지면 탐색 시간 증가

2-2. Quadratic Probing (이차 탐사)

충돌 시 제곱수만큼 이동합니다 (1, 4, 9, 16, …).

def _probe_quadratic(self, key, i):
    """i번째 충돌 시 이동할 인덱스"""
    return (hash(key) + i * i) % self.size

2-3. Double Hashing (이중 해싱)

두 번째 해시 함수를 사용하여 이동 간격을 결정합니다.

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

def _hash2(self, key):
    return 7 - (hash(key) % 7)  # 7은 소수

def _probe_double(self, key, i):
    return (self._hash1(key) + i * self._hash2(key)) % self.size

Chaining vs Open Addressing 비교

특징ChainingOpen Addressing
충돌 해결연결 리스트다른 빈 공간
메모리추가 메모리 (포인터)고정 크기 배열
캐시 효율낮음높음
삭제쉬움복잡 (재배치 필요)
부하율> 1 가능< 1 필수
사용Python dictJava HashMap

부하율(Load Factor) = 저장된 항목 수 / 테이블 크기

  • Chaining: 1.0 이상 가능
  • Open Addressing: 0.7 이하 권장

4. 실전 문제 풀이

문제 1: 두 수의 합 (Two Sum)

문제: 배열에서 합이 target인 두 수의 인덱스를 반환하세요.

def two_sum(arr, target):
    """
    합이 target인 두 수의 인덱스
    [2, 7, 11, 15], target=9 → [0, 1]
    
    시간: O(n), 공간: O(n)
    """
    seen = {}  # 값: 인덱스
    
    for i, num in enumerate(arr):
        complement = target - num
        
        if complement in seen:
            return [seen[complement], i]
        
        seen[num] = i
    
    return []

# 테스트
arr = [2, 7, 11, 15]
print(two_sum(arr, 9))  # [0, 1]
print(two_sum(arr, 13))  # [0, 2]
print(two_sum(arr, 100))  # []

동작 과정:

arr = [2, 7, 11, 15], target = 9

i=0, num=2:
  complement = 9 - 2 = 7
  7 not in seen
  seen = {2: 0}

i=1, num=7:
  complement = 9 - 7 = 2
  2 in seen! → return [0, 1]

왜 해시 테이블?

  • 브루트포스: O(n²) - 모든 쌍 확인
  • 해시 테이블: O(n) - 한 번만 순회

문제 2: 완주하지 못한 선수 (프로그래머스)

문제: 마라톤에 참가한 선수 중 완주하지 못한 선수 1명을 찾으세요. (동명이인 가능)

def solution(participant, completion):
    """
    완주하지 못한 선수 1명 찾기
    시간: O(n), 공간: O(n)
    """
    hash_table = {}
    
    # 참가자 카운트
    for name in participant:
        hash_table[name] = hash_table.get(name, 0) + 1
    
    # 완주자 감소
    for name in completion:
        hash_table[name] -= 1
    
    # 카운트가 1인 사람 찾기
    for name, count in hash_table.items():
        if count == 1:
            return name

# 테스트
participant = ["leo", "kiki", "eden"]
completion = ["eden", "kiki"]
print(solution(participant, completion))  # "leo"

# 동명이인 케이스
participant = ["marina", "josipa", "nikola", "vinko", "marina"]
completion = ["josipa", "nikola", "marina", "marina"]
print(solution(participant, completion))  # "vinko"

동작 과정:

participant = ["leo", "kiki", "eden"]
completion = ["eden", "kiki"]

1단계: 참가자 카운트
  hash_table = {"leo": 1, "kiki": 1, "eden": 1}

2단계: 완주자 감소
  "eden" → hash_table = {"leo": 1, "kiki": 1, "eden": 0}
  "kiki" → hash_table = {"leo": 1, "kiki": 0, "eden": 0}

3단계: 카운트 1인 사람
  "leo" → return "leo"

다른 풀이: Counter 사용:

from collections import Counter

def solution(participant, completion):
    counter = Counter(participant) - Counter(completion)
    return list(counter.keys())[0]

# 테스트
print(solution(["leo", "kiki", "eden"], ["eden", "kiki"]))  # "leo"

문제 3: 베스트앨범 (프로그래머스)

문제: 장르별로 가장 많이 재생된 노래를 2개씩 선택하세요.

조건:

  1. 장르별 총 재생 횟수가 많은 순서대로
  2. 장르 내에서 재생 횟수가 많은 순서대로
  3. 재생 횟수가 같으면 고유 번호가 낮은 순서대로
def solution(genres, plays):
    """
    장르별 재생 횟수 많은 노래 2개씩
    시간: O(n log n), 공간: O(n)
    """
    genre_play = {}  # 장르: 총 재생 횟수
    genre_songs = {}  # 장르: [(재생, 인덱스), ...]
    
    # 1단계: 데이터 수집
    for i, (genre, play) in enumerate(zip(genres, plays)):
        genre_play[genre] = genre_play.get(genre, 0) + play
        
        if genre not in genre_songs:
            genre_songs[genre] = []
        genre_songs[genre].append((play, i))
    
    # 2단계: 장르를 총 재생 횟수 내림차순 정렬
    sorted_genres = sorted(genre_play.items(), key=lambda x: x[1], reverse=True)
    
    result = []
    # 3단계: 각 장르에서 상위 2곡 선택
    for genre, _ in sorted_genres:
        # 재생 횟수 내림차순, 인덱스 오름차순
        songs = sorted(genre_songs[genre], key=lambda x: (-x[0], x[1]))
        result.extend([idx for _, idx in songs[:2]])  # 최대 2곡
    
    return result

# 테스트
genres = ["classic", "pop", "classic", "classic", "pop"]
plays = [500, 600, 150, 800, 2500]
print(solution(genres, plays))  # [4, 1, 3, 0]

동작 과정:

genres = ["classic", "pop", "classic", "classic", "pop"]
plays =  [500,       600,   150,       800,       2500]
index =  [0,         1,     2,         3,         4]

1단계: 데이터 수집
  genre_play = {"classic": 1450, "pop": 3100}
  genre_songs = {
    "classic": [(500, 0), (150, 2), (800, 3)],
    "pop": [(600, 1), (2500, 4)]
  }

2단계: 장르 정렬 (총 재생 횟수 내림차순)
  sorted_genres = [("pop", 3100), ("classic", 1450)]

3단계: 각 장르에서 상위 2곡
  pop: [(2500, 4), (600, 1)] → 인덱스 [4, 1]
  classic: [(800, 3), (500, 0), (150, 2)] → 인덱스 [3, 0]

결과: [4, 1, 3, 0]

defaultdict 버전:

from collections import defaultdict

def solution(genres, plays):
    genre_play = defaultdict(int)
    genre_songs = defaultdict(list)
    
    for i, (genre, play) in enumerate(zip(genres, plays)):
        genre_play[genre] += play
        genre_songs[genre].append((play, i))
    
    sorted_genres = sorted(genre_play.items(), key=lambda x: x[1], reverse=True)
    
    result = []
    for genre, _ in sorted_genres:
        songs = sorted(genre_songs[genre], key=lambda x: (-x[0], x[1]))
        result.extend([idx for _, idx in songs[:2]])
    
    return result

문제 4: 그룹 애너그램 (Group Anagrams)

문제: 애너그램끼리 그룹화하세요.

def group_anagrams(strs):
    """
    애너그램 그룹화
    ["eat", "tea", "tan", "ate", "nat", "bat"]
    → [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
    
    시간: O(n * k log k), 공간: O(n * k)
    n = 문자열 개수, k = 문자열 평균 길이
    """
    anagrams = {}
    
    for word in strs:
        # 정렬된 문자열을 키로 사용
        key = ''.join(sorted(word))
        
        if key not in anagrams:
            anagrams[key] = []
        anagrams[key].append(word)
    
    return list(anagrams.values())

# 테스트
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(strs))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

동작 과정:

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

"eat" → sorted: "aet" → anagrams = {"aet": ["eat"]}
"tea" → sorted: "aet" → anagrams = {"aet": ["eat", "tea"]}
"tan" → sorted: "ant" → anagrams = {"aet": ["eat", "tea"], "ant": ["tan"]}
"ate" → sorted: "aet" → anagrams = {"aet": ["eat", "tea", "ate"], "ant": ["tan"]}
"nat" → sorted: "ant" → anagrams = {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}
"bat" → sorted: "abt" → anagrams = {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]}

결과: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

defaultdict 버전:

from collections import defaultdict

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

문제 5: 중복 문자 없는 가장 긴 부분 문자열

문제: 중복 문자가 없는 가장 긴 부분 문자열의 길이를 구하세요.

def length_of_longest_substring(s):
    """
    "abcabcbb" → 3 ("abc")
    "bbbbb" → 1 ("b")
    "pwwkew" → 3 ("wke")
    
    시간: O(n), 공간: O(min(n, m)) (m = 문자 종류)
    """
    char_index = {}  # 문자: 마지막 인덱스
    max_length = 0
    start = 0
    
    for i, char in enumerate(s):
        # 중복 문자 발견 시 시작점 이동
        if char in char_index and char_index[char] >= start:
            start = char_index[char] + 1
        
        char_index[char] = i
        max_length = max(max_length, i - start + 1)
    
    return max_length

# 테스트
print(length_of_longest_substring("abcabcbb"))  # 3
print(length_of_longest_substring("bbbbb"))     # 1
print(length_of_longest_substring("pwwkew"))    # 3
print(length_of_longest_substring(""))          # 0

동작 과정:

s = "abcabcbb"

i=0, char='a': char_index={'a': 0}, start=0, max_length=1
i=1, char='b': char_index={'a': 0, 'b': 1}, start=0, max_length=2
i=2, char='c': char_index={'a': 0, 'b': 1, 'c': 2}, start=0, max_length=3
i=3, char='a': 중복! start=1, char_index={'a': 3, 'b': 1, 'c': 2}, max_length=3
i=4, char='b': 중복! start=2, char_index={'a': 3, 'b': 4, 'c': 2}, max_length=3
i=5, char='c': 중복! start=3, char_index={'a': 3, 'b': 4, 'c': 5}, max_length=3
i=6, char='b': 중복! start=5, char_index={'a': 3, 'b': 6, 'c': 5}, max_length=3
i=7, char='b': 중복! start=7, char_index={'a': 3, 'b': 7, 'c': 5}, max_length=3

결과: 3

5. Python collections 모듈

Counter 상세

from collections import Counter

# 생성
counter = Counter([1, 2, 2, 3, 3, 3])
print(counter)  # Counter({3: 3, 2: 2, 1: 1})

# 문자열 카운트
text = "hello world"
counter = Counter(text)
print(counter)  # Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ' ': 1, 'w': 1, 'r': 1, 'd': 1})

# most_common(): 가장 빈번한 요소
print(counter.most_common(3))  # [('l', 3), ('o', 2), ('h', 1)]

# 연산
c1 = Counter(['a', 'b', 'c', 'a'])
c2 = Counter(['a', 'b', 'b'])

print(c1 + c2)  # Counter({'a': 3, 'b': 3, 'c': 1})
print(c1 - c2)  # Counter({'a': 1, 'c': 1})
print(c1 & c2)  # Counter({'a': 1, 'b': 1}) (교집합, 최소값)
print(c1 | c2)  # Counter({'a': 2, 'b': 2, 'c': 1}) (합집합, 최대값)

# elements(): 요소 반복
c = Counter(a=3, b=1)
print(list(c.elements()))  # ['a', 'a', 'a', 'b']

defaultdict 상세

from collections import defaultdict

# int 기본값 (0)
word_count = defaultdict(int)
for word in ["apple", "banana", "apple"]:
    word_count[word] += 1
print(dict(word_count))  # {'apple': 2, 'banana': 1}

# list 기본값 ([])
groups = defaultdict(list)
for name, grade in [("Alice", "A"), ("Bob", "B"), ("Charlie", "A")]:
    groups[grade].append(name)
print(dict(groups))  # {'A': ['Alice', 'Charlie'], 'B': ['Bob']}

# set 기본값 (set())
tags = defaultdict(set)
tags["python"].add("programming")
tags["python"].add("tutorial")
print(dict(tags))  # {'python': {'programming', 'tutorial'}}

# lambda 기본값
counter = defaultdict(lambda: 0)
counter["a"] += 1
print(dict(counter))  # {'a': 1}

OrderedDict (순서 유지)

from collections import OrderedDict

# Python 3.7+ 이전에는 dict가 순서를 보장하지 않았음
# 현재는 dict도 순서 유지, OrderedDict는 추가 기능 제공

od = OrderedDict()
od["a"] = 1
od["b"] = 2
od["c"] = 3

# move_to_end(): 요소를 끝으로 이동
od.move_to_end("a")
print(list(od.keys()))  # ['b', 'c', 'a']

# popitem(last=True): 마지막 요소 제거
od.popitem(last=True)
print(list(od.keys()))  # ['b', 'c']

# popitem(last=False): 첫 요소 제거
od.popitem(last=False)
print(list(od.keys()))  # ['c']

LRU Cache 구현 (OrderedDict 활용)

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity
    
    def get(self, key):
        if key not in self.cache:
            return -1
        
        # 최근 사용으로 이동
        self.cache.move_to_end(key)
        return self.cache[key]
    
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        
        self.cache[key] = value
        
        # 용량 초과 시 가장 오래된 항목 제거
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)
    
    def __str__(self):
        return str(dict(self.cache))

# 테스트
cache = LRUCache(3)
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3)
print(cache)  # {'a': 1, 'b': 2, 'c': 3}

cache.get("a")  # 'a' 사용
cache.put("d", 4)  # 용량 초과, 'b' 제거
print(cache)  # {'c': 3, 'a': 1, 'd': 4}

6. 해시 테이블 실전 활용 패턴

패턴 1: 빈도수 세기

# 문자 빈도
def char_frequency(s):
    freq = {}
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    return freq

print(char_frequency("hello"))  # {'h': 1, 'e': 1, 'l': 2, 'o': 1}

# Counter 사용
from collections import Counter
print(dict(Counter("hello")))  # {'h': 1, 'e': 1, 'l': 2, 'o': 1}

패턴 2: 그룹화

# 길이별 그룹화
words = ["apple", "pie", "banana", "cat", "dog", "cherry"]

groups = {}
for word in words:
    length = len(word)
    if length not in groups:
        groups[length] = []
    groups[length].append(word)

print(groups)
# {5: ['apple'], 3: ['pie', 'cat', 'dog'], 6: ['banana', 'cherry']}

# defaultdict 사용
from collections import defaultdict
groups = defaultdict(list)
for word in words:
    groups[len(word)].append(word)
print(dict(groups))

패턴 3: 캐싱 (Memoization)

# 피보나치 (캐싱 없음) - 느림
def fib_slow(n):
    if n <= 1:
        return n
    return fib_slow(n-1) + fib_slow(n-2)

# 피보나치 (캐싱) - 빠름
def fib_fast(n, cache={}):
    if n in cache:
        return cache[n]
    
    if n <= 1:
        return n
    
    cache[n] = fib_fast(n-1, cache) + fib_fast(n-2, cache)
    return cache[n]

# 테스트
print(fib_fast(30))  # 832040 (빠름)
# print(fib_slow(30))  # 832040 (매우 느림)

# functools.lru_cache 사용 (권장)
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

print(fib(30))  # 832040 (매우 빠름)

패턴 4: 인덱스 매핑

# 배열 요소의 인덱스 저장
def find_indices(arr, target):
    """target 값의 모든 인덱스 찾기"""
    index_map = {}
    
    for i, num in enumerate(arr):
        if num not in index_map:
            index_map[num] = []
        index_map[num].append(i)
    
    return index_map.get(target, [])

arr = [1, 2, 3, 2, 4, 2, 5]
print(find_indices(arr, 2))  # [1, 3, 5]

패턴 5: 집합 연산

# 두 배열의 교집합
def intersection(arr1, arr2):
    """
    [1, 2, 2, 1], [2, 2] → [2, 2]
    시간: O(n + m), 공간: O(min(n, m))
    """
    count1 = Counter(arr1)
    result = []
    
    for num in arr2:
        if count1[num] > 0:
            result.append(num)
            count1[num] -= 1
    
    return result

print(intersection([1, 2, 2, 1], [2, 2]))  # [2, 2]

# Counter 사용
from collections import Counter
def intersection(arr1, arr2):
    c1 = Counter(arr1)
    c2 = Counter(arr2)
    common = c1 & c2  # 교집합
    
    result = []
    for num, count in common.items():
        result.extend([num] * count)
    return result

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

부하율 (Load Factor) 관리

class DynamicHashTable:
    def __init__(self, initial_size=8):
        self.size = initial_size
        self.count = 0
        self.table = [[] for _ in range(self.size)]
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def _load_factor(self):
        return self.count / self.size
    
    def _resize(self):
        """부하율이 0.7 초과 시 크기 2배 증가"""
        old_table = self.table
        self.size *= 2
        self.table = [[] for _ in range(self.size)]
        self.count = 0
        
        # 모든 항목 재삽입
        for bucket in old_table:
            for key, value in bucket:
                self.insert(key, value)
    
    def insert(self, key, value):
        # 부하율 체크
        if self._load_factor() > 0.7:
            self._resize()
        
        idx = self._hash(key)
        
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)
                return
        
        self.table[idx].append((key, value))
        self.count += 1
    
    def get(self, key):
        idx = self._hash(key)
        for k, v in self.table[idx]:
            if k == key:
                return v
        return None

# 테스트
ht = DynamicHashTable(initial_size=4)
for i in range(10):
    ht.insert(f"key{i}", i)
    print(f"삽입 후 크기: {ht.size}, 부하율: {ht._load_factor():.2f}")

해시 함수 선택

# 좋은 해시 함수 예제
def good_hash(s, size):
    """문자열 해시 (균등 분포)"""
    hash_value = 0
    prime = 31  # 소수 사용
    
    for char in s:
        hash_value = (hash_value * prime + ord(char)) % size
    
    return hash_value

# 나쁜 해시 함수 예제
def bad_hash(s, size):
    """길이만 사용 (충돌 많음)"""
    return len(s) % size

# 비교
words = ["apple", "grape", "peach", "melon", "berry"]
size = 10

print("좋은 해시 함수:")
for word in words:
    print(f"{word}: {good_hash(word, size)}")

print("\n나쁜 해시 함수:")
for word in words:
    print(f"{word}: {bad_hash(word, size)}")

8. 자주 하는 실수와 해결법

실수 1: 가변 객체를 키로 사용

# ❌ 잘못된 방법
# hash_table = {[1, 2]: "value"}  # TypeError: unhashable type: 'list'

# ✅ 올바른 방법
hash_table = {(1, 2): "value"}  # 튜플 사용
print(hash_table[(1, 2)])  # value

실수 2: KeyError 처리 누락

# ❌ 잘못된 방법
hash_table = {"a": 1}
# print(hash_table["b"])  # KeyError: 'b'

# ✅ 올바른 방법 1: get() 사용
value = hash_table.get("b", 0)
print(value)  # 0

# ✅ 올바른 방법 2: in 체크
if "b" in hash_table:
    print(hash_table["b"])
else:
    print("키가 없습니다")

실수 3: 순회 중 수정

# ❌ 잘못된 방법
hash_table = {"a": 1, "b": 2, "c": 3}
# for key in hash_table:
#     if hash_table[key] == 2:
#         del hash_table[key]  # RuntimeError: dictionary changed size during iteration

# ✅ 올바른 방법 1: 리스트로 변환
hash_table = {"a": 1, "b": 2, "c": 3}
for key in list(hash_table.keys()):
    if hash_table[key] == 2:
        del hash_table[key]
print(hash_table)  # {'a': 1, 'c': 3}

# ✅ 올바른 방법 2: 딕셔너리 컴프리헨션
hash_table = {"a": 1, "b": 2, "c": 3}
hash_table = {k: v for k, v in hash_table.items() if v != 2}
print(hash_table)  # {'a': 1, 'c': 3}

9. 실전 팁

코딩 테스트 해시 테이블 사용 시점

# ✅ 해시 테이블 사용
# - 빠른 검색 (O(1))
# - 빈도수 세기
# - 중복 확인
# - 그룹화
# - 캐싱

# ❌ 해시 테이블 부적합
# - 순서가 중요 (정렬된 순서) → 이진 탐색 트리
# - 범위 검색 (k1 ≤ key ≤ k2) → 이진 탐색 트리
# - 최소/최대값 빠른 접근 → 힙(Heap)

시간 복잡도 개선 패턴

# Before: O(n²) - 중첩 루프
def has_duplicate_slow(arr):
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

# After: O(n) - 해시 테이블
def has_duplicate_fast(arr):
    seen = set()
    for num in arr:
        if num in seen:
            return True
        seen.add(num)
    return False

# 또는 더 간단하게
def has_duplicate(arr):
    return len(arr) != len(set(arr))

정리

핵심 요약

  1. 해시 테이블: 키-값 저장, 평균 O(1) 검색/삽입/삭제
  2. 해시 함수: 키를 인덱스로 변환, 균등 분포 중요
  3. 충돌 해결:
    • Chaining: 연결 리스트로 저장
    • Open Addressing: 다른 빈 공간 찾기 (Linear/Quadratic/Double Hashing)
  4. Python 도구:
    • dict: 기본 해시 테이블
    • Counter: 빈도수 세기
    • defaultdict: 기본값 자동 생성
    • OrderedDict: 순서 유지 + 추가 기능

언제 사용하나?

상황자료구조시간 복잡도
빠른 검색해시 테이블O(1)
빈도수 세기CounterO(n)
중복 확인setO(n)
그룹화defaultdictO(n)
캐싱dict / LRU CacheO(1)

추천 문제

백준:

프로그래머스:

LeetCode:

다음 단계

  • 알고리즘: 트리
  • 알고리즘: 그래프

관련 글

  • 배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리