해시(Hash)
데이터의 빠른 검색, 삽입, 삭제를 가능하게 해주는 데이터 구조와 메커니즘
평균적으로 O(1) 시간 복잡도로 삽입/검색을 수행
해시(Hash) 기반 자료구조는 주로 딕셔너리(dict)와 셋(set) 형태로 제공
해싱(Hashing)
데이터를 특정 크기의 고유 값(해시 값)으로 변환
이때 사용되는 함수는 해시 함수(Hash Function)
해시 함수(Hash Function)
임의의 객체(문자열, 숫자, 튜플 등)에 대해 고유한 정수값(해시값)을 계산
파이썬에서는 내장 함수 hash(obj)를 통해 해시값을 확인
예: hash("hello") → 정수값
해시 테이블(Hash Table)
키-값 쌍을 저장하는 자료 구조
해시 함수로 계산된 해시 값을 인덱스로 사용해, 데이터가 저장될 버킷(bucket)을 찾음
버킷(Bucket) 또는 슬롯(Slot)
해시 테이블 안에는 여러 개의 버킷(슬롯)이 존재합
해시 함수로부터 나온 해시값을 버킷의 인덱스로 변환하여, 해당 버킷에 데이터를 저장
예: hash(key) % M (M은 버킷 배열의 크기)
충돌(Collision) 처리
서로 다른 키가 동일한 해시값(또는 동일한 버킷 인덱스)을 갖는 경우, 충돌이 발생
파이썬 dict와 set은 오픈 어드레싱(open addressing) 기법(특히 CPython은 오픈 어드레싱 + 이중 해싱 형태의 충돌 해결)을 사용
충돌이 심해지면 해시 테이블의 평균 접근 시간이 나빠지지만, 파이썬은 내부적으로 재해시(Rehash)와 확장을 통해 성능을 보정
---🐢
딕셔너리(dict) - 해시맵
기본 동작
# dict 생성
mydict = {"apple": 3, "banana": 5}
mydict["cherry"] = 10 # 삽입
print(mydict["banana"]) # 조회: 5키(key)
해시 가능한 객체 / 예) 문자열, 숫자, 튜플(내부 요소도 해시 가능해야)
리스트처럼 변경 가능한 객체는 해시 불가능(예외 발생)
값(value)
어떤 파이썬 객체든 가능 (해시 여부와 무관)
연산
삽입: mydict[key] = value (평균 O(1))
조회: value = mydict[key] (평균 O(1))
삭제: del mydict[key] (평균 O(1))
키 존재 확인: if key in mydict (평균 O(1))
# 파이썬 3.7부터 딕셔너리는 삽입 순서를 기억
# 즉, dict에 새 항목을 삽입하면, 추후 순회(for k in mydict:) 시 삽입된 순서대로 열거
내부 구조
배열(버킷 배열)
해시값을 나눈 인덱스를 사용해, (key, value, hash) 정보를 저장
오픈 어드레싱
버킷이 이미 사용중이면(충돌), 다음 버킷(이중 해싱 등)을 확인하여 빈 버킷을 찾음
확장(rehash)
버킷 사용률(로드 팩터)이 특정 임계값을 넘으면, 더 큰 버킷 배열로 확장 & 재배치
활용 예시(해시맵을 이용한 단어 세기)
text = "apple banana apple durian banana apple"
word_counts = {}
for word in text.split():
if word in word_counts:
word_counts[word] += 1
else:
word_counts[word] = 1
print(word_counts)
# {'apple': 3, 'banana': 2, 'durian': 1}--🐢-
셋(set) - 해시셋
기본 동작
myset = {"apple", "banana", "cherry"}
myset.add("orange")
print("banana" in myset) # True
myset.remove("cherry")원소(element)
해시 가능한 객체여야
연산
삽입: myset.add(elem) (평균 O(1))
검색: elem in myset (평균 O(1))
삭제: myset.remove(elem) (평균 O(1))
중복 허용 X
셋의 활용
멤버십 테스트(어떤 원소가 셋에 있는지 확인)가 빠름 (O(1))
중복 제거, 교집합/합집합/차집합 등의 집합 연산에 사용
-🐢--
시간 복잡도
딕셔너리와 셋은 평균적으로 다음 연산을 O(1) 시간에 수행
dict
키 삽입: O(1) (평균), 최악 O(n) (충돌 심할 때)
키 조회: O(1) (평균)
키 삭제: O(1) (평균)
set
원소 삽입: O(1) (평균)
원소 검색: O(1) (평균)
원소 삭제: O(1) (평균)
🐢---
주의 사항
# 해시 가능한 객체만 키/셋 원소로 사용 가능
문자열, 정수, 튜플(내부 요소도 해시 가능해야), frozenset 등은 가능
리스트, 딕셔너리 등 mutable(변경 가능) 객체는 해시 불가능 → 키나 셋 원소로 쓸 수 없음
# 충돌이 심해지면 성능 저하
파이썬 내부적으로 재해시(rehash) 와 확장을 통해 해결
보통 파이썬 레벨에서 크게 신경 쓰지 않아도 되지만, 해시 함수를 악의적으로 공격(DoS)할 수도 있음
# 정렬 순서
해시 자료 구조는 원래 순서를 보장하지 않는 것이 일반적이나,
파이썬 3.7+ dict는 삽입 순서 유지, set은 3.6/3.7 이후 구현상 순서를 유지하지만,
집합 연산 결과 등은 예측하기 어려운 순서가 나올 수 있으니, 순서가 필요하면 별도 정렬을 해야 함
# 딕셔너리의 키와 값
키는 해시 가능해야 하며 보통 immutable(불변) 객체 사용
값은 제한 없음(어떤 객체든 가능)