해시 테이블: O(1) 탐색 원리, 충돌 처리, 코딩 테스트 활용 패턴

시리즈 안내

#03 | 📋 전체 목차 | 이전: #02 스택과 큐 · 다음: #04 트리

---

들어가며

해시 테이블이란?

해시 테이블(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)

---

해시 함수 (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 (충돌!)

---

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)  # {}

---

해시 충돌 해결 방법

충돌이란?

서로 다른 키가 같은 해시값(인덱스)을 가질 때 충돌(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 비교

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

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

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

비교표에서 인터넷 자료가 자주 틀리는 곳이 마지막 줄입니다. CPython의 dict는 개방 주소법을 씁니다. 다만 위의 선형 탐사가 아니라, 해시값의 상위 비트를 조금씩 섞어 다음 칸을 정하는 섭동(perturbation) 탐사를 써서 클러스터링을 줄입니다. 테이블은 부하율이 약 2/3에 도달하면 더 큰 배열로 옮겨지며, Python 3.6부터는 실제 키·값을 삽입 순서대로 담은 배열과 그 배열의 번호만 담은 작은 해시 인덱스를 따로 두는 “compact dict” 구조를 씁니다. 3.7부터 dict가 삽입 순서를 보장하게 된 것이 바로 이 구조 덕분입니다. Java의 HashMap과 C++의 std::unordered_map은 체이닝이며, Java는 한 버킷에 원소가 8개 이상 몰리면 연결 리스트를 레드-블랙 트리로 바꿔 최악의 경우를 O(log n)으로 제한합니다.

개방 주소법에서 삭제가 “복잡”한 이유도 구체적으로 알아 둘 만합니다. 탐사 경로 중간의 칸을 그냥 비워 버리면, 그 뒤에 밀려서 저장된 키를 찾을 때 빈 칸에서 탐색이 멈춰 “없는 키”로 잘못 판단합니다. 그래서 실제 구현은 삭제된 칸에 삭제 표시(tombstone)를 남기고, 탐색할 때는 건너뛰되 삽입할 때는 재사용합니다. 삭제가 많이 쌓이면 빈 칸이 부족해 탐사가 길어지므로, CPython도 삭제 표시가 많아지면 재해싱으로 테이블을 정리합니다.

“평균 O(1)“에는 재해싱 비용을 나눠 낸 분할 상환(amortized) 이라는 의미도 들어 있습니다. 테이블을 두 배로 키울 때 모든 키를 새 배열로 옮기는 O(n) 작업이 가끔 일어나지만, 그 비용을 그동안의 삽입 횟수로 나누면 한 번당 상수입니다. 실시간 응답이 중요한 시스템에서 특정 요청만 가끔 느려지는 현상이 이 재해싱 때문인 경우가 있습니다.

---

실전 문제 풀이

문제 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) - 한 번만 순회

이 풀이의 핵심은 확인을 먼저 하고 저장을 나중에 한다는 순서입니다. 현재 값 num을 딕셔너리에 먼저 넣고 target - num을 찾으면, target이 짝수이고 num이 그 절반일 때(예: [3, 2, 4], target = 6에서 3) 자기 자신을 짝으로 찾아 [0, 0]을 반환하는 버그가 생깁니다. 또 같은 값이 여러 번 나올 수 있다면 딕셔너리에는 마지막 인덱스만 남는다는 점도 기억해야 합니다. “모든 쌍의 개수”를 세는 변형 문제에서는 인덱스 대신 등장 횟수를 저장해야 합니다.

문제 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

---

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}

---

해시 테이블 실전 활용 패턴

패턴 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

---

해시 테이블 성능 최적화

부하율 (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)}")

---

자주 하는 실수와 해결법

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

# ❌ 잘못된 방법
# hash_table = {[1, 2]: "value"}  # TypeError: unhashable type: 'list'
# ✅ 올바른 방법
hash_table = {(1, 2): "value"}  # 튜플 사용
print(hash_table[(1, 2)])  # value

리스트가 키가 될 수 없는 이유는 해시 테이블의 전제 때문입니다. 키를 넣을 때 계산한 해시값으로 칸을 정했는데, 나중에 키의 내용이 바뀌면 해시값도 바뀌어 그 키를 다시는 찾을 수 없게 됩니다. 그래서 Python은 내용이 바뀔 수 있는 list, dict, set에는 해시를 제공하지 않고 TypeError: unhashable type: 'list'를 냅니다. 좌표나 상태를 키로 쓸 때 tuple로 바꾸는 이유가 이것이며, 튜플 안에 리스트가 들어 있으면 그 튜플도 해시할 수 없습니다. 직접 만든 클래스는 기본적으로 객체의 id로 해시되므로, __eq__를 재정의해 “내용이 같으면 같은 객체”로 만들었다면 __hash__도 같은 필드로 함께 정의해야 합니다(__eq__만 정의하면 Python이 __hash__를 None으로 만들어 해시할 수 없는 타입이 됩니다). @dataclass(frozen=True)를 쓰면 이 둘을 자동으로 맞춰 줍니다.

실수 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("키가 없습니다")

defaultdict는 편하지만 조회만 해도 키가 생긴다는 부작용이 있습니다. if counts[x] > 0:처럼 존재 여부를 확인하려고 접근하는 순간 counts[x] = 0이 추가되어, 나중에 len(counts)나 순회 결과가 예상과 달라집니다. 존재 여부를 확인할 때는 x in counts나 counts.get(x, 0)을 쓰는 편이 안전합니다.

실수 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}

---

코딩 테스트에서 해시 테이블을 고르는 기준

해시 테이블을 쓰기 전에 키의 범위가 작은 정수인지 먼저 확인하면 좋습니다. 알파벳 소문자 빈도라면 크기 26의 리스트, 값이 0~100000인 정수라면 크기 100001의 리스트가 해시 테이블보다 빠르고 메모리도 예측 가능합니다. 해시 테이블이 진가를 발휘하는 것은 키가 문자열이거나 범위가 커서 배열로 만들 수 없을 때입니다. 또 Codeforces 같은 공개 채점 환경에서는 특정 언어 구현의 해시 함수를 노려 모든 키가 같은 칸에 몰리게 만든 입력(anti-hash test)이 올라오기도 합니다. Python 정수의 해시는 값 그대로라서 이런 공격에 노출될 수 있고, 이런 경우에는 정렬 후 이분 탐색이나 키에 임의 값을 섞는 방식으로 우회합니다.

# ✅ 해시 테이블 사용
# - 빠른 검색 (평균 O(1), 충돌이 몰리면 최악 O(n))
# - 빈도수 세기
# - 중복 확인
# - 그룹화
# - 캐싱
# ❌ 해시 테이블 부적합
# - 순서가 중요 (정렬된 순서) → 이진 탐색 트리
# - 범위 검색 (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))

---

상황별 선택과 추천 문제

해시 테이블은 “이 값을 전에 본 적이 있는가”, “몇 번 나왔는가”를 묻는 문제에서 거의 항상 첫 번째 후보입니다. 반대로 “k번째로 작은 값”이나 “범위 안의 값”처럼 순서가 필요한 질문에는 맞지 않으므로 정렬이나 이진 탐색 트리 쪽을 봐야 합니다.

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

백준:

• 1620번: 나는야 포켓몬 마스터
• 9375번: 패션왕 신해빈
• 17219번: 비밀번호 찾기

프로그래머스:

• 완주하지 못한 선수
• 베스트앨범
• 의상

LeetCode:

• 1. Two Sum
• 49. Group Anagrams
• 3. Longest Substring Without Repeating Characters

패션왕 신해빈과 의상은 같은 문제로, 종류별 개수를 센 뒤 “(개수 + 1)을 모두 곱하고 1을 빼는” 조합 계산이 핵심입니다. 다음 글인 트리에서는 해시가 못 하는 “순서 있는 탐색”을 다룹니다.

---

같이 보면 좋은 글

• 배열과 리스트 | 코딩 테스트 필수 자료구조
• 스택과 큐 | 코딩 테스트 필수 자료구조
• Python 자료형 | 리스트, 딕셔너리, 튜플, 세트
• C++ map vs unordered_map: 레드-블랙 트리와 해시 테이블의 성능·메모리 비교