핵심

키는 해시 함수를 거쳐 버킷 번호로 바뀝니다. 그래서 = 검색은 바로 가지만, 범위 검색은 원래 순서를 잃어 버킷 전체를 확인해야 합니다.

저장 구조

h(key) = key % 4
key
hash
저장 위치
10
h(10) = 2
버킷 2
25
h(25) = 1
버킷 1
14
h(14) = 2
버킷 2

버킷 0

버킷 1

25

버킷 2

10 14

버킷 3

충돌: 10과 14는 둘 다 버킷 2로 가므로, 같은 버킷 안에서 추가 비교가 필요합니다.

쿼리가 보는 방식

등호 검색

WHERE id = 25

1 h(25) = 1
2 버킷 1만 직접 확인
3 평균 O(1)로 빠르게 찾음

정확히 한 버킷으로 바로 이동할 수 있어서 등호 조건에 강합니다.

범위 검색

WHERE id > 10 AND id < 30

1 해시 값은 숫자의 원래 순서를 보존하지 않음
버킷 0 확인 버킷 1 확인 버킷 2 확인 버킷 3 확인

버킷 번호만 보고는 10~30 사이 값을 모을 수 없어서 범위 검색에는 부적합합니다.