Map
컬렉션 프레임워크는 Map 인터페이스를 제공한다. Map을 구현한 클래스에는 HashMap, LinkedHashMap, TreeMap, EnumMap, AbstractMap 등이 있으나 가장 자주 쓰이는 HashMap, LinkedHashMap, TreeMap만 알아볼 예정이다(자바 내부 코드는 JDK 17 버전이다).
Map
Map은 중복을 허용하지 않는 키와 값의 쌍으로 이루어진 자료구조이다.
1. HashMap
HashMap은 Map 인터페이스를 구현한 컬렉션이다. HashMap은 해시 테이블을 기반으로 키-값 쌍을 저장하고 검색한다.
Hash
해시(Hash)는 데이터에 해시 함수를 적용한 결과값을 의미한다. 해시 테이블(Hash Table)은 키와 값을 저장하는 자료구조를 의미한다. 버킷(Bucket)은 해시 테이블 내부의 저장공간을 의미한다.
1.1. 기본 설정
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
return o instanceof Map.Entry<?, ?> e
&& Objects.equals(key, e.getKey())
&& Objects.equals(value, e.getValue());
}
}
}HashMap은 내부 클래스 Node의 객체를 해시 테이블로 활용한다. Node는 hash 값과 key, value, 그리고 next에 해시 충돌이 일어난 키-값 쌍을 저장한다.
1.2. 생성
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
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("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);
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) {
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
} else {
while (s > threshold && table.length < MAXIMUM_CAPACITY)
resize();
}
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
}HashMap은 HashMap 내부 코드에서 정의한 네 개의 생성자로 생성할 수 있다.
빈 값으로 생성: Threshold와 Load Factor에 기본값 설정
용량을 지정해서 생성: 지정한 용량에 따른 Threshold 값 설정 및 Load Factor 기본값 설정
용량과 Load Factor를 지정해서 생성
용량이 0보다 작거나 최대 용량인 2의 30제곱(1073741824)보다 크면 IllegalArgumentException
지정한 Load Factor가 0보다 작거나 NaN인 경우에도 역시 IllegalArgumentException
그 외의 경우 Threshold와 Load Factor에 지정값 설정
다른 맵을 복사해서 생성
생성자는 Load Factor를 기본값으로 지정하고 putMapEntries 메서드를 호출
putMapEntries 메서드는 다른 맵의 모든 키-값 쌍을 HashMap의 인스턴스에 추가
Load Factor와 Threshold를 비교해서 해시 테이블 크기를 설정
매개변수로 들어온 맵 값을 복사 후 집어넣음
Threshold와 Load Factor
Threshold는 해시 테이블을 조정하기 위한 임계값을 의미한다. Load Factor는 해시 테이블의 허용량을 의미한다. 자바의 HashMapd은 Threshold와 Load Factor를 비교해서 해시 테이블 크기 조정한다.
1.3. 추가
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
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;
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;
}
}HashMap에 값을 추가할 때는 put 메서드를 호출한다. put 메서드는 putVal 메서드를 호출한다. putVal 메서드는 해시 맵에 새로운 키-값 쌍을 추가하거나 기존 키에 대한 값을 수정한다.
먼저 해시 테이블이 null이거나 비어있는지 확인
비어있으면 resize() 메서드를 호출해 해시 테이블 크기 조정
새로운 키-값 쌍을 삽입할 버킷이 비어있는 경우
인덱스를 생성: 해시 함수를 사용해 키의 해시 코드를 테이블 크기로 나눈 나머지
newNode 메서드를 호출해 키-값 쌍에 대한 새 Node를 생성하고 버킷에 삽입
새로운 키-값 쌍을 삽입할 버킷이 차있는 경우
동일한 Node가 있는 경우
Node의 값을 수정
TreeNode인 경우
putTreeVal 메서드를 호출해서 TreeNode에 p값을 저장
버킷에 Node가 있는 경우
다음 Node가 없는 경우
Node 배열을 처음부터 끝까지 순회
newNode 메서드를 호출해서 버킷에 새로운 값 추가
TREEIFY_THRESHOLD를 초과한 경우
LinkedList를 TreeNode로 변환
반복문 종료
새로 삽입할 키와 일치하는 Node가 있는 경우
반복문 종료
키가 같은 Node가 이미 버킷에 존재하는 경우
기존 Node의 값을 변경해야 하면 새 값을 할당
afterNodeAccess 메서드 호출
size가 threshold보다 크면 resize() 메서드를 호출해 해시 테이블 크기 조정
HashMap의 충돌 처리와 성능
Java 8 이전까지 HashMap은 LinkedList로 충돌을 처리했다. 따라서 최악의 경우 복잡성이 O(n)으로 증가했다. Java 8 이후부터 LinkedList 대신 Red-Black Tree를 사용해서 충돌 항목을 저장한다. 이는 성능을 O(n)에서 O(log n)으로 향상시켰다. 위 코드에서 살펴본 것처럼 HashMap은 처음에 LinkedList를 사용한다. 그러다 항목 수가 임계값을 초과하면 LinkedList를 Red-Black Tree로 대체한다. 임계값(TREEIFY_THRESHOLD)의 기본값은 8이다.
1.4. 삭제
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
@Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
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;
}
}HashMap에 값을 삭제할 때는 remove 메서드를 호출한다. remove 메서드는 key 값과 함께 removeNode 메서드를 호출한다. remove 메서드는 주어진 해시 코드와 키로 매핑된 Node를 찾아서 제거한다.
해시 테이블이 null이 아니고 비어있지 않은 경우
동일한 Node가 있는 경우
삭제할 Node를 저장
다음 Node가 있는 경우
TreeNode인 경우
getTreeNode 메서드를 호출해서 삭제할 Node를 저장
TreeNode가 아닌 경우
Node 배열을 처음부터 끝까지 순회
새로 삽입할 키와 일치하는 Node가 있는 경우
삭제할 Node를 저장
반복문 종료
삭제할 Node를 찾았고 값 일치 여부를 판단해서 제거하는 경우
삭제할 Node가 TreeNode인 경우
removeTreeNode 메서드 호출해서 Node 삭제
삭제할 Node가 첫 번째 Node인 경우
첫 번째 Node를 삭제할 Node의 다음 Node로 변경
삭제할 Node가 첫 번째 Node가 아닌 경우
삭제할 Node의 이전 Node와 다음 Node를 연결
afterNodeRemoval 메서드를 호출해서 Node 삭제
null을 반환
2. LinkedHashMap
LinkedHashMap은 HashMap을 확장해서 구현한 컬렉션으로 순서를 가지는 HashMap을 생성한다.
2.1. 기본 설정
public class LinkedHashMap<K,V> extends HashMap<K,V>
implements Map<K,V> {
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
final boolean accessOrder;
}LinkedHashMap은 HashMap의 Node를 확장한 Entry 객체를 해시 테이블로 활용한다. Entry의 순서를 알 수 있는 before와 after, LinkedList의 처음과 끝을 의미하는 head와 tail이 추가되었다.
2.2. 생성
public class LinkedHashMap<K,V> extends HashMap<K,V>
implements Map<K,V> {
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
}LinkedHashMap은 LinkedHashMap 내부에서 정의한 다섯 개의 생성자로 생성할 수 있다.
빈 값으로 생성: HashMap과 같음
용량을 지정해서 생성: HashMap과 같음
용량과 Load Factor를 지정해서 생성: HashMap과 같음
용량, Load Factor, accessOrder를 지정해서 생성: 3과 같으나 추가적으로 accessOrder를 지정
다른 맵을 복사해서 생성: HashMap과 같으나 accessOrder의 기본값을 false로 설정
Access Order
Access Order는 Map의 원소에 접근한 순서를 유지하는 기능이다. accessOrder가 true인 LinkedHashMap은 원소에 접근할 때마다 해당 원소를 List의 끝에 추가한다. LinkedHashMap은 접근 순서를 유지하기 위해 추가 작업을 수행하므로 접근 시간이 느려질 수 있다.
2.3. 추가 및 삭제
HashMap과 동일하다.
3. TreeMap
TreeMap은 NavigableMap 인터페이스를 구현한 컬렉션이다. TreeMap은 Red-Black Tree를 기반으로 키-값 쌍을 저장하고 검색한다.
Red-Black Tree
Red-Black Tree는 자가 균형 이진 탐색 트리를 의미한다. Red-Black Tree의 성립 조건은 다음과 같다. 1. 모든 노드는 빨강 혹은 검정 2. 루트 노드는 검정 3. 모든 리프 노드는 검정 4. 빨강 노드의 자식은 검정(= 빨강 노드 연속 출현 불가) 5. 모든 리프 노드에서 Black Depth는 동일(= 리프 노드 -> 루트 노드 경로의 검정 노드 개수 동일)
3.1. 기본 설정
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
private transient int size = 0;
private transient int modCount = 0;
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
return o instanceof Map.Entry<?, ?> e
&& valEquals(key,e.getKey())
&& valEquals(value,e.getValue());
}
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public String toString() {
return key + "=" + value;
}
}
}TreeMap은 내부 클래스 Entry를 트리 노드로 활용한다. Entry는 트리를 구성하기 위해 key, value, left, right, parent, color를 저장한다.
3.2. 생성
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
public TreeMap() {
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException | ClassNotFoundException cannotHappen) {
}
}
}TreeMap은 TreeMpa 내부 코드에서 정의한 네 개의 생성자로 생성할 수 있다.
빈 값으로 생성: comparator를 null로 설정
comparator를 지정해서 생성: 지정된 comparator 설정
다른 맵을 복사해서 생성
comparator를 null로 설정
putAll 메서드 호출
다른 정렬된 맵을 복사해서 생성
정렬되어 있으므로 comparator를 지정
buildFromSorted 메서드 호출
Comparator
Comparator는 key 객체들의 정렬 순서를 지정하는 인터페이스다. Comparator를 명시적으로 지정하지 않으면 compareTo 메서드를 기반으로 정렬된다.
3.3. 추가
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
public V put(K key, V value) {
return put(key, value, true);
}
private V put(K key, V value, boolean replaceOld) {
Entry<K,V> t = root;
if (t == null) {
addEntryToEmptyMap(key, value);
return null;
}
int cmp;
Entry<K,V> parent;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else {
V oldValue = t.value;
if (replaceOld || oldValue == null) {
t.value = value;
}
return oldValue;
}
} while (t != null);
} else {
Objects.requireNonNull(key);
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else {
V oldValue = t.value;
if (replaceOld || oldValue == null) {
t.value = value;
}
return oldValue;
}
} while (t != null);
}
addEntry(key, value, parent, cmp < 0);
return null;
}
private void addEntryToEmptyMap(K key, V value) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
}
private void addEntry(K key, V value, Entry<K, V> parent, boolean addToLeft) {
Entry<K,V> e = new Entry<>(key, value, parent);
if (addToLeft)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
}
}TreeMap에 값을 추가할 때는 put 메서드를 호출한다. put 메서드는 Red-Black Tree의 조건에 맞게 값을 추가 후 트리를 재정렬한다.
3.4. 삭제
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
default boolean remove(Object key, Object value) {
Object curValue = get(key);
if (!Objects.equals(curValue, value) ||
(curValue == null && !containsKey(key))) {
return false;
}
remove(key);
return true;
}
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
}
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
p.left = p.right = p.parent = null;
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) {
root = null;
} else {
if (p.color == BLACK)
fixAfterDeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
}TreeMap에 값을 삭제할 때는 remove 메서드를 호출한다. remove 메서드는 Red-Black Tree의 조건에 맞게 값을 삭제 후 트리를 재정렬한다.
참고 자료
Last updated