#java.util.HashMap HashMap은 가장 많이 사용하는 클래스일 것이다. 키와 값 쌍으로 데이터를 관리하는 Map을 구현한 HashMap은 이름 그대로 Map을 구현하기 위해 해시를 사용한다. Java8에서는 HashMap이 어떻게 구현되어있을까? 해시함수는 어떻게 되어있을까? 본 포스팅에서는 HashMap의 해시함수와 해시충돌을 어떻게 해결하고 있는지 살펴볼 것이다.
#해시 Hash 들어가기에 앞서 잠시 해시에 대해서 알아보자. 해시 테이블은 키와 값 쌍으로 이루어진 구조로서 키와 값은 매핑되어있어 접근시 O(1)의 시간을 소비한다. 즉, 아주 속도가 빠르다. 키는 직접 내부 배열의 인덱스가 될 수 있고 또는 계산되어 인덱스를 얻을 수도 있다. 만일 키가 다르다면 반드시 값도 달라야한다. 해시 인덱스를 계산하는 함수를 해시함수라고 하며, 서로 다른 키가 같은 해시함수 결과(인덱스)를 낸다면 이를 해시충돌이라고 한다.
#직접 주소 테이블 직접 주소 테이블은 그저 배열이라고 볼 수 있다. 키는 아무런 연산없이 바로 배열의 인덱스로 사용된다. 직접 주소 테이블은 매우 빠르고, 구현도 간단하다. 그러나 여러가지 아주 큰 문제점을 안고 있다. 배열의 크기보다 수가 큰 키는 사용할 수 없다. 만일 큰 키를 사용하기 위해서 배열의 크기를 동적으로 늘릴 수도 있겠지만, 이는 잉여 공간이 많이 생길 수가 있다. 또한, 키를 숫자만 사용해야한다는 점도 매우 큰 단점으로 존재한다.
#해시 테이블 해시 테이블은 키를 해시함수를 통해 계산을 해서 인덱스를 얻는 것이다. 이는 해시 테이블 내 공간을 보다 효율적으로 사용할 수 있다. 그리고 해시의 키를 숫자 이외에도 다양하게 사용할 수 있다. 그러나 해시함수를 통해 얻는 인덱스는 중복이 발생할 수 있다. 즉, 서로 다른 키 임에도 불구하고 해시함수의 결과 가 값은 것이다. 이를 해시충돌이라고 하는데, 해시 테이블은 이러한 해시충돌이 줄이는 것이 가장 큰 목표이다.
##해시충돌 해결기법 ###Open-addressing 해시 충돌이 일어나면 테이블 내의 새로운 주소를 계산하여 입력하는 것.
- 선형 탐사(Linear Probing)
- 제곱 탐사(Quadratic Probing)
- 이중 해싱(Double Hashing)
###Chaining 해시 테이블의 각 버킷은 연결리스트(또는 트리)로 구성되며 해시 충돌 발생시 리스트에 추가하는 것
###Resizing 해시 테이블의 크기를 더 크게 만들고, 새로운 크기에 맞추어 가지고 있던 모든 데이들을 다시 해싱하는 것.
#HashMap 클래스 ##Node Class 자바 컬래션의 HashMap은 해시충돌을 해결하기 위해서 Chaining기법을 사용한다. HashMap의 내부 클래스인 Node클래스는 이러한 Chaining을 구현하기 위한 단일연결리스트 노드이다. 해시값과 키, 값을 가지며, 단일연결리스트이기 때문에 다음 노드를 가리키는 next만을 가지고 있다. 이 Node클래스는 Object의 hashCode메서드를 재정의하고 있다.
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
위 코드처럼 키과 값의 해시코드를 XOR하여 새로운 해시코드를 생성한다. 뿐만아니라 equals메서드도 재정의하고 있다.
public final boolean equals(Object o){
if(o == this)
return true;
if(o instanceof Map.Entry){
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if(Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
해시코드가 같거나 키와 값이 모두 같은 경우에만 true를 반환한다.
##TreeNode Class 자바8부터는 HashMap에서 트리구조를 사용한다. TreeNode클래스는 해시충돌을 해결하기 위한 방법인 Chaining을 트리로 구현하기 위한 HashMap의 내부 클래스이다. TreeNode클래스는 LinkedHashMap의 Entry를 상속받고 있다(참고로 LinkedHashMap은 HashMap의 하위클래스이고, LinkedHashMap.Entry는 HashMap.Entry를 상속받고 있다. 상위클래스가 하위 클래스에 의존적이라니, 의존역전원칙에 위배되는 거아닌가 싶다). 트리는 레드블랙트리로 구현되었다.
##해시 함수 HashMap이 해시 테이블을 구현한 것인 만큼, 해시 함수도 구현하고 있다. 해시함수는 자바8부터는 달라졌는데, 더 간단해졌다. 이유는 자바8로 업그레이드되면서 성능이 많이 향상되었고, HashMap 내부적으로 트리구조가 생겼기 때문이라고 한다.
static final int hash(Object key){
int h;
return (key == null)? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
##어떻게 데이터가 저장되는가?
###put메서드
put메서드는 Map인터페이스에서 정의되어 HashMap에서 구현된 메서드이다. 키와 값을 입력하여 데이터를 저장한다. put메서드는 내부적으로 putVal메서드를 호출한다.
public V put(K key, V value){
return putVal(hash(key), key, value, false, true);
}
###putVal메서드 HashMap의 모든 데이터 저장관련 작업은 putVal메서드를 통해 이루어진다.
/**
* 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;
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;
}
코드를 보면 먼저 테이블(버킷에 저장되는)이 존재하는지와 테이블의 크기를 검사한다. 그리고 해시함수를 사용하여 인덱스를 계산하고 해당 인텍스의 버킷이 비어있다면 새로운 노드를 생성한다. 이 부분이 해시충돌이 일어나지 않았을 경우로, 매우 간단하다. 하나 눈여겨 볼것은 해시함수로 인덱스를 얻는 부분이다. 앞에서 살펴본 hash메서드를 키를 인자로 전달하여 해시값을 얻고 이를 해시테이블의 크기 만큼 마스킹(AND)하여 사용하고 있다. HashMap에서 해시테이블의 크기는 2의 배수이다. 즉, 2배씩 증가한다. 로컬변수 n은 해시테이블의 크기가 저장되는데, 이를 통해 테이블 사이즈 이내의 인덱스를 얻는다.
(n-1) & hash -> 인덱스
Ex)
n = 8 = 0000 1000
hash = 21 = 0001 0101
n-1 = 0000 0111
(n-1) & hash = 0000 0101 = 5
그 다음부터는 모두 해시충돌이 발생하였을때의 코드이다. 로컬변수 e는 값이 바뀔 대상이되는 노드이며, p는 현재 선택된 노드이다. 만일 이미 저장되어있는 노드 p가 지금 저장하는 노드와 같은 경우(해시값과 키가 같거나 equals메서드의 결과가 true인 경우) 로컬변수 e는 p가 되며 이후의 코드에서 값을 바꾼다. p가 TreeNode의 객체라면 putTreeVal메서드를 통해 트리노드로서 값을 저장한다. 이도 아니라면, 리스트로 구현되어 있는 p노드를 따라서 마지막 노드로 이동하고 그자리에 추가하거나, 순환 중에 같은 키를 가진 노드를 발견할 경우 해당 노드의 값을 변경한다(break로 반복문을 탈출한다). 그런데 이때 리스트의 노드의 수를 새는데(binCount변수), 한 리스트의 노드의 수가 일정 수(TREEIFY_THRESHOLD상수)이상 넘어갈 경우, 각 버킷이 리스트로 이루어져 있는 해시테이블을 트리화시킨다. 즉, 리스트로 구현된 각 버킷들이 트리로 변하는 것이다(Node -> TreeNode). 처음에는 리스트로 관리하다가 해시충돌이 너무 많이 일어나 리스트가 커질 경우, 버킷을 트리로 변환하는 것이다.
추가가 마무리된 이후에는 재정의해서 사용할 수 있는 afterNodeAccess메서드나 afterNodeInsertion메서드를 호출한다. 그리고 그전에 현재 노드의 수를 확인하여 일정 수준이상이 되면 해시테이블을 크기를 다시 설정한다.
#Reference