해시 (Hash)
해시란
해시 함수는 임의의 데이터를 고정된 크기의 정수로 변환하는 함수다. 좋은 해시 함수가 되려면 세 가지 조건을 갖춰야 한다. 첫째, 결정적이어야 한다. 같은 입력에는 항상 같은 출력이 나와야 한다. 둘째, 균등하게 분포해야 한다. 출력 값이 특정 범위에 몰리지 않고 전체 배열에 고르게 흩어져야 충돌이 줄어든다. 셋째, 빠르게 계산할 수 있어야 한다. 해시 값 계산 자체가 O(1)에 이루어져야 조회 전체가 O(1)로 유지된다. 이 정수를 인덱스로 사용해서 배열에 값을 저장한 것이 해시 테이블이다.
키 → 해시 함수 → 정수 (해시 값) → 배열 인덱스
"apple" → h("apple") → 3 → table[3] = value배열의 특정 인덱스에 바로 접근하기 때문에 삽입, 삭제, 검색 모두 평균 O(1)이다.
Python에서 hash() 내장 함수로 해시 값을 확인할 수 있다.
print(hash("apple"))
print(hash(42))
print(hash((1, 2, 3)))리스트는 해시 불가능하다. hash([1, 2, 3])은 TypeError를 낸다. 해시 함수는 불변(immutable) 객체에만 적용할 수 있다. 리스트처럼 변하는 객체는 같은 객체가 다른 해시 값을 가질 수 있어서 해시 키로 사용할 수 없다.
Python에서 해시 사용하기
dict 기본 사용법
Python의 dict가 해시 테이블의 구현체다.
scores = {"alice": 95, "bob": 82, "charlie": 90}
scores["dave"] = 88
print(scores["alice"])
print("bob" in scores)
print("eve" in scores)
scores.pop("charlie")
print(scores)출력:
95
True
False
{'alice': 95, 'bob': 82, 'dave': 88}in 연산자로 키 존재 여부를 O(1)에 확인할 수 있다. 리스트에서 in을 사용하면 O(n)인데, dict나 set에서는 O(1)이다. 중복 제거나 멤버십 검사가 필요할 때 리스트 대신 set을 사용하는 것이 중요한 이유다. set도 내부적으로 해시 테이블을 사용하기 때문에 in 연산이 O(1)이다.
get() 메서드로 키가 없을 때 기본값을 지정할 수 있다.
scores = {"alice": 95}
alice_score = scores.get("alice", 0)
bob_score = scores.get("bob", 0)
print(alice_score, bob_score)출력:
95 0키가 없을 때 scores["bob"]은 KeyError를 내지만, scores.get("bob", 0)은 0을 반환한다.
collections.defaultdict
빈도수를 세거나 그룹핑할 때, 키가 없으면 기본값으로 자동 초기화하는 defaultdict가 유용하다.
from collections import defaultdict
word_count = defaultdict(int)
words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
for word in words:
word_count[word] += 1
print(dict(word_count))출력:
{'apple': 3, 'banana': 2, 'cherry': 1}defaultdict(int)는 키가 없을 때 0을 기본값으로 사용한다. 일반 dict라면 word_count[word] = word_count.get(word, 0) + 1처럼 사용해야 하는 것이 += 1 한 줄로 줄어든다.
defaultdict(list)는 키가 없을 때 빈 리스트를 기본값으로 사용한다.
from collections import defaultdict
groups = defaultdict(list)
students = [("A반", "철수"), ("B반", "영희"), ("A반", "민준"), ("B반", "지수")]
for class_name, student in students:
groups[class_name].append(student)
print(dict(groups))출력:
{'A반': ['철수', '민준'], 'B반': ['영희', '지수']}collections.Counter
빈도수 세기에 특화된 클래스다. defaultdict(int)보다 기능이 더 풍부한 버전이다.
from collections import Counter
fruits = ["apple", "banana", "apple", "cherry", "banana", "apple"]
counter = Counter(fruits)
print(counter)
print(counter.most_common(2))
print(counter["apple"])
print(counter["grape"])출력:
Counter({'apple': 3, 'banana': 2, 'cherry': 1})
[('apple', 3), ('banana', 2)]
3
0most_common(n)은 빈도수 상위 n개를 내림차순으로 반환한다. 없는 키에 접근하면 KeyError 대신 0을 반환한다.
Counter끼리 뺄셈도 된다.
from collections import Counter
a = Counter(["apple", "apple", "banana", "cherry"])
b = Counter(["apple", "banana"])
result = a - b
print(result)출력:
Counter({'apple': 1, 'cherry': 1})두 리스트 사이의 차집합을 빈도 기반으로 구할 때 유용하다. 완주하지 못한 선수(프로그래머스 42576) 문제가 이 패턴의 전형이다.
해시 충돌과 해결 방법
서로 다른 키가 같은 해시 값을 가지는 상황을 해시 충돌이라고 한다. 해시 테이블 크기는 유한하고 키의 종류는 무한할 수 있어서, 충돌은 피할 수 없다.
체이닝 (Chaining)
같은 인덱스에 여러 값이 들어오면 그 자리에 연결 리스트를 달아서 관리한다.
index 3 → [("apple", 값A)] → [("grape", 값B)] → None최악의 경우 모든 키가 같은 인덱스로 몰리면 검색이 O(n)이 된다. 충돌이 적으면 O(1)을 유지한다.
개방 주소법 (Open Addressing)
충돌이 나면 다음 빈 슬롯을 찾아 그 자리에 저장한다. 선형 탐사(Linear Probing)가 가장 단순한 방법이다.
충돌 → 다음 인덱스 → 비어 있으면 저장Python의 dict는 내부적으로 개방 주소법(더블 해싱 방식)을 사용한다. 로드 팩터(저장된 항목 수 / 전체 슬롯 수)가 2/3을 넘으면 자동으로 크기를 두 배로 늘린다. 그래서 Python dict는 평균 O(1)을 유지한다.
| 연산 | 평균 | 최악 |
|---|---|---|
| 삽입 | O(1) | O(n) |
| 삭제 | O(1) | O(n) |
| 검색 | O(1) | O(n) |
최악 O(n)은 모든 키가 같은 인덱스로 몰렸을 때 발생하지만, 실제로는 거의 일어나지 않는다. Python의 dict는 로드 팩터가 2/3를 초과하면 배열 크기를 두 배로 늘려 충돌 확률을 낮추기 때문이다. 잘 설계된 해시 함수와 자동 리사이징이 결합되면 평균 O(1)이 실용적으로 보장된다.
해시 활용 패턴
빈도수 세기
가장 자주 사용되는 패턴이다. 배열에서 각 원소가 몇 번 등장하는지 셀 때 사용한다.
빈도수를 세는 것은 "가장 많이 나온 원소", "중복 원소 확인", "과반수 원소" 등 수많은 문제의 첫 번째 단계다.
리스트로 빈도수를 세면 느리다. 각 원소마다 .count()를 호출하면 배열을 n번 순회하고, 원소가 n개이면 전체 O(n^2)이 된다.
Counter는 배열을 한 번 순회하면서 각 원소를 키로, 등장 횟수를 값으로 저장한다. O(n)에 빈도수를 모두 구할 수 있다.
입력 [1, 2, 1, 1, 2, 1]로 Counter 결과와 과반수 판정 과정을 따라가면 다음과 같다.
Counter([1, 2, 1, 1, 2, 1]) → {1: 4, 2: 2}
threshold = 6 // 2 = 3
1의 빈도 4 > 3 → True → 1 반환from collections import Counter
def find_majority(nums):
count = Counter(nums)
threshold = len(nums) // 2
for num, freq in count.items():
if freq > threshold:
return num
return -1과반수 원소(배열에서 절반보다 많이 등장하는 원소)를 O(n)에 찾는 함수다.
두 자료 간 매칭/비교
두 배열 또는 두 문자열을 비교할 때, 한쪽을 해시에 넣고 다른 쪽을 순회하며 in 연산자로 O(1) 조회한다.
이 패턴의 핵심은 한쪽 자료를 "검색용 자료구조"로 미리 만들어두는 것이다. 다른 쪽을 하나씩 순회하면서 O(1) 조회로 빠르게 확인한다.
set(phone_numbers)로 변환하는 이유는 조회 성능 때문이다. 리스트에서 in은 처음부터 끝까지 순회하므로 O(n)이다. set에서 in은 해시 기반이므로 O(1)이다. 전화번호가 10만 개일 때 두 자릿수 차이가 난다.
코드의 이중 for문 구조를 따라가면 다음과 같다. 바깥 for는 각 전화번호를 하나씩 순회한다. 안쪽 for는 그 번호의 모든 가능한 접두사를 생성한다. number = "11955"이면 접두사는 "1", "11", "119", "1195"가 된다.
접두사 검사가 필요한 이유는 "119"가 "1195524421" 안에 포함되는지 확인하는 문제이기 때문이다. "119" in phone_set으로 O(1)에 판단한다.
def find_prefix_duplicates(phone_numbers):
phone_set = set(phone_numbers)
for number in phone_numbers:
for length in range(1, len(number)):
if number[:length] in phone_set:
return True
return False전화번호 목록에서 어떤 번호가 다른 번호의 접두사인지 확인하는 패턴이다. in 연산자가 O(1)이기 때문에, 리스트 대신 set으로 변환하는 것이 핵심이다.
그룹핑
같은 특성을 가진 원소를 같은 버킷에 모을 때 사용한다. 아나그램 그룹핑이 대표 예시다.
그룹핑은 공통점을 가진 원소끼리 같은 버킷에 묶는 것이다. 아나그램은 같은 알파벳을 사용하지만 순서가 다른 단어다. "eat"과 "tea"는 각각 a, e, t로 이루어져 있어서 아나그램 관계다.
핵심 아이디어는 "같은 그룹인지 판별하는 기준"을 해시의 키로 사용하는 것이다. 같은 아나그램 그룹이면 구성 알파벳이 같으므로, 알파벳을 정렬하면 항상 같은 문자열이 된다. sorted("eat")과 sorted("tea") 모두 ['a', 'e', 't']가 나온다.
defaultdict(list)는 키가 처음 등장할 때 빈 리스트를 자동으로 생성한다. 키를 미리 초기화하지 않아도 바로 append를 호출할 수 있다.
입력 ["eat", "tea", "tan"]으로 groups 딕셔너리가 채워지는 과정을 따라가면 다음과 같다.
"eat" → key = ('a', 'e', 't') → groups[('a', 'e', 't')] = ['eat']
"tea" → key = ('a', 'e', 't') → groups[('a', 'e', 't')] = ['eat', 'tea']
"tan" → key = ('a', 'n', 't') → groups[('a', 'n', 't')] = ['tan']세 단어가 두 그룹으로 나뉜다.
from collections import defaultdict
def group_anagrams(words):
groups = defaultdict(list)
for word in words:
key = tuple(sorted(word))
groups[key].append(word)
return list(groups.values())words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(words))출력:
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]철자가 같은 단어는 정렬하면 같은 문자열이 된다. 정렬된 문자열을 키로 사용해서 아나그램끼리 같은 그룹에 모은다.
연습 문제
초급
| 번호 | 문제 | 난이도 | 링크 | 핵심 접근 |
|---|---|---|---|---|
| 42576 | 완주하지 못한 선수 | Level 1 | https://programmers.co.kr/learn/courses/30/lessons/42576 | Counter 뺄셈으로 participant - completion에 남은 선수 찾기 |
| 42577 | 전화번호 목록 | Level 2 | https://programmers.co.kr/learn/courses/30/lessons/42577 | 전화번호 목록을 set으로 변환 후 접두사 여부 O(1) 조회 |
중급
| 번호 | 문제 | 난이도 | 링크 | 핵심 접근 |
|---|---|---|---|---|
| 42578 | 위장 | Level 2 | https://programmers.co.kr/learn/courses/30/lessons/42578 | 카테고리별 의상 수를 defaultdict로 집계 후 경우의 수 곱셈 |
| 42579 | 베스트앨범 | Level 3 | https://programmers.co.kr/learn/courses/30/lessons/42579 | 장르별 총재생수, 장르 내 곡 순위를 따로 집계 후 정렬 |
| 1620 | 나는야 포켓몬 마스터 | 실버 4 | https://www.acmicpc.net/problem/1620 | 이름→번호, 번호→이름 양방향 dict로 O(1) 조회 |