버킷

해시 테이블에서 데이터를 저장하는 배열의 각 칸(슬롯) 을 의미합니다.

구조

해시 테이블 = 버킷들의 배열

index 0 → [버킷 0] → null
index 1 → [버킷 1] → "apple"
index 2 → [버킷 2] → null
index 3 → [버킷 3] → "banana" → "grape"  (체이닝)
index 4 → [버킷 4] → "cherry"

버킷 관련 핵심 개념

Java HashMap에서의 버킷

// 기본 버킷 크기: 16
// 로드 팩터: 0.75
// → 12개 이상 저장 시 버킷 크기 2배로 확장 (재해싱)

Map<String, Integer> map = new HashMap<>(); // 버킷 16개 생성
// 초기 용량 지정 가능
Map<String, Integer> map2 = new HashMap<>(32); // 버킷 32개 생성

로드 팩터와 성능

로드 팩터 낮음 → 충돌 적음, 메모리 낭비
로드 팩터 높음 → 충돌 많음, 메모리 효율 좋음
→ Java HashMap 기본값 0.75는 이 둘의 절충점

버킷은 해시 테이블의 저장 공간 단위이며, 버킷 수와 로드 팩터가 해시 테이블의 성능을 결정하는 핵심 요소입니다.