개념
키(Key)와 값(Value)을 매핑하여 데이터를 저장하는 자료구조
해시 함수를 사용하여 키를 배열의 인덱스로 변환하여
O(1)접근
시간복잡도
| 연산 | 평균 | 최악 | 설명 |
|---|---|---|---|
| 삽입 | O(1) | O(n) | 해시 충돌 시 최악 |
| 삭제 | O(1) | O(n) | 해시 충돌 시 최악 |
| 탐색 | O(1) | O(n) | 해시 충돌 시 최악 |
특징
장점
- 빠른 접근: 평균
O(1)시간에 데이터 접근 - 효율적인 탐색: 키를 통한 직접 접근
- 유연한 키: 다양한 타입의 키 사용 가능
단점
- 메모리 낭비: 빈 공간이 생길 수 있음
- 순서 없음: 데이터의 순서가 보장되지 않음
- 해시 충돌: 서로 다른 키가 같은 인덱스에 매핑될 수 있음
활용 분야
- 데이터베이스 인덱싱
- 캐시 구현
- 중복 검사
- 빠른 검색이 필요한 경우
핵심 개념
1. 해시 함수 (Hash Function)
키를 해시 값(인덱스)으로 변환하는 함수
# 간단한 해시 함수 예시
def simple_hash(key, table_size):
return hash(key) % table_size2. 해시 충돌 (Hash Collision)
서로 다른 키가 같은 해시 값을 가지는 경우
해결 방법:
- 체이닝 (Chaining): 같은 인덱스에 연결 리스트로 저장
- 오픈 어드레싱 (Open Addressing): 다른 빈 공간 찾기
Python 구현
1. Python 내장 딕셔너리 사용 (가장 추천)
# 딕셔너리 생성
hash_table = {}
# 삽입
hash_table['name'] = 'Alice'
hash_table['age'] = 25
hash_table['city'] = 'Seoul'
# 탐색
print(hash_table['name']) # Alice
print(hash_table.get('age')) # 25
print(hash_table.get('job', 'Not Found')) # Not Found
# 삭제
del hash_table['city']
# 키 존재 확인
if 'name' in hash_table:
print('name exists')
# 순회
for key, value in hash_table.items():
print(f"{key}: {value}")
# 시간복잡도: 모두 평균 O(1)2. 체이닝 방식으로 직접 구현
class HashTable:
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):
hash_index = self._hash(key)
bucket = self.table[hash_index]
# 키가 이미 존재하면 값 업데이트
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
# 새로운 키-값 추가
bucket.append((key, value))
def get(self, key):
hash_index = self._hash(key)
bucket = self.table[hash_index]
for k, v in bucket:
if k == key:
return v
return None
def delete(self, key):
hash_index = self._hash(key)
bucket = self.table[hash_index]
for i, (k, v) in enumerate(bucket):
if k == key:
del bucket[i]
return True
return False
def display(self):
for i, bucket in enumerate(self.table):
print(f"Index {i}: {bucket}")
# 사용 예시
ht = HashTable()
ht.insert('apple', 100)
ht.insert('banana', 200)
ht.insert('orange', 300)
print(ht.get('apple')) # 100
ht.delete('banana')
ht.display()3. collections.Counter 활용
from collections import Counter
# 리스트에서 빈도 계산
nums = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
counter = Counter(nums)
print(counter) # Counter({4: 4, 3: 3, 2: 2, 1: 1})
# 가장 많은 요소 찾기
print(counter.most_common(2)) # [(4, 4), (3, 3)]
# 문자열에서 문자 빈도
text = "hello world"
char_count = Counter(text)
print(char_count) # Counter({'l': 3, 'o': 2, ...})4. collections.defaultdict 활용
from collections import defaultdict
# 기본값이 있는 딕셔너리
dd = defaultdict(int) # 기본값 0
dd['apple'] += 1
dd['banana'] += 2
print(dd) # defaultdict(<class 'int'>, {'apple': 1, 'banana': 2})
# 리스트를 값으로 가지는 딕셔너리
dd_list = defaultdict(list)
dd_list['fruits'].append('apple')
dd_list['fruits'].append('banana')
print(dd_list) # defaultdict(<class 'list'>, {'fruits': ['apple', 'banana']})자주 나오는 문제 유형
1. 두 수의 합 (Two Sum)
문제: 배열에서 합이 target이 되는 두 수의 인덱스 찾기
def two_sum(nums, target):
hash_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hash_map:
return [hash_map[complement], i]
hash_map[num] = i
return []
# 테스트
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]
# 시간복잡도: O(n)
# 공간복잡도: O(n)핵심: 해시 테이블로 O(n²) → O(n) 최적화
2. 애너그램 그룹핑
문제: 애너그램끼리 그룹화하기
from collections import defaultdict
def group_anagrams(strs):
anagrams = defaultdict(list)
for s in strs:
# 정렬된 문자열을 키로 사용
key = ''.join(sorted(s))
anagrams[key].append(s)
return list(anagrams.values())
# 테스트
words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(words))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
# 시간복잡도: O(n * k log k) - n: 단어 개수, k: 단어 길이
# 공간복잡도: O(n * k)핵심: 정렬된 문자열을 해시 키로 사용
3. 첫 번째 중복되지 않는 문자
문제: 문자열에서 처음으로 한 번만 나타나는 문자 찾기
def first_unique_char(s):
# 빈도 계산
char_count = {}
for char in s:
char_count[char] = char_count.get(char, 0) + 1
# 첫 번째 유일한 문자 찾기
for i, char in enumerate(s):
if char_count[char] == 1:
return i
return -1
# 테스트
print(first_unique_char("leetcode")) # 0 ('l')
print(first_unique_char("loveleetcode")) # 2 ('v')
# 시간복잡도: O(n)
# 공간복잡도: O(1) - 알파벳 26개로 제한핵심: 두 번의 순회로 해결 (빈도 계산 + 첫 유일 문자)
4. 연속된 배열의 최대 길이
문제: 정렬되지 않은 배열에서 연속된 수의 최대 길이 찾기
def longest_consecutive(nums):
num_set = set(nums)
max_length = 0
for num in num_set:
# 시작점만 확인 (num-1이 없는 경우)
if num - 1 not in num_set:
current = num
length = 1
# 연속된 수 찾기
while current + 1 in num_set:
current += 1
length += 1
max_length = max(max_length, length)
return max_length
# 테스트
print(longest_consecutive([100, 4, 200, 1, 3, 2])) # 4 ([1,2,3,4])
# 시간복잡도: O(n)
# 공간복잡도: O(n)핵심: Set으로 O(1) 탐색, 시작점만 확인하여 중복 계산 방지
5. 부분 배열의 합이 K (Subarray Sum Equals K)
문제: 합이 K인 연속 부분 배열의 개수 찾기
def subarray_sum(nums, k):
count = 0
prefix_sum = 0
sum_count = {0: 1} # 누적 합: 빈도
for num in nums:
prefix_sum += num
# prefix_sum - k가 존재하면, 그만큼의 부분 배열 존재
if prefix_sum - k in sum_count:
count += sum_count[prefix_sum - k]
# 현재 누적 합 저장
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
return count
# 테스트
print(subarray_sum([1, 1, 1], 2)) # 2
print(subarray_sum([1, 2, 3, 4, 5], 9)) # 2 ([2,3,4], [4,5])
# 시간복잡도: O(n)
# 공간복잡도: O(n)핵심: 누적 합(Prefix Sum)과 해시 테이블 활용
6. 중복 문자 없는 가장 긴 부분 문자열
문제: 중복 문자가 없는 가장 긴 부분 문자열의 길이
def length_of_longest_substring(s):
char_index = {}
max_length = 0
start = 0
for end, char in enumerate(s):
# 중복 문자 발견
if char in char_index and char_index[char] >= start:
start = char_index[char] + 1
char_index[char] = end
max_length = max(max_length, end - start + 1)
return max_length
# 테스트
print(length_of_longest_substring("abcabcbb")) # 3 ("abc")
print(length_of_longest_substring("bbbbb")) # 1 ("b")
print(length_of_longest_substring("pwwkew")) # 3 ("wke")
# 시간복잡도: O(n)
# 공간복잡도: O(min(n, m)) - m: 문자 집합 크기핵심: 슬라이딩 윈도우 + 해시 테이블로 중복 추적
추천 연습 문제
기초
중급
- LeetCode 1 - Two Sum
- LeetCode 49 - Group Anagrams
- LeetCode 387 - First Unique Character
- 백준 9375번 - 패션왕 신해빈
고급
- LeetCode 128 - Longest Consecutive Sequence
- LeetCode 560 - Subarray Sum Equals K
- LeetCode 3 - Longest Substring Without Repeating Characters
핵심 요약
| 개념 | 설명 |
|---|---|
| 원리 | 키를 해시 함수로 변환하여 인덱스 결정 |
| 연산 | 삽입, 삭제, 탐색 평균 O(1) |
| 구현 | Python dict, set 사용 |
| 활용 | 빠른 탐색, 중복 검사, 빈도 계산 |
해시 테이블 vs 배열
| 특성 | 해시 테이블 | 배열 |
|---|---|---|
| 접근 | O(1) (키 기반) | O(1) (인덱스 기반) |
| 탐색 | O(1) | O(n) |
| 순서 | 보장 안 됨 | 보장됨 |
| 메모리 | 추가 공간 필요 | 연속적 |
유용한 Python 해시 자료구조
| 자료구조 | 용도 |
|---|---|
| dict | 기본 키-값 매핑 |
| set | 중복 제거, 집합 연산 |
| Counter | 빈도 계산 |
| defaultdict | 기본값이 있는 딕셔너리 |
| OrderedDict | 순서가 보장되는 딕셔너리 (Python 3.7+ dict도 순서 보장) |