해시 테이블 | O(1) 탐색 자료구조 완벽 정리 | 핵심 개념과 실전 활용
이 글의 핵심
해시 테이블: O(1) 탐색 자료구조 해시 함수 (Hash Function)·Python dict 사용법.
시리즈 안내
🎯 이 글을 읽으면 (읽는 시간: 20분)
TL;DR: O(1) 탐색의 비밀, 해시 테이블을 완벽하게 마스터합니다. 배열의 O(n) 검색을 O(1)로 최적화하는 방법과 해시 충돌 해결 전략을 배웁니다. 이 글을 읽으면:
- ✅ 해시 함수와 해시 테이블 동작 원리 완벽 이해
- ✅ Python dict, C++ unordered_map 실전 활용
- ✅ 해시 충돌 해결 전략 (Chaining, Open Addressing) 마스터 실무 활용:
- 🔥 빠른 데이터 검색 (사용자 조회, 캐싱)
- 🔥 중복 제거 및 빈도 계산
- 🔥 Two Sum, Anagram 등 코딩 테스트 난이도: 중급 | 실습 문제: 8개 | Python + C++: 모두 포함
들어가며
해시 테이블이란?
해시 테이블(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) |
코딩 테스트 준비하며 깨달은 것
알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.
1. 해시 함수 (Hash Function)
해시 함수란?
해시 함수는 임의 크기의 데이터를 고정 크기의 값(해시값)으로 변환하는 함수입니다. 좋은 해시 함수의 조건:
- ✅ 결정적: 같은 입력 → 같은 출력
- ✅ 빠른 계산: O(1)
- ✅ 균등 분포: 해시값이 골고루 분산
- ✅ 충돌 최소화: 다른 입력 → 다른 출력 (이상적)
간단한 해시 함수 예제
해시 함수는 키를 받아 고정된 크기의 슬롯 번호(배열 인덱스)로 바꿉니다. 우편번호로 구역을 나누듯, “이 키는 몇 번 칸에 넣는다”를 한 번에 정해 주는 역할입니다. 같은 키는 항상 같은 칸으로 가야 하므로(결정적) 검색 시에도 같은 인덱스로 찾아갈 수 있습니다.
# 방법 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')}") # NoneChaining 시간 복잡도:
- 평균: 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')}") # 100Linear Probing 문제점:
- 클러스터링(Clustering): 연속된 공간이 채워지면 탐색 시간 증가
2-2. Quadratic Probing (이차 탐사)
충돌 시 제곱수만큼 이동합니다 (1, 4, 9, 16, …).
def _probe_quadratic(self, key, i):
"""i번째 충돌 시 이동할 인덱스"""
return (hash(key) + i * i) % self.size2-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.sizeChaining vs Open Addressing 비교
| 특징 | Chaining | Open Addressing |
|---|---|---|
| 충돌 해결 | 연결 리스트 | 다른 빈 공간 |
| 메모리 | 추가 메모리 (포인터) | 고정 크기 배열 |
| 캐시 효율 | 낮음 | 높음 |
| 삭제 | 쉬움 | 복잡 (재배치 필요) |
| 부하율 | > 1 가능 | < 1 필수 |
| 사용 | Python dict | Java 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개씩 선택하세요. 조건:
- 장르별 총 재생 횟수가 많은 순서대로
- 장르 내에서 재생 횟수가 많은 순서대로
- 재생 횟수가 같으면 고유 번호가 낮은 순서대로
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
결과: 35. 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 result7. 해시 테이블 성능 최적화
부하율 (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))정리
핵심 요약
- 해시 테이블: 키-값 저장, 평균 O(1) 검색/삽입/삭제
- 해시 함수: 키를 인덱스로 변환, 균등 분포 중요
- 충돌 해결:
- Chaining: 연결 리스트로 저장
- Open Addressing: 다른 빈 공간 찾기 (Linear/Quadratic/Double Hashing)
- Python 도구:
dict: 기본 해시 테이블Counter: 빈도수 세기defaultdict: 기본값 자동 생성OrderedDict: 순서 유지 + 추가 기능
언제 사용하나?
| 상황 | 자료구조 | 시간 복잡도 |
|---|---|---|
| 빠른 검색 | 해시 테이블 | 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
다음 단계
관련 글
심화 부록: 구현·운영 관점
이 부록은 앞선 본문에서 다룬 주제(「해시 테이블 | O(1) 탐색 자료구조 완벽 정리」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.
내부 동작과 핵심 메커니즘
flowchart TD A[입력·요청·이벤트] --> B[파싱·검증·디코딩] B --> C[핵심 연산·상태 전이] C --> D[부작용: I/O·네트워크·동시성] D --> E[결과·관측·저장]
sequenceDiagram participant C as 클라이언트/호출자 participant B as 경계(런타임·게이트웨이·프로세스) participant D as 의존성(API·DB·큐·파일) C->>B: 요청/이벤트 B->>D: 조회·쓰기·RPC D-->>B: 지연·부분 실패·재시도 가능 B-->>C: 응답 또는 오류(코드·상관 ID)
- 불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
- 결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
- 경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
- 백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.
프로덕션 운영 패턴
| 영역 | 운영 관점 질문 |
|---|---|
| 관측성 | 요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가 |
| 안전성 | 입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가 |
| 신뢰성 | 재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가 |
| 성능 | 캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가 |
| 배포 | 롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가 |
| 용량 | 피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가 |
스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.
확장 예시: 엔드투엔드 미니 시나리오
앞선 본문 주제(「해시 테이블 | O(1) 탐색 자료구조 완벽 정리」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.
- 입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
- 핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
- 실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
- 호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
- 부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.
handle(request):
ctx = newCorrelationId()
validated = validateSchema(request)
authorize(validated, ctx)
result = domainCore(validated)
persistOrEmit(result, idempotentKey)
recordMetrics(ctx, latency, outcome)
return result문제 해결(Troubleshooting)
| 증상 | 가능 원인 | 조치 |
|---|---|---|
| 간헐적 실패 | 레이스, 타임아웃, 외부 의존성, DNS | 최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검 |
| 성능 저하 | N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스 | 프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거 |
| 메모리 증가 | 캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납 | 상한·TTL·힙/FD 스냅샷 비교 |
| 빌드·배포만 실패 | 환경 변수, 권한, 플랫폼 차이, lockfile | CI 로그와 로컬 diff, 런타임·이미지 버전 핀 |
| 설정 불일치 | 프로필·시크릿·기본값, 리전 | 스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화 |
| 데이터 불일치 | 비멱등 재시도, 부분 쓰기, 캐시 무효화 누락 | 멱등 키·아웃박스·트랜잭션 경계 재검토 |
권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.
배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.
자주 묻는 질문 (FAQ)
Q. 이 내용을 실무에서 언제 쓰나요?
A. 해시 테이블: O(1) 탐색 자료구조 완벽 정리. 해시 함수 (Hash Function)·Python dict 사용법로 흐름을 잡고 원리·코드·실무 적용을 한글로 정리합니다. 알고리즘·자료구조·해시테이블 중심으로 설… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.
Q. 선행으로 읽으면 좋은 글은?
A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.
Q. 더 깊이 공부하려면?
A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.
같이 보면 좋은 글 (내부 링크)
이 주제와 연결되는 다른 글입니다.
- 배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리
- 스택과 큐 | 코딩 테스트 필수 자료구조 완벽 정리
- Python 자료형 | 리스트, 딕셔너리, 튜플, 세트 완벽 가이드
- C++ map vs unordered_map 심층 비교 | ‘어느 게 빠를까?’ 성능 비교와 선택 가이드
이 글에서 다루는 키워드 (관련 검색어)
알고리즘, 자료구조, 해시테이블, Hash Table, dict, 코딩테스트 등으로 검색하시면 이 글이 도움이 됩니다.