Hash 인덱스

Hash 인덱스

해시 함수를 통해 키 값을 버킷 주소로 변환하여 데이터를 O(1) 시간에 검색하는 동등 조건 특화 인덱스

특징: 동등 검색 O(1) 최고 성능, 범위/정렬 검색 불가, 해시 충돌 처리 필요

구성요소

• •해시 함수(Hash Function): 키를 버킷 주소로 변환
• •버킷(Bucket): 해시 값에 대응하는 저장 위치
• •충돌 처리(Collision Handling): 체이닝(연결리스트), 개방 주소법

유형

• •정적 해싱(Static Hashing): 고정 버킷 수, 오버플로우 가능
• •동적 해싱(Dynamic Hashing): 확장 가능 해싱, 버킷 동적 분할

적용사례: 키-값 조회, 메모리 DB(Redis), 조인 연산(Hash Join)

비교: Hash 인덱스(동등검색 O(1)/범위불가) vs B-Tree 인덱스(범위검색 O(log n)/범용)

연관: 인덱스, 해싱, 메모리 DB, Hash Join