[Algorithm] HashMap
※이 포스트는 https://d2.naver.com/helloworld/831311를 참고해 작성하였습니다.
★Hash 함수 : 가변적인 길이의 데이터를 고정 길이의 데이터로 변환하는 함수이다. y = hash(x)에서 y의 길이는 고정되어 있다.
★Hash 함수는 결과값 y를 이용해 x를 역추적하는 것이 불가능하다는 특성(일방향성)과 입력값이 다르면 항상 출력값도 다르다는 특성(충돌회피성)을 갖고, 이로 인해 무결성이 생겨난다. 이러한 특성은 수 많은 데이터가 연결되어 있는 블록체인과 같은 분야에서 중요한 역할을 한다.
★HashMap은 Key, Value쌍을 입력 받아 Hash함수를 이용해 데이터의 Key를 고정길이의 데이터로 변환하여 나온 결과값을 index로 사용해 해당 위치에 Value를 저장한다.
★Perfect Hash Functions(완전 해시 함수) : X.equals(Y)가 false일 때 X.hashCode() == Y.hashCode()가 항상 false이면 이 해시함수 완전 해시 함수라고 한다.
★하지만 기본자료형의 경우는 데이터 그 자체를 hashCode값으로 사용할 수 있기 때문에 완전 해시 함수를 사용할 수 있으나 다른 객체 자료형의 경우에 완전한 해시함수를 제작하는 것은 사실상 불가능 하다. 데이터x의 수는 무한대에 수렴하나 결과 hashCode인 y값은 유한하기 때문에 비둘기집 원리에 의해 반드시 중복이 발생할 수 밖에 없게 된다.
★HashMap은 기본적으로 각 객체의 hashCode()가 반환하는 값을 사용하는데 이 반환값은 2^32크기의 정수형이다. 그러나 생성 가능한 객체의 수가 2^32보다 많을 수 있고, 모든 Map이 2^32크기를 가져야 한다는 점에서 반환값의 범위를 2^32보다 작은 값 M을 사용한다. 즉 실제 사용되는 index값은 x.hashCode() % M이 된다.
★이러한 사용방식은 객체에서의 해시함수 불완전성에 더해 해시코드의 범위를 좁힘으로써 해시 충돌의 가능성을 더 높여 준다. 따라서 이렇게 해시 충돌이 발생한 경우에도 HashMap을 잘 작동시키기 위해서 대표적으로 두가지 방식을 사용한다
- Open Addressing : 데이터를 사용하려는 해시 버킷이 이미 사용중인 경우 다른 버킷에 데이터를 저장하는 방법이다.
- Separate Chaning : 데이터를 사용하려는 해시 버킷이 이미 사용중인 경우, 데이터를 Linked List로 연결하여 저장하는 방법이다. 검색 속도를 향상시키기 위해 JDK8에서는 충돌한 데이터의 수가 8개 이상이 되면 Linked List 대신 Tree로 변경하고, 다시 6개로 줄어들면 Linked List로 변경한다. 여기서 Tree는 Red-Black Tree를 적용시켰다.
★일반적으로 Open Addressing 방법은 데이터의 수가 늘어날수록 해시충돌 확률이 더 높아지기 때문에 데이터의 수가 일정 이상인 경우 Separate Chaning방식보다 느리기 때문에 자바에서는 Separete Chaning방식을 채용하고 있다.
★String의 hashCode()에서는 문자의 갯수만큼 기존의 해시값에 31을 곱한 후 각 문자의 코드를 넣고 다시 31을 곱하는 작업을 반복한다. 31은 소수이며 시프트 연산으로 곱셈을 빠르게 할 수 있기 때문이다.
★HashTable과 HashMap : HashTable은 JDK1에서, HashMap은 JDK2에서 등장한 API이다. 둘다 Map을 구현하고 있으나 HashTable과 달리 HashMap은 보조 해시 함수를 사용하고, 성능 또한 지속적으로 개선되고 있으나 HashTable은 거의 변화가 없다. 사실상 저버전 JRE를 대상으로 한 호환성을 위해 유지만 되고 있는 것으로 보인다.
★결국 HashMap도 내부적으로 배열을 사용하므로 탐색 시간은 O(1)로 굉장히 빠른 편이다.
★HashSet은 내부적으로 HashMap의 Value에 Dummy데이터를 방식으로 사용하므로 사실은 HashMap을 사용하는 것과 같다. 그래서 HashMap만 해보도록 하자.
★삽입 알고리즘 : key객체의 hashCode()를 이용해 내부적으로 사용할 hash값을 구한다(이를 위해 해시 함수를 먼저 구현해야 한다). 그런 다음 이 hash값을 이용해 index를 구한다(이를 위해 indexFor 함수를 구현해야 한다). 만약 해당 index에 entry가 없다면 그냥 넣으면 되고 존재한다면 LinkedList(Java에서는 레드 블랙 트리도 같이 사용)의 형태로 연결한다. 이를 위해 Entry클래스는 다음 노드를 지정할 next 변수를 가진다. 한 버킷은 같은 index값을 가진 노드들을 모아놓은 것이지 노드들의 key가 꼭 같지는 않다. 그래서 equals연산으로 해당 key가 존재하는지를 확인한 후 존재한다면 value만 변경한다. entry의 갯수가 일정 기준을 넘어서면 doubling을 진행한다.
★doubling : HashMap에서 사용하는 배열은 그 크기가 정해져 있기 때문에 entry들이 많으면 많을 수록 충돌또한 많이 발생하게 된다. O(1)이라는 초고속 탐색에서 멀어져 가는 것이다. 그래서 entry의 갯수가 어느 정도 늘어나면 entry배열의 크기(capacity)를 2배씩 늘려주는데 이 것을 doubling이라고 한다. 따라서 capacity는 항상 2의 제곱수이다. loadFactor라는 변수를 두고, entry의 갯수가 capacity * loadFactor(기본 0.75인 듯)를 넘어서면 doubling을 진행한다. doubling 수행시 전 entry에 대해 새로 hash와 index를 계산해 재 배치 한다.
★탐색과 삭제 알고리즘도 사실 같다. Key객체 -> 해시 함수 -> indexFor를 거쳐 버킷의 index를 알아낸 후 LinkedList를 따라 key값을 비교해 찾아낸다. 삽입, 탐색, 삭제의 모든 과정이 hash값 계산을 통해 이루어 지므로 O(1)시간에 끝나는데, 이 알고리즘 보다 중요한 것은 최대한 충돌없이 골고루 분산되게끔 해시 함수와 indexFor함수를 잘 짜는것이다.
★Java 8에서 indexFor() : capacity - 1값과 hash값을 and연산한 값을 반환하도록 되어있다. hash값도 정수인데 바로 index로 사용하지 않는 이유는, hash값은 반드시 capacity보다 작다는 보장이 없기 때문이다. 따라서 어떠한 식으로든 hash를 capacity 이하로 바꿔줘야 한다. capacity는 2의 제곱수이므로 capacity - 1의 비트값은 모두 1이다. 이 값과 hash를 and연산하면 hash의 값이 어떠하든 capacity보다 작은 수가 나오므로 index로 사용할 수가 있다. 또한 capacity가 2배로 늘어나면 capacity - 1도 맨 앞자리만 바뀌고, 이 값과 and연산을 한 index값도 변화가 없거나, 맨 앞자리만 바뀌거나 둘중 하나이기 때문에 효율적인 분산이 가능하다.
★Java 8에서 hash()
int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}key.hashCode()의 총 32비트 정수를 반으로 나눠 앞의 16자리는 그대로 사용하고, 뒤의 16자리를 앞의 16자리와 xor연산하여 뒤의 16자리를 한다.
★HashMap을 구현해 보자
public class MyHashMap<K, V> {
private int capacity;
private Entry<K, V>[] table;
private float loadFactor;
private int size;
private int threshold;
@SuppressWarnings("unchecked")
public MyHashMap() {
this.capacity = 16;
table = (Entry<K, V>[])new Entry[capacity];
this.loadFactor = 0.75f;
this.size = 0;
this.threshold = (int) (capacity * loadFactor);
}
public boolean put(K key, V value) {
Entry<K, V> entry = table[indexFor(key)];
if (entry == null) {
table[indexFor(key)] = new Entry<K, V>(key, value, null);
} else {
while (entry != null) {
if (key.equals(entry.key)) {
entry.value = value;
break;
}
if (entry.next == null) {
entry.next = new Entry<K, V>(key, value, null);
break;
}
entry = entry.next;
}
}
if (++size > threshold) {
resize();
}
return true;
}
@SuppressWarnings("unchecked")
private void resize() {
capacity *= 2;
threshold = (int)(capacity * loadFactor);
Entry<K, V>[] newTab = (Entry<K, V>[])new Entry[capacity];
for (int i = 0; i < table.length; i++) {
Entry<K, V> e = table[i];
while (e != null) {
Entry<K, V> next = e.next;
e.next = null;
int newI = indexFor(e.key);
Entry<K, V> newEntry = newTab[newI];
if (newEntry == null) {
newTab[newI] = e;
} else {
while (newEntry != null) {
if (newEntry.next == null) {
newEntry.next = e;
break;
}
newEntry = newEntry.next;
}
}
e = next;
}
}
table = newTab;
}
public V get(K key) {
Entry<K, V> entry = table[indexFor(key)];
while (entry != null) {
if (entry.key.equals(key)) {
return entry.value;
}
entry = entry.next;
}
return null;
}
public boolean remove(K key) {
int index = indexFor(key);
Entry<K, V> prev = null;
Entry<K, V> entry = table[index];
while (entry != null) {
if (entry.key.equals(key)) {
if (prev == null) table[index] = entry.next;
else prev.next = entry.next;
size--;
return true;
}
prev = entry;
entry = entry.next;
}
return false;
}
public int size() {
return size;
}
private int hash(K key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
private int indexFor(K key) {
return hash(key) & (capacity - 1);
}
private class Entry<K, V> {
private K key;
private V value;
private Entry<K, V> next;
public Entry(K key, V value, Entry<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
}
}