Java 프로그래밍 언어에서 기본적인 데이터 구조는 배열과 참조(가상 포인터)로 구성됩니다. 모든 데이터 구조는 이 두 가지 기본 요소를 통해 구현됩니다. HashMap은 배열과 연결 리스트의 결합체로, 데이터 구조에서 일반적으로 "연결된 해시"라고 불립니다.
배열이란?
Java는 동일한 타입의 요소를 저장하는 고정 크기의 연속형 컬렉션을 제공합니다. 이는 배열로 구현됩니다.
연결 리스트란?
연결 리스트는 물리적 저장 공간이 비연속적이며 순서가 없는 구조입니다. 데이터 요소의 논리적 순서는 연결 리스트 내부의 포인터를 통해 결정됩니다. 연결 리스트는 여러 노드로 구성되며, 실행 중에 동적으로 생성됩니다. 각 노드는 데이터 영역과 다음 노드 주소를 저장하는 포인터 영역으로 구성됩니다.
배열과 연결 리스트의 주요 차이점
- 배열의 요소 수는 고정되어 있으나 연결 리스트의 노드 수는 필요에 따라 조절 가능합니다.
- 배열은 정의 시 메모리 할당이 이루어지지만, 연결 리스트는 실행 중에 동적으로 메모리 요청이 발생합니다.
- 배열의 순서는 인덱스로 결정되고, 연결 리스트의 순서는 포인터를 통해 나타납니다.
- 변동성이 큰 리스트에서는 배열의 최대 길이를 사용할 경우 메모리 낭비가 발생합니다.
- 빈번한 삽입/삭제 작업이 필요한 경우 배열보다 연결 리스트가 더 효율적입니다. 배열은 삽입 시 후행 요소를 이동시키고, 삭제 시 전행 요소를 이동해야 하지만 연결 리스트는 포인터만 수정하면 됩니다.
HashMap의 데이터 구조
JDK 버전: 1.8
HashMap은 AbstractMap 추상 클래스를 상속하고 Map, Cloneable, Serializable 인터페이스를 구현하여 복제 및 직렬화가 가능합니다.
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 내용...
}
저장 내용: 키-값 쌍 데이터 구조: 배열 + 단일 연결 리스트 + 1.8 이후 추가된 레드-블랙 트리(배열 내 연결 리스트 길이가 8 이상일 경우 연결 리스트를 레드-블랙 트리로 전환)
핵심 파라미터:
- 초기 용량(기본값):
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16과 동일
- 배열 최대 용량:
static final int MAXIMUM_CAPACITY = 1 << 30;
- 로드 인자:
static final float DEFAULT_LOAD_FACTOR = 0.75f;
- 연결 리스트 → 레드-블랙 트리 전환 기준(연결 리스트 길이 >= 8):
static final int TREEIFY_THRESHOLD = 8;
- 트리화 최소 배열 용량 기준:
static final int MIN_TREEIFY_CAPACITY = 64;
원본 코드 분석:
1. HashMap 생성자
/* 기본 생성자: 초기 용량 16, 로드 인자 0.75 */
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 다른 필드는 기본값으로 설정
}
/* 단일 파라미터 생성자: 용량 지정, 로드 인자는 기본값 */
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/* 두 파라미터 생성자 */
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("잘못된 초기 용량");
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("잘못된 로드 인자");
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/* Map 파라미터 생성자 */
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
2. 문제 중심 코드 분석
위 생성자 코드를 통해 최대 용량의 사용 목적을 알 수 있습니다. 다음 질문에 대한 답을 찾아보세요:
- HashMap의 초기 용량이 16(2^4)인 이유는?
- 로드 인자가 0.75로 설정된 이유는?
- key의 hashCode와 equals 메서드 재정의 필요성은?
3. put 메서드 분석
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
3.1 hash(key)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = calculateHashCode(key)) ^ (h >>> 16);
}
3.2 putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
3.3 Node 노드
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
3.4 배열 확장: resize()
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0)
newCap = oldThr;
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
3.5 연결 리스트 ↔ 레드-블랙 트리 전환: treeifyBin()
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
HashMap의 초기 용량이 16인지 이유는? key의 해시 값을 통해 배열 인덱스를 계산할 때, 배열 크기-1과 AND 연산을 수행합니다. 배열 크기가 2의 거듭제곱일 경우, 해시 충돌 확률을 최소화할 수 있습니다. 예를 들어, 16의 배열 크기로 계산 시, 8과 9의 해시 값이 서로 다른 인덱스를 반환합니다.
加载因子(loaded factor)는 테이블에 저장된 요소 수 / 테이블 크기로 정의됩니다. 0.75의 로드 인자는 충돌 확률과 공간 활용도 사이의 균형을 맞추기 위해 선택되었습니다. 이는 통계학적 분포인 포아송 분포와 관련이 있습니다.
4. get() 메서드 분석
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
5. remove() 메서드 분석
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
6. 요약
- 1.7 버전: 배열 + 단일 연결 리스트, 1.8 버전: 연결 리스트 길이가 8 이상이면 레드-블랙 트리로 전환
- 1.7: 리사이징 시 해시 값을 다시 계산, 1.8: 해시 값 재계산 없이 AND 연산으로 인덱스 계산
- 1.7: 연결 리스트에 요소 삽입 시 머리에 추가, 1.8: 꼬리에 추가하여 동시성 확장 시 루프 방지