해시 검색 (Hash Search)

해시 검색 (Hash Search)

해시 함수를 사용하여 키를 해시 테이블의 인덱스로 변환하고 O(1) 평균 시간에 데이터를 검색하는 방법

목적: 상수 시간 검색, 빠른 삽입/삭제, 대용량 데이터 접근

특징: O(1) 평균 시간, 해시 함수 의존, 충돌 처리 필요, 순서 없음

해시 함수 요건

• •균등 분포: 키를 테이블 전체에 고르게 분포
• •빠른 계산: O(1) 계산 시간
• •결정적: 같은 키는 항상 같은 해시 값

해시 함수 예시

• •나눗셈법: h(k) = k mod m (m은 소수 권장)
• •곱셈법: h(k) = ⌊m × (kA mod 1)⌋ (A는 황금비 등)
• •문자열 해시: 다항식 롤링 해시 (h = Σc_i × p^i mod m)

충돌 해결

• •Chaining: 연결 리스트로 같은 인덱스 원소 관리
• •Open Addressing: Linear/Quadratic Probing, Double Hashing

시간 복잡도

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

공간 복잡도: O(n) - 해시 테이블 크기

부하율(Load Factor): α = n/m (저장 원소 수/테이블 크기), 0.75 권장

장점: 매우 빠른 검색(O(1)), 삽입/삭제 효율

단점: 순서 없음, 해시 함수 품질 의존, 최악 O(n), 메모리 낭비 가능

적용사례: 데이터베이스 인덱스, 캐시, 심볼 테이블, 중복 검사

비교: 해시(O(1)/순서없음) vs 이진검색(O(log n)/정렬필요) vs 선형(O(n)/단순)

연관: 해시 테이블, 해시 함수, 충돌 해결, 부하율