해시 코드와 배열 인덱스
직접 인덱싱의 범위 실패를 출발점으로 해시 함수·그룹·충돌 탐색의 역할을 분리합니다.
정수 키 1을 배열 1번 칸에 저장하면 조회는 한 번에 끝납니다.
문제는 키가 -20이거나 10억일 때입니다.
키 범위만큼 배열을 만들 수 없고 음수 칸도 존재하지 않습니다.
해시 자료 구조는 원본 키를 버리는 대신 제한된 그룹 인덱스로 변환하고, 같은 인덱스에 모인 후보 안에서 원래 키를 다시 비교합니다.
키의 직접 배열 인덱스 사용 실패
다음 코드는 작은 양수에서는 성공해 결함이 숨어 있습니다.
두 번째 입력 -7이 들어오면 배열 경계 밖을 접근합니다.
배열 길이를 100만으로 키워도 음수 문제는 남고, 드문 큰 키 때문에 대부분의 칸이 비게 됩니다.
public final class DirectIndexFailure {
public static void main(String[] args) {
String[] values = new String[10];
values[3] = "hash";
values[-7] = "collision";
System.out.println(values[3]);
}
}java.lang.ArrayIndexOutOfBoundsException: Index -7 out of bounds for length 10원본 키와 저장 위치를 같은 값으로 본 것이 원인입니다.
해시 코드는 넓은 키 공간을 정수로 요약하고, 인덱스 함수는 그 정수를 그룹 배열 범위로 줄입니다.
이 두 변환 뒤에도 원본 키는 그룹 안에 보관해야 합니다.
나머지 연산과 음수 처리
그룹 수가 8이면 양수 hashCode에 hashCode % 8을 적용해 0부터 7까지를 얻습니다.
하지만 Java의 %는 왼쪽 피연산자가 음수일 때 음수 결과를 낼 수 있습니다.
Math.floorMod(hashCode, bucketCount)는 항상 유효한 0 이상 인덱스를 반환해 의도를 정확히 드러냅니다.
bucketCount가 0이면 어떤 나머지 연산도 성립하지 않습니다.
생성자에서 양수인지 검사하고 이후에는 바뀌지 않게 둡니다.
이 검증은 add마다 반복할 일이 아니라 자료 구조 생성 불변식입니다.
충돌은 오류가 아니라 후보가 늘어난 상태
서로 다른 키도 같은 나머지를 가질 수 있습니다.
그룹이 8개라면 1, 9, 17은 모두 1번에 도착합니다.
하나의 배열 칸에 값 하나만 두고 새 입력으로 덮어쓰면 기존 키를 잃습니다.
각 칸을 작은 목록으로 만들고 충돌한 Entry를 함께 저장해야 합니다.
조회는 전체 저장소를 훑지 않습니다.
먼저 해시 인덱스로 한 그룹을 고른 뒤 그 목록에서 원본 키의 동등성을 확인합니다.
분산이 좋으면 그룹이 짧아 평균 탐색이 빠르고, 모든 키가 한 칸에 모이면 선형 검색으로 퇴화합니다.
import java.util.ArrayList;
import java.util.List;
public final class IntegerBucketTable {
public static void main(String[] args) {
IntTable table = new IntTable(8);
table.put(1, "array");
table.put(9, "hash");
table.put(-7, "negative");
System.out.println(table.get(1));
System.out.println(table.get(9));
System.out.println(table.get(-7));
System.out.println("sizes=" + table.bucketSizes());
}
private static final class IntTable {
private final List<List<Entry>> buckets = new ArrayList<>();
IntTable(int bucketCount) {
if (bucketCount <= 0) throw new IllegalArgumentException("bucketCount");
for (int i = 0; i < bucketCount; i++) {
buckets.add(new ArrayList<>());
}
}
void put(int key, String value) {
List<Entry> bucket = buckets.get(index(key));
for (int i = 0; i < bucket.size(); i++) {
if (bucket.get(i).key() == key) {
bucket.set(i, new Entry(key, value));
return;
}
}
bucket.add(new Entry(key, value));
}
String get(int key) {
for (Entry entry : buckets.get(index(key))) {
if (entry.key() == key) {
return entry.value();
}
}
return null;
}
private int index(int key) {
return Math.floorMod(Integer.hashCode(key), buckets.size());
}
String bucketSizes() {
StringBuilder out = new StringBuilder();
for (List<Entry> bucket : buckets) {
out.append(bucket.size());
}
return out.toString();
}
}
private static final class Entry {
private final int key;
private final String value;
private Entry(int key, String value) {
this.key = key;
this.value = value;
}
private int key() { return key; }
private String value() { return value; }
}
}1, 9, -7은 모두 같은 1번 그룹에 들어가지만 get은 세 값을 구분합니다.
이 예제에서 충돌은 데이터 손실이 아니라 그룹 내부 비교 횟수 증가로 나타납니다.
bucketSizes 출력은 분산을 눈으로 확인하기 위한 진단값입니다.
제네릭 배열 형변환이 핵심을 흐리지 않도록 그룹 자체도 List로 표현했습니다.
해시 성능을 설명할 때 확인할 세 숫자
첫째는 그룹 수입니다.
너무 적으면 충돌이 늘고 너무 많으면 빈 목록과 배열 공간이 늘어납니다.
둘째는 저장 원소 수를 그룹 수로 나눈 적재 계수입니다.
셋째는 평균만 가릴 수 있는 가장 긴 그룹 길이입니다.
원소 수가 늘면 더 큰 그룹 배열을 만들고 모든 키의 새 index를 계산하는 rehash가 필요합니다.
기존 인덱스를 그대로 복사할 수 없는 이유는 나누는 그룹 수가 달라지기 때문입니다.
확장 한 번은 비싸지만 이후 탐색 길이를 다시 줄입니다.
해시 함수가 같은 입력에 매번 다른 값을 반환하면 저장 당시 그룹을 조회에서 찾을 수 없습니다.
키가 저장된 뒤 hashCode 계산에 쓰는 필드가 바뀌어도 같은 문제가 생깁니다.
해시 키는 동등성과 해시가 안정적인 값 객체여야 합니다.
게시글 저장소의 숫자 식별자를 해시로 탐색
게시글 저장소 CLI가 게시글 ID로 기록을 찾는다고 가정합니다.
사용자는 그룹을 모르고 id만 전달합니다.
저장소는 id를 해시하고 후보 Post의 id를 비교한 뒤 제목을 반환합니다.
import java.util.HashMap;
import java.util.Map;
public final class HashedBoardPostCli {
public static void main(String[] args) {
Map<Integer, Post> posts = new HashMap<>();
add(posts, new Post(101, "hash-index", 45));
add(posts, new Post(205, "collision", 55));
int requested = 205;
Post found = posts.get(requested);
System.out.println("found=" + found.title());
int total = 0;
for (Post post : posts.values()) {
total += post.viewCount();
}
System.out.println("total=" + total);
}
private static void add(Map<Integer, Post> posts, Post post) {
if (posts.putIfAbsent(post.id(), post) != null) {
throw new IllegalArgumentException("duplicate id=" + post.id());
}
}
private static final class Post {
private final int id;
private final String title;
private final int viewCount;
private Post(int id, String title, int viewCount) {
if (id <= 0 || title == null || title.isBlank() || viewCount <= 0) {
throw new IllegalArgumentException("invalid post");
}
this.id = id;
this.title = title;
this.viewCount = viewCount;
}
private int id() { return id; }
private String title() { return title; }
private int viewCount() { return viewCount; }
}
}HashMap을 쓰는 애플리케이션 코드는 해시의 내부 동작을 재구현하지 않습니다.
직접 만든 IntTable은 원리 확인용이고, CLI는 표준 구현의 putIfAbsent로 중복 ID 정책을 표현합니다.
조회 결과와 합계가 외부에 드러나는 계약입니다.
연습 문제
키 1, 9, 2, 10, -7을 그룹 8개에 배치합니다.
각 키와 floorMod로 얻은 index를 출력하고 어떤 키가 충돌하는지 설명하세요.
정답과 해설
1, 9, -7은 1번에 모이고 2와 10은 2번에 모입니다.
음수에도 % 대신 floorMod를 쓰므로 -7의 결과가 유효합니다.
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.ArrayList;
public final class CollisionGroupSolution {
public static void main(String[] args) {
Map<Integer, List<Integer>> groups = new LinkedHashMap<>();
for (int key : new int[] {1, 9, 2, 10, -7}) {
int index = Math.floorMod(Integer.hashCode(key), 8);
groups.computeIfAbsent(index, ignored -> new ArrayList<>()).add(key);
System.out.println(key + "->" + index);
}
System.out.println(groups);
}
}이 출력에서 같은 index는 같은 키라는 뜻이 아닙니다.
그룹 선택 뒤 원본 키 비교가 반드시 남아 있어야 충돌한 값이 공존합니다.
이 절의 마무리 기준은 세 문장입니다.
hashCode는 키를 정수로 요약하고, floorMod는 배열 범위를 보장하며, equals 또는 원본 키 비교는 충돌 후보를 구분합니다.
어느 하나라도 생략하면 범위 오류·데이터 손실·잘못된 조회 중 하나가 발생합니다.