Hash란?
어떤 **입력값(key)**을 받아서, 고정된 크기의 **출력값(hash value)**으로 변환하는 함수 또는 구조.
person = {
"name": "Alice",
"age": 25
}
- "name"이라는 key를 해시함수로 변환 → 어떤 메모리 위치로 매핑
- 거기서 바로 "Alice"를 가져옴 → 검색이 빠름 (O(1) 시간)
주요 개념
| 해시 함수 | 데이터를 특정한 고정 길이의 값으로 바꿔주는 함수 |
| 해시 값(hash value) | 해시 함수의 출력값 |
| 해시 충돌 | 서로 다른 입력값이 같은 해시값을 가질 때 충돌 발생 |
| 충돌 처리 | 같은 해시값이 나올 때 어떻게 처리할지 |
| 해시 테이블 | (key, value)쌍을 저장하고 검색하는 자료구조 |
| 검색/삽입 속도 | 평균 O(1) 시간 복잡도 |
해시의 사용
- 파이썬 딕셔너리(dict)
- 자바의 HashMap
- 데이터베이스 인덱싱
- 비밀번호 저장 (암호화 해시)
- 블록체인
- 캐시 시스템
주의할 점
- 해시는 복원 불가능한 경우도 많음 (예: 암호화 해시)
- 충돌이 생기면 성능 저하 → 충돌 처리 필요
코딩테스트 관점
| 중복 검사 | set() |
| 빠른 검색/삽입 | dict() |
| 빈도수 세기 | collections.Counter |
| 두개의 배열 비교 | 해시로 빠르게 매칭 |
자주 나오는 패턴
1. 배열에서 중복 요소 제거하기
nums = [1, 2, 3, 2, 1]
unique = list(set(nums)) # O(n)
print(unique) # [1, 2, 3]
2. 문자열 내 문자 등장 횟수 세기
from collections import Counter
s = "hello"
count = Counter(s)
print(count) # Counter({'l': 2, 'h': 1, 'e': 1, 'o': 1})
3. two sum(두 수의 합)
def two_sum(nums, target):
hash_map = {}
for i, num in enumerate(nums):
diff = target - num
if diff in hash_map:
return [hash_map[diff], i]
hash_map[num] = i
4. 완주하지 못한 선수
def solution(participant, completion):
from collections import Counter
p_count = Counter(participant)
c_count = Counter(completion)
diff = p_count - c_count
return list(diff.keys())[0]