해시 테이블 (Hash Table)

해시 테이블 (Hash Table)

키를 해시 함수로 변환하여 배열의 인덱스로 사용함으로써 평균 O(1) 시간에 삽입·삭제·검색을 수행하는 자료구조로, 키-값 쌍을 효율적으로 저장

목적: 빠른 검색·삽입·삭제(O(1)), 키-값 매핑, 중복 검사, 캐싱

특징: 해시 함수, 배열 기반, 평균 O(1), 충돌 처리 필요

구성요소: ① 해시 함수 ② 배열(버킷) ③ 충돌 처리 방식 ④ 로드 팩터

해시 함수: h(key) → index, 균등 분포, 빠른 계산, 결정적

• •예: h(key) = key % table_size (나머지 연산)
• •Division, Multiplication, Universal Hashing

충돌(Collision): 서로 다른 키가 같은 인덱스로 매핑

• •체이닝(Chaining): 연결 리스트로 충돌 키 저장, 무제한 저장, 추가 메모리
• •개방 주소법(Open Addressing): 다른 빈 슬롯 찾기

로드 팩터(Load Factor): α = n / m (요소 수 / 테이블 크기)

• •α < 0.7: 성능 유지, α > 0.7: 재해싱(Rehashing, 테이블 확장+재삽입)

시간 복잡도

• •평균: 삽입·삭제·검색 O(1)
• •최악: O(n) - 모든 키가 충돌

공간 복잡도: O(n + m) - 체이닝, O(m) - 개방 주소법

장점: 매우 빠른 평균 성능(O(1)), 단순한 구현, 유연한 키 타입

단점: 최악 O(n), 정렬 불가, 범위 쿼리 불가, 메모리 오버헤드(로드 팩터), 해시 함수 의존

적용사례: HashMap/HashSet, 데이터베이스 해시 인덱스, 캐시(LRU), 중복 검사, 심볼 테이블

비교: 해시(평균 O(1)/정렬불가) vs BST(O(log n)/정렬/범위쿼리)

연관: 해시 함수, 충돌 처리, HashMap, 체이닝, 개방 주소법