HashMap을 설명할 때 가장 자주 등장하는 단어가 버킷(bucket)이다.
하지만 막상 “버킷이 정확히 뭐냐”고 물으면 명확하게 설명을 못한다.
이 글은 HashMap 내부 구조를 bucket → Node 순서로 정리해서, “HashMap이 데이터를 어디에, 어떤 단위로 저장하는지”를 정확히 이해하는 것을 목표로 한다.
HashMap의 가장 바깥 구조는 table 배열이다
HashMap 내부에는 다음과 같은 필드가 있다.
Node<K, V>[] table;이 한 줄이 HashMap의 전체 뼈대다.
table은 1차원 배열- 배열의 각 칸은 버킷(bucket) 이다
즉,
HashMap = 버킷들의 배열
이라는 말이 정확한 출발점이다.
버킷(bucket)이란 정확히 무엇인가
버킷은 추상적인 개념이 아니라, table 배열의 한 칸이다.
table[0] → bucket 0
table[1] → bucket 1
table[2] → bucket 2
...HashMap에서 자주 나오는 표현을 정확히 고쳐 쓰면 이렇다.
❌ “버킷 안에 여러 개가 들어간다”
✅ “하나의 버킷(table[index])이 여러 엔트리의 시작점이 될 수 있다”
이 차이가 굉장히 중요하다.
hashCode는 “버킷 번호”를 정하기 위한 값이다
map.put(key, value);이 한 줄이 실행되면, HashMap은 다음 질문을 먼저 던진다.
이 key는 table 배열의 몇 번 칸(bucket)에 들어가야 하지?
이를 위해 사용하는 것이 key의 hashCode다.
개념적으로는 다음과 같은 흐름이다.
key.hashCode()계산- hash 값을 보정
index = hash & (table.length - 1)table[index]선택 → 이 칸이 바로 버킷
즉,
hashCode의 역할은 이 key가 들어갈 버킷 번호를 정하는 것
버킷 하나에는 무엇이 들어 있을까?
이제 이 질문으로 자연스럽게 이어진다.
“그럼 버킷(table[index]) 안에는 뭐가 들어 있지?”
답은 Node 하나다.
static class Node<K,V> implements Map.Entry<K,V>Node<K,V>는 HashMap의 최소 저장 단위다
Node는 HashMap에 저장되는 엔트리 하나를 표현한다.
static class Node<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}Node 하나 = (key, value) 한 쌍
우리가 쓰는 코드
map.put("a", 1);는 내부적으로 보면
Node 객체 하나를 생성해서 버킷에 넣는 작업이다.
버킷 하나에 Node는 하나만 들어간다
이 부분에서 가장 많이 헷갈린다.
“버킷에 여러 Node가 들어간다”
이 말은 구조적으로 틀린 표현이다.
정확한 설명은 이렇다.
버킷(table[index])에는 Node 하나만 직접 들어간다.
그럼 여러 Node는 어떻게 저장되는가?
답은 Node 안에 있다.
Node<K,V> next;Node는 다음 Node를 가리키는 참조를 가지고 있다.
이 필드 때문에 구조가 이렇게 된다.
table[3]
↓
NodeA → NodeB → NodeCtable[3]에는 NodeA 하나- NodeA.next → NodeB
- NodeB.next → NodeC
즉,
버킷은 “Node 연결 구조의 시작점(head)” 역할을 한다.
이 방식을 체이닝(chaining) 이라고 부른다.
그래서 Node는 연결리스트인가?
정확히 말하면:
- Node 자체는 연결리스트가 아니다
- Node는 연결리스트의 노드
- 여러 Node가 next로 이어질 때 연결리스트 구조가 된다
이 구분을 놓치면 “HashMap은 배열인가 리스트인가” 같은 혼란이 계속 생긴다.
put()을 버킷 기준으로 다시 보면
map.put(key, value);버킷 관점에서 보면 흐름은 이렇다.
-
key의 hashCode로 버킷 index 결정
-
table[index]확인-
null → Node 하나 생성
-
Node 있음 →
- next를 따라가며 key.equals 비교
- 같으면 value 교체
- 없으면 Node를 뒤에 연결
-
중요한 점은 이것이다.
HashMap은 충돌을 피하려고 하지 않는다.
충돌을 처리할 수 있도록 설계되었다.
지금 단계에서 반드시 기억해야 할 문장
이 문장은 HashMap 이해의 기준점이다.
HashMap은 1차원 배열(table)을 가지고 있고, 각 배열 칸이 버킷이며, 버킷은 Node 연결 구조의 시작점이다.
