이번 글에서는 Java 7, Java 8에서 HashMap이 어떻게 구현되어 있는지 알아보겠습니다. Java에서는 HashTable을 구현할 때 어떻게 충돌 가능성을 줄이고 성능을 향상시키려 했는지에 대해 중점을 두어 정리해보겠습니다. public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable {}
하지만 아래와 같은 차이점을 가지고 있습니다.
해시 분포와 해시 충돌동일하지 않은 어떤 객체 X와 Y가 있을 때, 즉 X.equals(Y)가 '거짓'일 때 X.hashCode() != Y.hashCode()가 같지 않다면, 이때 사용하는
해시 함수는 일반적으로 Number 객체(Double, Long, Integer), Boolean 같은 것들은 충돌이 일어나지 않고 완전한 해시함수로 구현할 수 있지만, HashMap은 버킷의 위치를 정할 때 객체의 해시코드를 사용합니다. 이 때 해시코드의 결과 자료형은 int 입니다. 32비트 정수 자료형(int)으로는 완전한 자료 해시 함수를 만들 수 없습니다. 논리적으로 2^32보다 더 많은 객체를 생성할 수 있기 때문입니다. 그리고 설령 가능하다 하더라도 2^32 만큼 버킷을 만드는 것은 엄청난 메모리 낭비이며, 배열을 사용하는 것과 다르지 않아 해시의 의미가 사라집니다. 따라서 실제 HashMap을 비롯한 많은 해시 함수에서는 메모리를 절약하기 위해서 표현해야 할 N의 범위보다 적은 M 만큼의 배열을 사용합니다. (간단하게 예를들면, 총 50개의 정수를 가지고 해시자료 구조를 쓴다면 버킷을 한 15개정도 사용하는 식입니다.)  위와 같이 나눠주면 그리고 이러한 충돌을 해결하기 위한 대표적인 방법 2가지가 각각 어떤 방법인지 간단하게 알아보겠습니다. 개방 주소법(Open Addressing)
1, 2번은 버킷 조사는 원형으로 회전하게 됩니다. 테이블의 마지막에 도달하면 다시 처음으로 이동합니다. 분리 연결법(Seperate Chaining)Java HashMap에서도 이용하고 있는 방식입니다. Separate Chaining이란 동일한 버킷의 데이터에 대해 리스트 or 트리 자료구조를 이용해서 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것입니다. 아래의 그림과 같이 충돌이 발생했을 때 다음 노드를 연결하고 있는 것을 볼 수 있습니다. 그리고 충돌이 많이 발생해서 리스트의 형태로 계속 데이터가 쌓이게 되면 검색하는데 시간 복잡도가 O(n)으로 나빠지게
됩니다. 그래서 Java8의 HashMap은 리스트의 개수가 8개 이상이 되면 간단하게 정리하면 이러한 특징들을 가지고 있습니다. 이제 자바의 HashMap과 연결지어 좀 더 설명을 해보겠습니다. 개방주소법은 연속된 공간에 데이터를 저장하기 때문에 Seperate Chaining에 비하여 캐시 효율이 높습니다. 따라서 데이터의 개수가 충분히 적다면 그리고 Java HashMap에서 사용하고 있는 것은 그리고 java 7에서의 해시 버킷 관련 구현transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; // transient로 선언된 이유는 직렬화(serializ)할 때 전체, table 배열 자체를 직렬화하는 것보다 // 키-값 쌍을 차례로 기록하는 것이 더 효율적이기 때문이다. static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } public final K getKey() { … } public final V getValue() { …} public final V setValue(V newValue) { … } public final boolean equals(Object o) { … } public final int hashCode() {…} public final String toString() { …} void recordAccess(HashMap<K,V> m) {… } void recordRemoval(HashMap<K,V> m) {…} } Java HashMap에서는 public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); // table 배열 생성 } // HashMap에서는 null을 키로 사용할 수 있다. if (key == null) return putForNullKey(value); // value.hashCode() 메서드를 사용하는 것이 아니라, 보조 해시 함수를 이용하여 // 변형된 해시 함수를 사용한다. "보조 해시 함수" 단락에서 설명한다. int hash = hash(key); // i 값이 해시 버킷의 인덱스이다. // indexFor() 메서드는 hash % table.length와 같은 의도의 메서드다. int i = indexFor(hash, table.length); // 해시 버킷에 있는 링크드 리스트를 순회한다. // 만약 같은 키가 이미 저장되어 있다면 교체한다. for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 삽입, 삭제 등으로 이 HashMap 객체가 몇 번이나 변경(modification)되었는지 // 관리하기 위한 코드다. // ConcurrentModificationException를 발생시켜야 하는지 판단할 때 사용한다. modCount++; // 아직 해당 키-값 쌍 데이터가 삽입된 적이 없다면 새로 Entry를 생성한다. addEntry(hash, key, value, i); return null; } 그렇지만 Java 8에서는 성능을 개선하기 위해 변화가 있었습니다. Java 8 HashMap에서의 Seperate ChainingJava 7까지는 Java 8에서는 일정 개수 이상이 되면
개수의 차이를 2로 둔 이유는 키-값 쌍이 삽입, 삭제가 연속적으로 일어나게 되었을 때, 계속 리스트->트리, 트리->리스트로 변환하는 과정이 일어나는데 이러면 성능상 좋지 않기 때문에 개수 차이를 2개로 두었습니다. static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6; Java 8 HashMap에서는 Entry 클래스 대신 Node 클래스를 사용합니다. Node 클래스 자체는 사실상 Java 7의 Entry 클래스와 내용이 같지만, 링크드 리스트 대신 트리를 사용할 수 있도록 하위 클래스인 TreeNode가 있다는 것이 Java 7 HashMap과 다릅니다. 이때 사용하는 트리는 Red-Black Tree인데, Java Collections Framework의 TreeMap과 구현이 거의 같습니다. 해시 버킷 동적 확장해시 버킷을 적게 사용한다면 초반에 메모리 사용을 절약할 수 있지만, 충돌을 빈번하게 발생할 수 있다는 단점이 있고, 너무 많이 사용하게 되면 메모리 낭비를 할 수도 있다는 단점이 있습니다. public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 static final float DEFAULT_LOAD_FACTOR = 0.75f; } 그래서 HashMap 클래스를 보면 여기서 기본용량은 버킷의 수와 같고, 로드팩터는 위의 예시로 들면 기본 용량은 16이기 때문에 데이터의 개수가 12개가 차면 버킷의 용량을 16 -> 32로 늘리는 과정이 일어납니다. 이 때 원래 버킷에 있던 것을 새로운 버킷에다 옮기는 과정이 일어나기 때문에 자주 일어난다면 당연히 성능상 좋지 않습니다. public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 static final float DEFAULT_LOAD_FACTOR = 0.75f; final float loadFactor; public HashMap(int initialCapacity, float loadFactor) { } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } } 따라서 생성자로 기본 생성자를 사용하면 버킷의 수가 16이기 때문에 계속 2배로 늘어가는 과정이 발생하게 되면 속도가 많이 느려지기 때문에 버킷의 수를 직접 지정하는 것이 성능상 좋습니다. // 인자로 사용하는 newCapacity는 언제나 2a이다. void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; // MAXIMIM_CAPACITY는 230이다. if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; // 새 해시 버킷을 생성한 다음 기존의 모든 키-값 데이터들을 // 새 해시 버킷에 저장한다. transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; // 모든 해시 버킷을 순회하면서 for (Entry<K,V> e : table) { // 각 해시 버킷에 있는 링크드 리스트를 순회하면서 while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } // 해시 버킷 개수가 변경되었기 때문에 // index 값(hashCode % M)을 다시 계산해야 한다. int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } } 위의 코드로 버킷을 2배로 늘리는데 문제점초기 버킷의 수는 16이고 2배로 늘어나면 32, 64 ... 으로 늘어나게 됩니다. 그러면 2^a 형태가 되는데, 이러면 32비트 영역 중 a개의 비트만 사용하게 된다는 단점이 있습니다. (즉, index = X.hashCode() % M을 계산할 때 X.hashCode()의 하위 a개의 비트만 사용하게 됨) 즉 해시 함수가 32비트 영역을 고르게 사용하도록 만들었다 하더라도 해시 값을 2의 승수로 나누면 해시 충돌이 쉽게 발생할 수 있습니다.
보조 해시 함수index = X.hashCode() % M을 계산할 때 사용하는 M 값은 소수일 때 index 값 분포가 가장 균등할 수 있습니다. 그러나 M 값이 소수가 아니기 때문에 별도의 보조 해시 함수를 이용하여 index 값 분포가 가급적 균등할 수 있도록 해야 합니다.
final int hash(Object k) { // Java 7부터는 JRE를 실행할 때, 데이터 개수가 일정 이상이면 // String 객체에 대해서 JVM에서 제공하는 별도의 옵션으로 // 해시 함수를 사용하도록 할 수 있다. // 만약 이 옵션을 사용하지 않으면 hashSeed의 값은 0이다. int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); // 해시 버킷의 개수가 2a이기 때문에 해시 값의 a비트 값만을 // 해시 버킷의 인덱스로 사용한다. 따라서 상위 비트의 값이 // 해시 버킷의 인덱스 값을 결정할 때 반영될 수 있도록 // shift 연산과 XOR 연산을 사용하여, 원래의 해시 값이 a비트 내에서 // 최대한 값이 겹치지 않고 구별되게 한다. h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } Java 7의 HashMap 에서는 위와 같은 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } Java 8에서는 위와 같이 Java 7의 보조 해시 함수보다는 훨씬 간단하게 사용하고 있습니다. Java 8 HashMap 보조 해시 함수는 상위 16비트 값을 XOR 연산하는 매우 단순한 형태의 보조 해시 함수를 사용합니다. 이유로는 두 가지가 있는데,
String 객체에 대한 해시 함수String 객체에 대한 해시 함수 수행 시간은 문자열 길이에 비례합니다. 때문에 JDK 1.1에서는 String 객체에 대해서 빠르게 해시 함수를 수행하기 위해, 일정 간격의 문자에 대한 해시를 누적한 값을 문자열에 대한 해시 함수로 사용했습니다. public int hashCode() { int hash = 0; int skip = Math.max(1, length() / 8); for (int i = 0; i < length(): i+= skip) hash = s[i] + (37 * hash); return hash; } 위의 예제에서 볼 수 있듯이 모든 문자에 대해 해시 값을 구하는 것이 아니라 일부 스킵을 하면서 구하는 것을 볼 수 있습니다. 그러나 이런 방식은 심각한 문제를 야기했습니다. 웹상의 URL은 길이가 수십 글자에 이르면서 앞 부분은 동일하게 구성되는 경우가 많기에 이 경우 서로 다른 URL의 해시 값이 같아지는 빈도가 매우 높아질 수 있다는 문제가 있습니다. 따라서 이런 방식은 곧 폐기되었고, 예제 11에서 보는 방식을 현재의 Java 8까지도 계속 사용하고 있습니다. public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; } 여기서 숫자 31을 곱하는 이유는 아래와 같습니다.
|
Hash map을 만들 때 어떤 hash 함수가 가장 효율적
저작권 © 2024 estudarpara Inc.
