HashMap - 자바코드 뜯어보기(연결리스트 중심으로)
자바에서 해시맵은 노드의 배열로 되어있는 자료구조이다.
자료를 저장할 때에는 데이터를 해싱이라는 작업을 통해 정수로 반환하고,
해당하는 인덱스의 배열에 저장한다.
마찬가지로 조회할 때에도 해싱을 통해 반환된 인덱스로 빠르게 자료를 조회할 수 있다.
여기서 주의해야할 점이 2가지 있다.
1. 해시맵 사용 시 주의 사항
첫번째는 해시값은 중복이 가능하다는 점이다. 이를 해시충돌 이라고 한다.
따라서 다른 데이터여도, 해시값이 같으면 같은 인덱스에 노드로써 저장된다. 기본적으로 연결리스트 형식으로 저장되지만, 크기가 커지면 트리노드형식으로 저장된다.
두번째는 같은 상태를 가진 동일한 객체라고 해도 참조가 다르다면, 다른 해시코드를 반환한다는 점이다.
TmpObject object1 = new TmpObject(1);
TmpObject object2 = new TmpObject(1);
System.out.println("object1 = " + object1.hashCode());
System.out.println("object2 = " + object2.hashCode());
---
object1 = 793589513
object2 = 824909230
이것이 왜 중요한것일까?
이것이 중요한 이유는 해시맵의 내부 배열 저장 인덱스, 즉 버킷 인덱스는,
키값의 해시코드값에 달려있기 때문이다.
최소 jdk1.8 이후 객체의 해시코드(Object.hashCode)는 어떠한 규칙에 의해 만들어지는것이 아니라,
로컬-스레드 난수로 이루어진 id값으로 생성된다.
그렇기에 우리가 다른곳에서 저장한 값을 불러오고자 할때, 같은 벨류를 가진 객체를 이용해서 찾는다고해도,
결국은 새로운 객체이기 때문에 새로운 해시코드를 할당받는다.
그렇기에 우리는 같은 밸류라면 같은 해쉬코드를 반환한다는 약속을 해야하는 것이다.
그것이 흔히 이야기하는 hashCode 메서드를 오버라이드 하라는 의미이다.
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
TmpObject tmpObject = (TmpObject) o;
return num == tmpObject.num;
}
@Override
public int hashCode() {
//Object.hashCode와는 다르게, 객체 데이터 값을 이용해 해시값을 지정한다.
return Objects.hash(num);
}
TmpObject object1 = new TmpObject(1);
TmpObject object2 = new TmpObject(1);
//오버라이드한 hashCode값을 반환한다.
System.out.println("object1 = " + object1.hashCode());
System.out.println("object2 = " + object2.hashCode());
// 본래 hashCode값(Obejct.hashCode)을 반환한다.
int OriginalObject1Hash = System.identityHashCode(object1);
int OriginalObject2Hash = System.identityHashCode(object2);
System.out.println("OriginalObject1Hash = " + OriginalObject1Hash);
System.out.println("OriginalObject2Hash = " + OriginalObject2Hash);
---
object1 = 32
object2 = 32
OriginalObject1Hash = 664223387
OriginalObject2Hash = 824909230
그렇다면 equals는 왜 따라서 오버라이드 해야 하는 것일까?
해시코드만 동일하게 고정시키고, 저장, 조회한다면, equals는 왜 필요할까?
그것은 해시맵의 구조 자체가 한 인덱스에 하나의 데이터만 들어가는 구조가 아니기 때문이다.
즉, 해시 충돌이 발생한 인덱스의 경우, 정확히 어떤값을 찾아야할지 비교해야하므로,
우리는 equlas를 오버라이드하여, 해시맵이 보통 타입, 벨류들을 비교 후 동등한지 아닌지를
비교하여 반환하게 한다.
이것이 equals, hashCode 메서드가 해시관련 자료구조에서 오버라이딩해야하는 이유이다.
2. 멤버 인스턴스
다음은 멤버 인스턴스를 살펴보자.
2-1. 상수
DEFAULT_INITIAL_CAPACITY : 최초로 값을 넣을 때 생성되는 맵 내부 배열의 크기이다. 주석을 보면 2의 제곱만 가능하다고 되어있는데, 이것은 이후에 소개 할 resize 메서드와 관련이 있다.
MAXIMUM_CAPACITY : 해시맵 으로써 가질수 있는 길이의 최대 크기이다.
DEFAULT_LOAD_FACTOR : 배열의 크기를 늘리는 기준이다.
TREEIFY_THRESHOLD : 배열에서 한 버킷 안에 연결되어있는 노드가 연결될 수 있는 최대 수, 내부배열의 자료구조가 링크드리스트에서 트리맵으로 변경되는 기준1
UNTREEIFY_THRESHOLD : 트리노드에서 다시 배열로 전환되는 버킷 사이즈에 대한 값이다.
MIN_TREEIFY_CAPACITY : 배열의 길이를 의미하며, 내부배열의 자료구조가 링크드리스트에서 트리맵으로 변경되는 기준2
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
2-2 변수
/**
* The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some operations to allow * bootstrapping mechanics that are currently not needed.) */
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
* */
transient Set<Map.Entry<K,V>> entrySet;
/**
* The number of key-value mappings contained in this map.
* */
transient int size;
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
* * @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
/**
* The load factor for the hash table.
* * @serial
*/
final float loadFactor;
3. 기본 생성자
Stack, ArrayDeque와는 다르게, 초기화 할 때 내부 배열의 크기를 정하지 않는다.
/**
* Constructs an empty {@code HashMap} with the default initial capacity
* (16) and the default load factor (0.75). */public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
4. 삽입
해시맵에서는 객체의 해시값 외에 자체적인 내부 해시값을 객체에 부여하며,
해시충돌 수, 배열의 크기에 따라 연결리스트에서 트리노드로 변환되기도 하며, 반대의 경우도 있다.
이 글에서는 연결리스트 섹션을 중심으로 정리하고자 한다.
각각의 파라미터는 다음과 같다.
4-1. put
put 메서드에서는 hash라는 메서드를 통해 객체의 해시코드를 해시맵에 사용할수 있게 내부용 해시코드를 생성한다.
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
4-2. putVal
hash : 내부용 해시코드
key : 키
value : 값
onlyIfOnlyAbsent : 참이면, 동일한 키의 데이터가 이미 저장되어있을 때 값을 덮어 씌우지 않는다.
evict : LinkedHashMap에서 사용되며, 해시맵 자체에서는 단독으로 사용되지 않는다.
/**
* Implements Map.put and related methods. * * @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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);
else {
Node<K,V> e; K k;
//3
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);
//4
else {
for (int binCount = 0; ; ++binCount) {
//4-1
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//4-2
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//5
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);//미구현
return oldValue;
}
}
//6
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);//미구현
return null;
}
(1)
내부 배열이 생성되지 않은 경우에는 resize 메서드를 이용하여 내부 배열을 초기화한다.
//1
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
(2)
해당 인덱스가 null 이라면, 데이터를 저장한다.
//2
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
(3)
해당 인덱스의 첫번째 키가 저장하려는 키와 동일하다면, 저장하려는 노드를 e로 할당한다
//3
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
(4)
버킷의 노드를 순회한다.
//4
else {
for (int binCount = 0; ; ++binCount) {
//4-1
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//4-2
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
(4-1)
현재 노드의 다음노드가 없다면
그 다음노드로 현재 노드를 추가한다.
만약 특정 버킷에서 연결 리스트의 길이가 `TREEIFY_THRESHOLD` (기본값은 8)를 초과하면, 연결 리스트는 트리 구조로 변환된다. 이는 버킷 내부에 있는 노드들의 총 수에 기반한다.
//4-1
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
(4-2)
만약 버킷에서 동일한 키의 노드를 찾으면 루프를 벗어난다.
//4-2
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
(5)
이미 키가 존재한다면, 기존 키의 값을 반환하고, 현재 값으로 덮어쓴다.
//5
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
(6)
현재 해쉬맵에 저장된 데이터 수량이 임계값을 넘어가면 resize를 호출한다.
//6
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
4-3. 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;
//1
if (oldCap > 0) {
//1-1
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//1-2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//2
//2-1
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//2-2
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//3
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//4
@SuppressWarnings({"rawtypes","unchecked"})
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 { // 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) {
//1-1
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//1-2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
(1-1)
기존의 내부 배열이 MAXIMUM_CAPACITY 이상이면
저장가능한 데이터 수량(threshold)을 최대치로 변경하고 그대로 반환한다.
(1-2)
내부 배열을 2배로 늘린 값이 MAXIMUM_CAPACITY 보다 작고,
기존의 내부 배열이 DEFAULT_INITIAL_CAPACITY 이상이면
newThr(데이터 최대 저장 수) 또한 기존의 oldThr의 2배로 늘린다.
(2)
//2
//2-1
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//2-2
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
(2-1)
주석에는 '최초 용량이 threshold에 할당되어 있다' 라고 적혀있다.
언뜻 조건을 보면 이상하게 느껴진다. (1)의 oldCap이 0 이하이고, oldThr 가 0보다 큰 경우는 뭘까?
//2-1
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
답은 생성자에 있었다.
(1)을 보면, 최초 내부 용량을 tableSizeFor메서드를 이용해서 threshold로 전송하고있다.
내부 배열 크기를 결정하는 변수가 따로 존재하지 않아,
threshold를 이용해 임시적으로 initialCapacity를 전송한 것으로 보인다.
/**
* Constructs an empty {@code HashMap} with the specified initial
* capacity and load factor. * * @apiNote
* To create a {@code HashMap} with an initial capacity that accommodates
* an expected number of mappings, use {@link #newHashMap(int) newHashMap}.
* * @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive */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;
//1
this.threshold = tableSizeFor(initialCapacity);
}
(2-2)
기본 생성자로 해시맵을 생성 했을 때의 로직이다.
//2-2
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
(3)
(2-1) 의 경우, oldThr로 newCap은 값이 할당되지만,
newThr는 따로 값이 초기화되지 않으므로,
newThr값을 연산하여 threshold에 대입한다.
//3
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
(4)
//4
//4-1
@SuppressWarnings({"rawtypes","unchecked"})
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);
//4-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);
//4-3
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
(4-1)
newCap으로 배열을 확장하고, oldCap의 배열들을 순회하면서
버킷에 요소가 하나뿐인것들을 골라 newTab에 재배열한다.
//4-1
@SuppressWarnings({"rawtypes","unchecked"})
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);
...
(4-2)
버킷에 요소가 다수일 경우, 해시값에 대한 연산을 통해 low, high로 지정한다.
//4-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);
...
이렇게 나뉘어진 두 연결 리스트의 head를 각각의 버킷 인덱스에 할당한다 .
(4-3)
//4-3
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
이렇게 resize를 호출할때마다 기존 버킷의 요소들을 넓게 분포시킴으로써 해시충돌을 완화하여 시간복잡도를 낮게 유지시켜준다.
24.01.31
이렇게 resize()로 기존 요소들을 다시 여러 버킷으로 재할당 할 때, Node의 hash값 자체는 변경하지 않는다.
즉, 동일한 버킷 내에서도 여러 hash값들이 존재할 수 있다.
5. 조회
찾으려는 값의 key를 내부 해시함수로 연산하여 버킷값을 찾고,
해당하는 값이 나올때까지 연결 리스트를 순회한다.
없다면 null을 반환한다.
public V get(Object key) {
Node<K,V> e;
return (e = getNode(key)) == null ? null : e.value;
}
final Node<K,V> getNode(Object key) {
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) {
if (first.hash == hash && // always check first node
((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;
}