1. 서론
항해 취업코스 기술 질문 예시로 Java Map 내부구현을 추측해보는 문제를 받았다.
Map은 키-밸류를 가지는 자료형으로 키는 고유값이며, 밸류는 중복이 허용된다.
그리고 Map은 순서를 유지하지 않는다.
Map의 구현체는 많지만, 익히 알려진 것은
- HashMap
- LinkedHashMap
- TreeMap
정도다.
특히 HashMap을 위주로 코드를 보려고 한다.
2. 코드
1. Map의 메서드들
public class MapService implements Map{
@Override
public Set keySet() {
return null;
}
@Override
public Collection values() {
return null;
}
@Override
public Set<Entry> entrySet() {
return null;
}너무 많아서 줄였다.
Map 구현체를 만든다면 기본적으로 CRUD 역할을 하는 put, putAll, get, remove, clear이 존재하고, size, containsKey, containsValue, isEmpty 등 Map의 상태를 확인하는 메서드도 존재한다.
그리고 모든 Key를 Set 자료형에 담아주는 KeySet, 모든 value를 보여주는 values, 모든 Key,Value 쌍을 Entry로 보여주는 entrySet 메서드도 존재했다.
주의점은 entrySet의 return 자료형만 체크해서 사용하면 되겠다.
entrySet에서 볼 수 있듯, Map에서는 Key-Value를 Entry 자료형으로 보관하는 것으로 추측할 수 있다.
그리고 코드를 보면서, compute, merge, replace 등 메서드를 사용할 때, 기존의 Value가 null이 아니고, newValue가 null이라면 key가 삭제된다는 점이 특이했다. 해당하지 않는다면, newValue를 oldValue 대신 키에 덮어씌운다.
2. HashMap
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라는 값을 받을 수 있다.
어...? HashMap을 만들 때 입력한 적이 없는데???
HashMap도 기본적으로 Hash를 가진 자료형이기 때문에 충돌을 관리하기 위해서 크기값을 가진다.
initialCapacity는 초기 HashMap의 크기이며, loadFactor은 HashMap의 어느 정도 데이터가 찼을 때, 크기를 키울지에 대한 값이다.
디폴트 값은 initialCapacity 1 << 4(16), loadFactor 0.75f로 설정되어 있고, HashMap<>(32, 0.80f)으로 설정할 수 있다.
TREEIFY_THRESHOLD라는 변수가 존재했다. Treeify? 결론부터 말하면 해시 충돌이 일어나면 버킷을 체이닝 방법과 LinkedList로만 관리했었는데 탐색에 O(N)의 시간이 걸리다보니, Java8부터 버킷의 key가 늘어나면, Red-Black-Tree를 통해 인덱스를 관리하게 하여 성능 최적화를 노렸다고 한다. Map은 보통 성능 때문에 사용하는데, 그 성능을 조금이라도 더 최적화하긴 노력인거 같다.
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);
}
}실제 treeify 코드. 임계값이 넘지 않는다면 그냥 resize를 하고, 아니라면 treeNode로 바꾼다.
임계값이 6과 8인 이유는 너무 적은 데이터는 사실 시간 차이가 그렇게 나지 않고, 유의미한 차이를 두려면 완전 이진트리를 완성하고 나서부터라고 한다.(1+2+4)
여기서 tab은 기존 버킷을 관리하던 linkedList다. 참고로 resize할 때, 새로운 배열에 재해싱하는 과정을 거치는 것 같다. 그리고 Capacity값은 2배가 되는 것으로 추측한다.(기존 Capacity << 1) 코드를 보여주고 싶지만 너무 길고... 들여쓰기가 많아서 보기 힘들다. 사실 treeifyBin도 무슨 메서드인지 정확하게 이해하기 힘들다 ㅠㅠ
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) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}마지막으로 put 메서드만 뜯어보자.
- 테이블이 비었다면 resize를 수행한다. (새로운 HashMap 생성 및 초기화)
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;- 해당 키의 해시코드를 참고해 버킷 인덱스를 찾고, 인덱스가 비었다면 노드를 삽입한다. 이 if문을 통과하지 못했다면 해시 충돌이 난 것이다.
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);3-1. 충돌이 났지만, 해당 버킷 인덱스에 해시 값이 key인지 확인한다.
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;3-2. Treeify 되었는지 확인한다. 되었다면 putTreeVal로 넘긴다.
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);3-3. 3-1, 3-2가 아니라면 연결 리스트 끝에 새 노드를 추가한다. 트리 임계점을 넘는다면 treeify를 진행한다.
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;
}3-4. 만약 충돌이 존재했다면, 값을 갱신한다.
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}- HashMap의 크기를 증가 시킨다.
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;afterNodeInsertion같은 메서드가 보이는데 LinkedHashMap을 위한 메서드들이다. 하위 클래스나 따로 정의해줄 수 있을 것 같다. LinkedHashMap에서는 해당 메서드에서, LinkedList로 key의 순서를 보장하기 위한 로직이 들어간다.
3. 마치며
와....
하면서 HashTable 코드도 봤는데 @Synchronized가 있더라 그런데 왜 HashMap에는 없지?
틀린 것이 있다면 알려주시면 감사하겠습니다.
treeify 임계점? : https://stackoverflow.com/questions/42422469/why-does-a-hashmap-contain-a-linkedlist-instead-of-an-avl-tree
hashMap : https://velog.io/@gkdbssla97/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-HashMap-%EB%82%B4%EB%B6%80-%EB%8F%99%EC%9E%91-1-feat.-Java
hash 관련 : https://siahn95.tistory.com/86
조금 더 볼만한 주제(ConcurrentHashMap) : https://velog.io/@alsgus92/ConcurrentHashMap%EC%9D%98-Thread-safe-%EC%9B%90%EB%A6%AC
