이번 글에서는 코틀린에서 HashSet과 HashMap이 어떻게 빠른 속도로 데이터를 읽고, 수정하고, 삭제할 수 있는지 내부 구현을 보면서 이해해보도록 하겠습니다.
이 글을 통해서 HashSet과 HashMap의 내부 구현을 자세히 살펴보고, 코틀린에서 hashCode()와 equals() 메서드가 어떻게 활용되는지 알아갈 수 있습니다.
Kotlin의 equals와 hashCode 규칙
코틀린 클래스의 최상위(루트) 클래스인 Any 는 equals, hashCode, toString 3 개의 메서드를 가지고 있습니다.
equals의 주석에 따르면 다음과 같은 규칙을 가져야 합니다.
- 반사적: null이 아닌 값
x에 대해x.equals(x)는 true를 반환해야 한다. - 대칭적: null이 아닌 값
x,y에 대해x.equals(y)와y.equals(x)는 같은 값을 반환해야 한다. - 연속적: null이 아닌 값
x,y,z에 대해x.equals(y)와y.equals(z)가 true를 반환하면x.equals(z)도 true를 반환해야 한다. - 일관적: null이 아닌 값
x,y에 대해x.equals(y)를 여러 번 호출해도 (객체에 대한equals비교에 사용된 정보가 변경되지 않는 한) 항상 일관된 값을 반환해야 한다. - null과 같지 않음: null이 아닌 값
x에 대해x.equals(null)은 항상 false 를 반환해야 한다.
hashCode에 대한 규칙은 다음과 같습니다.
hashCode메서드가 동일한 객체에 대해 두 번 이상 호출될 때 객체에 대한equals비교에 사용된 정보가 수정되지 않은 경우 일관되게 동일한 정수를 반환해야 합니다.equals()메서드에 따라 두 객체가 동일한 경우 두 객체의hashCode()메서드를 호출한 반환 값은 동일한 정수여야 합니다.
equals를 직접 구현해야 하는 경우가 있을 수 있습니다.
- 기본 동작과 다른 동작을 해야 하는 경우
- 일부 프로퍼티만 비교하고 싶은 경우
- data class 로 선언하기 싫거나 비교하고 싶은 프로퍼티가 기본 생성자에 없는 경우
하지만 대부분의 상황에서는 위 규칙들을 모두 지키기 힘들기 때문에 직접 구현하는 것을 추천하지 않습니다.
해시 테이블
Map과 Set 자료구조는 요소를 추가하거나 추출할 때 동일한 요소가 이미 들어 있는지 확인해야 합니다.
배열이나 링크드 리스트를 사용해서 동일한 요소가 이미 들어 있는지 확인하려면 하나하나 모든 요소를 비교해야 하기 때문에 성능에 좋지 않습니다.
이때 사용할 수 있는 것이 해시 테이블입니다.
어떠한 값을 해시 테이블에 저장할 때 같은 값이라면 항상 같은 숫자를 할당하는 해시 함수를 사용하여 이를 기반으로 해시 테이블의 버킷이라는 공간에 값을 저장하게 됩니다. 이때 자바/코틀린에서 해시 함수는 위에서 설명한 hashCode() 입니다. hashCode() 주석에 설명된 규칙은 해시 함수의 일관성을 보장하기 위한 경고였던 것이죠.
버킷 수(해시 테이블 크기)는 제한되어 있기 때문에 해시 함수의 값을 그대로 키로 사용하는 것이 아니라 적절한 연산(보통 모듈러 연산)을 통해 얻은 인덱스로 저장하게 됩니다.
equals() 와 hashCode()는 같이 작성하라
data class Profile(
val firstName: String,
val lastName: String,
val age: Int,
val gender: Gender,
) {
override fun equals(other: Any?): Boolean {
if (other !is Profile) return false
return firstName == other.firstName && lastName == other.lastName
}
}
위 코드처럼 data class 를 작성하고 equals() 만 구현했을 때 hashCode() 도 구현하라는 경고가 뜹니다.
hashCode() 2번째 주석에는 두 객체의 equals() 값이 동일하다면 hashCode() 값도 동일해야 한다고 되어 있습니다.
다음과 같이 hashCode() 를 구현해줬습니다.
data class Profile(
val firstName: String,
val lastName: String,
val age: Int,
val gender: Gender,
) {
override fun equals(other: Any?): Boolean {
if (other !is Profile) return false
return firstName == other.firstName && lastName == other.lastName
}
override fun hashCode(): Int {
return firstName.hashCode() * 31 + lastName.hashCode()
}
}해시 함수를 구현할 때 관례적으로 31이라는 숫자를 주로 사용합니다. 31이라는 수가 주로 사용되는 이유는 여러 썰이 있으니 직접 찾아보셔도 좋을 듯 합니다. (참고: https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier)
HashSet은 HashMap으로 구현되어 있다
이제 Kotlin 의 HashSet과 HashMap에 대해 좀 더 자세히 알아보겠습니다.
코틀린에서 사용하는 ArrayList, LinkedHashMap, HashMap, LinkedHashMap, HashSet은 자바의 컬렉션을 그대로 사용하고 있습니다.
이 중 HashSet의 구현을 살펴보겠습니다.
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
@java.io.Serial
static final long serialVersionUID = -5024744406713321676L;
transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
// ...
}HashSet 은 사실 내부적으로 HashMap을 사용하고 있었습니다. key-value 구조에서 value를 PRESENT로 고정하고 key 부분만 사용하고 있는 것이죠.
HashMap의 내부 구현
HashMap 내부 구현을 살펴보며 전달하고 싶은 내용은 HashMap이 어떻게 해시 충돌을 해결하고, 최적화하는지 입니다.
이런 내용들은 주석에도 친절하게 설명되어 있지만 내용이 상당히 자세하고 길기 때문에 주석을 요약한 것을 보며 빠르게 파악하고 코드로도 살펴 보겠습니다.
HashMap 주석 요약
- 기본 작동 원리:
HashMap은 보통 해시 테이블로 동작하지만, 특정 버킷의 데이터가 많아지면 이 버킷을 트리 구조로 변환하여 탐색 속도를 높입니다. - 트리 버킷의 정렬: 트리 버킷에서는 요소들이
hashCode순으로 정렬됩니다. 만약Comparable을 구현한 요소들이 동일한 해시 값을 가지면compareTo메서드로 정렬을 결정합니다. - 메모리 효율성: 트리 노드는 일반 노드보다 메모리를 많이 차지하므로, 노드 수가 충분히 많은 경우에만 트리로 변환됩니다. 노드 수가 줄어들면 다시 일반 버킷으로 전환됩니다.
- 버킷 내 노드 분포: 무작위 해시 코드의 경우, 버킷 내 노드 개수는 포아송 분포를 따릅니다. 이는 충돌이 적은 환경에서 효율적인 메모리 사용을 보장합니다.
- 구조 유지: 삽입, 삭제, 접근 시
LinkedHashMap과 같은 하위 클래스와의 호환성을 위해 특정 후크 메서드를 사용해 구조가 안정되도록 합니다.
HashMap (생성자)
여러 생성자가 있지만 가장 raw한 생성자를 살펴보겠습니다.
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}initialCapacity(초기 버킷 사이즈)와 loadFactor(버킷이 얼마나 꽉 찼을 때 resize 할 지의 수치)를 받아 초기 설정을 하는 역할을 합니다.
initialCapacity는 MAXIMUN_CAPACITY를 넘을 수 없는데 이 값은 2의 30승 입니다. 만약 버킷이 2의 30승 개가 넘은 경우엔 해시 충돌 확률이 높아집니다. 기본 값인 DEFAULT_INITIAL_CAPACITY는 2의 4승인 16 입니다.
loadFactor의 기본 값인 DEFAULT_LOAD_FACTOR은 0.75 입니다. 이 말은 해시 테이블의 75%가 찼을 때 버킷 수를 2배로 늘린다는 의미입니다. 예를 들어 현재 버킷 사이즈가 16이고, 12개의 요소가 들어가면 버킷 사이즈를 두 배 늘립니다.
loadFactor의 수가 낮으면 충돌 확률이 낮아지겠지만 그만큼 자주 메모리를 더 사용할 수 있고, 반대로 높으면 메모리 효율이 높아지지만 충돌 가능성이 높아져 성능이 떨어질 수 있습니다.
get()
public V get(Object key) {
Node<K,V> e;
return (e = getNode(key)) == null ? null : e.value;
}final Node<K,V> getNode(Object key) {
// 1) 테이블과 기본 변수 초기화
Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & (hash = hash(key))]) != null) {
// 2) 첫 번째 노드 검사
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 3) 첫 번째 노드에 다음 노드가 있을 때 (해시 충돌로 인한 체이닝)
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 4) 링크드 리스트 순회 (트리가 아닌 경우)
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 5) 노드가 없는 경우 null 반환
return null;
}주어진 key로 값을 탐색해 반환하거나 테이블에 없으면 null을 반환하는 메서드 입니다.
3번에서 TreeNode 인지 확인하고 있는 부분이 있습니다. 주석에 설명되어 있는 것처럼 특정 버킷의 데이터가 많아지면 이 버킷을 트리 구조로 변환하는데, 탐색 과정에서 버킷이 어떤 형태로 되어있는지 확인하는 걸 볼 수 있습니다.
자세히 살펴보겠습니다.
- 테이블과 기본 변수 초기화
Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & (hash = hash(key))]) != null) {tab = table로 해시 테이블을 참조합니다.table은 HashMap 내부의 해시 테이블 객체입니다.n = tab.length로 버킷 수를 구합니다.hash = hash(key)로 키의 해시 값을 구합니다.(n — 1) & hash로 해시 값과 버킷 수를 비트 연산하여 배열의 인덱스를 구합니다.- 위에서 계산된 인덱스의 첫 번째 노드를
first에 할당합니다.
위 조건문에서 table이 null 이 아니고, 길이가 0보다 크고, 해당 버킷에 노드가 존재하는 경우에 다음 코드를 실행합니다.
2. 첫 번째 노드 검사
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;- 첫 번째 노드의 해시 값이
hash와 같고, 노드의 키가 찾고자 하는key와 동일한지 체크합니다. - 위 조건에 만족하면 첫 번째 노드
first를 바로 반환합니다.
3. 첫 번째 노드에 다음 노드가 있을 때 (해시 충돌로 인한 체이닝)
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);first.next가null이 아니면 해시 충돌로 인해 체이닝이 발생한 경우입니다.- 첫 번째 노드가
TreeNode타입이면, 버킷이 트리 구조로 변환된 상태입니다. 이때getTreeNode(hash, key)메서드를 호출해서 트리 내에서 노드를 찾습니다.
4. 링크드 리스트 순회 (트리가 아닌 경우)
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);- 트리 구조가 아니라면, 링크드 리스트를 순회하며
key와 일치하는 노드를 찾습니다. - 각 노드의 해시 값과 키가
key와 일치하는지 확인하고, 조건을 만족하면 해당 노드를 반환합니다. - 일치하는 노드가 나올 때까지 계속
next노드로 이동하며 찾습니다.
5. 노드가 없는 경우 null 을 반환
return null;- 링크드 리스트를 끝까지 순회해도 일치하는 노드가 없다면
null을 반환합니다.
정리하자면 다음과 같습니다.
- 주어진 키의 해시 값을 사용해 버킷 인덱스를 구하고 첫 번째 노드를 검사
- 첫 번째 노드가 일치하면 반환하고, 그렇지 않으면 다음 노드를 탐색 (링크드 리스트인지 트리 구조인지 확인하여 적절한 방식으로 탐색)
- 값을 찾으면 반환하고, 끝까지 못 찾으면
null을 반환
put()
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 1) 테이블 초기화 및 리사이징
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 2) 해당 인덱스에 노드가 없는 경우
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 3) 해당 인덱스에 노드가 이미 있는 경우
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 4) TreeNode로 처리해야 하는 상황
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 5) 링크드 리스트에 새로운 노드 추가 (TreeNode가 아닌 경우)
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 6) 기존 키가 있을 경우 값 업데이트
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 7) 새로운 노드 삽입 후 크기 조정
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
// 8) 반환
return null;
}주어진 키와 값을 삽입하는 메서드입니다. 해시 충돌 처리, 트리 구조로 변환, 해시 테이블 확장 등의 로직을 포함하고 있어서 생각보다 복잡한 메서드 입니다.
putVal 의 파라미터 중 2개의 파라미터가 생소합니다. 그 의미는 다음과 같습니다.
onlyIfAbsent: 기존 키가 있으면 값을 덮어쓰지 않도록 하는 플래그evict: LinkedHashMap에서 사용하는 플래그. 해시 테이블을 비우는 작업에 영향을 줌
마찬가지로 자세히 살펴보겠습니다.
- 테이블 초기화 및 리사이징
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;- 해시테이블(
table) 이 초기화되지 않았거나 길이가 0이면resize()메서드를 통해 테이블을 초기화하거나 크기를 조정합니다. (resize()메서드도 꽤 복잡한 로직을 가지고 있기 때문에 밑에서 별도로 다루겠습니다)
2. 해당 인덱스에 노드가 없는 경우
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);- 해시 값(
hash)과n — 1간의 비트 연산을 통해 저장할 인덱스i를 구합니다. tab[i]가 비어있으면, 해당 인덱스에 새 노드(newNode)를 생성해 할당합니다. 이 경우 링크드 리스트나 트리 없이 단일 노드로 저장됩니다.
3. 해당 인덱스에 노드가 이미 있는 경우
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;- 해시 충돌이 발생한 경우입니다.
- 해당 노드의 해시와
hash가 동일한지 확인하고, 같다면 기존 노드p를e에 할당합니다.
4. TreeNode로 처리해야 하는 상황
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);p가TreeNode인 경우, 이 버킷이 트리 구조이므로putTreeVal메서드를 통해 트리 노드로 삽입합니다.
5. 링크드 리스트에 새로운 노드 추가 (TreeNode가 아닌 경우)
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;
}
}TreeNode가 아닌 경우 링크드 리스트를 순회하며 노드e를 찾습니다.- 노드가 끝날 때까지 키를 찾지 못했다면, 새로운 노드를 링크드 리스트의 마지막에 추가합니다.
- 리스트 길이가
TREEIFY_THRESHOLD에 도달하면treeifyBin메서드를 통해 리스트를 트리 구조로 변환합니다.
6. 기존 키가 있을 경우 값 업데이트
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}- 일치하는 노드
e가 이미 있는 경우, 기존 값을 저장하고 새 값으로 업데이트 합니다. onlyIfabsent가false이거나oldValue가null인 경우에만 값을 갱신합니다.- 갱신이 완료되면
afterNodeAccess(e)를 호출하여 후처리하고, 기존 값을 반환합니다.
7. 새로운 노드 삽입 후 크기 조정
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);- 삽입이 완료되면
modCount를 증가시켜 구조적 변경을 기록합니다. size가threshold를 초과한 경우,resize()메서드를 통해 해시 테이블을 확장합니다.afterNodeInsertion(evict)는LinkedHashMap에서 오버라이드되어 사용되는 메서드로, 노드 삽입 후 추가 처리를 수행합니다.
8. 반환
- 값이 새로 추가되었을 때는
null을 반환합니다.
정리하자면 다음과 같습니다.
HashMap에 키-값 쌍을 삽입하고 필요하면 테이블 크기 확장.- 키 충돌이 없을 경우 새로운 노드를 바로 추가, 충돌이 발생하면 링크드 리스트나 트리 구조에 따라 추가.
- 리스트 길이가 일정 임계치를 넘으면 트리로 변환하여 성능을 최적화.
- 추가가 완료되면
threshold초과 여부를 확인하고, 초과 시 테이블을 리사이즈.
remove()
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
// 1) 해시 테이블 접근 및 초기화
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) {
// 2) 첫 번째 노드 검증
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;
// 3) 링크르 리스트 / 트리 탐색
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);
}
}
// 4) 값 일치 여부 확인 및 노드 제거 준비
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 5) 노드 제거
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;
// 6) 구조 변경 및 후처리
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
// 7) 노드가 없으면 null 반환
return null;
}주어진 키에 해당하는 노드를 해시테이블에서 제거하는 함수입니다.
이번에도 역시 생소해보이는 matchValue, movable 두 파라미터만 간단히 살펴보겠습니다.
matchValue: true일 경우 값도 일치해야만 노드를 제거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) {table이null이 아니고, 길이가 0보다 크면서 인덱스(index)의 노드p가null이 아니면 제거 작업을 시작. 즉, 제거할 값이 있는 경우 제거- 인덱스는
(n — 1) & hash를 통해 해시 값을 기반으로 계산
2. 첫 번째 노드 검증
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;- 버킷의 첫 번째 노드
p가 일치하는 키를 가지고 있는지 확인 hash와 키가 모두 일치하면node에p를 할당
3. 링크드 리스트 / 트리 탐색
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);
}
}- 첫 번째 노드에서 찾지 못한 경우 다음 노드(
e = p.next) 확인 p가TreeNode타입이면getTreeNode()를 통해 노드 탐색- 그렇지 않으면 링크드 리스트를 순회하며 노드 탐색
4. 값 일치 여부 확인 및 노드 제거 준비
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {- 일치하는 노드가 존재하고,
matchValue가true일 때 값도 일치하는 경우 노드 제거 준비
5. 노드 제거
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;- 제거할 노드가
TreeNode타입이면removeTreeNode를 통해 트리에서 제거 - 링크드 리스트일 때, 제거할 노드가 첫 번째 노드인 경우(
node == p) 해당 인덱스에 다음 노드를 연결 - 첫 번째 노드가 아닌 경우 이전 노드의 next(
p.next)를 제거할 노드의 next 로 변경
6. 구조 변경 및 후처리
++modCount;
--size;
afterNodeRemoval(node);
return node;modCount를 증가시켜HashMap의 구조적 변경을 기록size를 감소시켜 요소 개수 업데이트afterNodeRemoval(node)메서드를 통해 노드 제거 후 후처리 작업 수행- 제거된 노드 반환
7. 노드가 없는 경우 null 반환
return null;- 일치하는 노드가 없는 경우
null반환
정리하자면 다음과 같습니다.
- 탐색 → 제거 → 반환 단계를 통해 값을 제거하는 동작을 수행합니다.
- 탐색: 주어진 해시 값을 통해 해시 테이블에서 노드를 찾고, 첫 번째 노드를 확인. 만약 첫 번째 노드와 일치하지 않으면 링크드 리스트나 트리를 순회하며 노드를 찾는다.
- 제거:
TreeNode라면 트리 구조에서 제거하고, 링크드 리스트면 노드를 연결 해제 - 반환:
HashMap의 변경 사항을 반영하고, 제거된 노드 반환
resize()
해시 테이블의 크기를 늘리고 재배치하는 역할을 하는 메서드입니다.
주로 해시 충돌이 많아지거나, 특정 임계값을 초과한 경우 호출됩니다.
final Node<K,V>[] resize() {
// oldTab: 기존 해시 테이블
Node<K,V>[] oldTab = table;
// oldCap: 기존 테이블의 용량
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// oldThr: 기존 임계값
int oldThr = threshold;
// newCap: 새로운 테이블의 용량, newThr: 새로운 임계값
int newCap, newThr = 0;
// 1) 새로운 용량 및 임계값 계산
// 1-1) 현재 용량이 있는 경우
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; // double threshold
}
// 1-2) 초기화 상태인 경우
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 1-3) 임계값이 계산되지 않은 경우
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 2) 새로운 테이블 생성
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 3) 기존 요소 재배치
// 3-1) 기존 테이블(oldTab)에 요소가 있는 경우
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);
// 3-2) 링크드 리스트 재배치
else { // preserve order
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;
}- 새로운 용량 및 임계값 계산
1–1. 현재 용량이 있는 경우
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; // double threshold
}oldCap >= MAXIMUM_CAPACITY일 때 임계값을 정수 최대 크기로 지정하고 기존 테이블 반환- 그렇지 않으면, 기존 용량을 두 배로 증가(
newCap = oldCap << 1)시키고 임계값도 두 배로 증가(newThr = oldThr << 1)
1–2. 초기화 상태인 경우
else if (oldThr > 0)
newCap = oldThr;
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}- 기존 임계값(
oldThr)이 설정된 경우 이 값을 새로운 용량으로 사용 - 기존 임계값이 없으면
DEFAULT_INITIAL_CAPACITY와DEFAULT_LOAD_FACTOR를 이용해 새로운 임계값 계산
1–3. 임계값이 계산되지 않은 경우
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;loadFactor를 기반으로 새로운 임계값 계산- 계산된 임계값이 최대 용량(
MAXIMUM_CAPACITY)을 초과하면 정수 최대 크기로 지정
2. 새로운 테이블 생성
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;- 새로운 용량(
newCap)을 가진 해시 테이블(newTab)을 생성하고 이를table로 설정
3. 기존 요소 재배치
3–1. 기존 테이블(oldTab)에 요소가 있는 경우
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);- 각 버킷(
oldTab[j])을 순회하며 요소(e)가 있는 경우 재배치 시작 - 단일 노드인 경우, 새로운 인덱스를 계산(
e.hash & (newCap — 1))하여 새로운 테이블에 그대로 복사 - 트리인 경우,
split()메서드를 통해 재배치
3–2. 링크드 리스트 재배치
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;
}
}- 두 개의 버킷 정의 (
loHead,hiHead) (e.hash & oldCap) == 0← 해시 값의 특정 비트를 통해 두 그룹으로 분할loHead: 해당 비트가 0인 노드. 새 테이블의 기존 인덱스에 배치 (newTab[j])hiHead: 해당 비트가 1인 노드. 새 테이블의j + oldCap인덱스에 배치
위 과정을 통해 새로운 버킷에 노드를 균등하게 분배할 수 있습니다.
마무리
지금까지 Map 에서 수행할 수 있는 기본 작업인 get(), put(), remove() 에 대해 살펴봤습니다. (추가로 resize() 까지)
이 과정에서 HashMap은 기본적으로 해시 충돌이 발생하면 체이닝 방식을 통해 충돌을 해결하며, 버킷의 크기에 따라 링크드 리스트, 트리 구조 등으로 변환하여 데이터를 관리하는 것을 확인할 수 있었습니다.
또한 탐색, 삽입, 삭제 등의 과정에서 equals()와 hashCode() 를 적극적으로 사용하는 것을 확인할 수 있었습니다.
추가로 다음 질문에 스스로 답을 해보세요.
hashCode()와equals()의 차이점은 무엇인가요?hashCode()와equals()를 둘 다 오버라이드 해야 하는 이유는 무엇인가요?hashCode()가 항상 같은 값을 반환하면 어떻게 되나요?HashMap에서 값을 탐색할 때 일반적인 경우와 최악의 경우 시간 복잡도는 무엇인가요?HashMap은 해시 충돌 발생시 어떻게 해결하나요?HashMap의 해시 테이블 공간이 부족하면 어떤 처리가 이루어지나요?
다음 글에서는 HashMap 의 Tree 구조인 TreeNode 에 대해 좀 더 자세히 살펴보겠습니다.
긴 글 읽어주셔서 감사합니다.
