1. HashMap과 HashTable
HashMap과 HashTable은 Java의 API 이름이다. HashTable은 JDK 1.0부터 있던 Java의 API이고, HashMap은 Java2에서 처음 선보인 Java Collection Framework에 속한 API다. HashTable 또한 Map 인터페이스를 구현하고 있기 때문에 HashMap과 HashTable에서 제공하는 기능은 같다. 다만 HashMap은 보조 해시 함수(Additional Hash Function)을 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 성능상 이점이 있다. 보조 해시 함수가 아니더라도, HashTable 구현에는 거의 변화가 없는 반면, HashMap은 지속적으로 개선되고 있다. HashTable의 현재 가치는 JRE 1.0, JRE 1.1 환경을 대상으로 구현한 Java 애플리케이션이 잘 동작할 수 있도록 하위 호환성을 제공하는 것에 있기 때문에, 이 둘 사이에 성능과 기능을 비교하는 것은 큰 의미가 없다고 할 수 있다.
HashMap과 HashTable을 정의한다면, "키에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 증가하는 associate array'라고 할 수 있다. 이 associate array를 지칭하는 다른 용어가 있는데, 대표적으로 Map, Dictionary, Symbo Table 등이다.
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
위의 코드은 HashTable과 HashMap의 선언부이다.
associate array를 지칭하기 위하여 HashTable에서는 Dicitionary라는 이름을 사용하고, HashMap에서는 그 명칭이 그렇듯이 Map이라는 용어를 사용하고 있다.
map(또는 mapping)은 수학 함수에서의 대응 관계를 지칭하는 용어로, 경우에 따라서는 함수 자체를 의미하기도 한다. HashMap이라는 이름에서 알 수 있듯이, HashMap은 키 집합인 정의역과 값 집합인 공역에 대응해 해시 함수를 이용한다.
2. 해시 분포와 해시 충돌
동일하지 않은 어떤 객체 X와 Y가 있을 때, 즉 X.equals(Y)가 '거짓'일 때 X.hashCode() != Y.hashCode()가 같지 않다면, 이때 사용하는 해시 함수는 완전한 해시 함수(perfect hash functions)라고 한다.
Boolean같이 서로 구별되는 객체의 종류가 적거나, Integer, Long, Double 같은 Number 객체는 객체가 나타내려는 값 자체를 해시 값으로 사용할 수 있기 때문에 완전한 해시 함수 대상으로 삼을 수 있다. 하지만 String이나 POJO(plain old jaba object)에 대하여 완전한 해시 함수를 제작하는 것은 사실상 불가능하다.
적은 연산만으로 빠르게 동작할 수 있는 완전한 해시 함수가 있다고 하더라도, 그것을 HashMap에서 사용할 수 있는 것은 아니다. HashMap은 기본적으로 각 객체의 hashCode() 메서드가 반환하는 값을 사용하는데, 결과 자료형은 int다. 32비트 정수 자료형으로는 완전한 자료 해시 함수를 만들 수 없다. 논리적으로 생성 가능한 객체의 수가 2^32보다 많을 수 있기 때문이며, 또한 모든 HashMap 객체에서 O(1)을 보장하기 위해 랜덤 접근이 가능하게 하려면 원소가 2^32인 배열을 모든 HashMap이 가지고 있어야 하기 때문이다.
따라서 HashMap을 비롯한 많은 해시 함수를 이용하는 associative array 구현체에서는 메모리를 절약하기 위하여 실제 해시 함수의 표현 정수 범위보다 작은 M개의 원소가 있는 배열만을 사용한다. 따라서 다음과 같이 객체에 대한 해시 코드의 나머지 값을 해시 버킷 인덱스 값으로 사용한다.
int index = X.hashCode() % M;위의 식은 해시를 사용하는 associative array 구현체에서 저장/조회할 해시 버킷을 계산하는 방법
이 코드와 같은 방식을 사용하면, 서로 다른 해시 코드를 가지는 서로 다른 객체가 1/M의 확률로 같은 해시 버킷을 사용하게 된다. 이는 해시 함수가 얼마나 해시 충돌을 회피하도록 잘 구현되었느냐에 상관없이 발생할 수 있는 또 다른 종류의 해시 충돌이다. 이렇게 해시 충돌이 발생하더라도 키-값 쌍 데이터를 잘 저장하고 조회할 수 있게 하는 방식에는 대표적으로 두 가지가 있는데, 하나는 Open Addressing이고, 다른 하나는 Separate Chaining이다. 이 둘 외에도 해시 충돌을 해결하기 위한 다양한 자료 구조가 있지만, 거의 모두 이 둘을 응용한 것이라고 할 수 있다.
Open Addressing은 데이터를 삽입하려는 해시 버킷이 이미 사용 중인 경우 다른 해시 버킷에 해당 데이터를 삽입하는 방식이다. 데이터를 저장/조회할 해시 버킷을 찾을 때는 Linear Probing, Quadratic Probing 등의 방법을 사용한다.
Separate Chaining에서 각 배열의 인자는 인덱스가 같은 해시 버킷을 연결한 링크드 리스트의 첫 부분(head)이다.
둘 모두 Worst Case O(M)이다. 하지만 Open Addressing은 연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비하여 캐시 효율이 높다. 따라서 데이터 개수가 충분히 적다면 Open Addressing이 Separate Chaining보다 더 성능이 좋다. 하지만 배열의 크기가 커질수록(M 값이 커질수록) 캐시 효율이라는 Open Addressing의 장점은 사라진다. 배열의 크기가 커지면 L1, L2 캐시 적중률(hit ratio)이 낮아지기 때문이다.
Java HashMap에서 사용하는 방식은 Separate Chaininig이다. Open Addressing은 데이터를 삭제할 때 효율적이기 어려운데, HashMap에서 remove()는 매우 빈번하게 호출될 수 있기 때문이다. 게다가 HashMap에 저장된 키-값 쌍 개수가 일정 이상으로 많아지면, 일반적으로 Open Addressing은 Separate Chaining보다 느리다. Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 높아지기 때문이다. 반면 Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 '조정'할 수 있다면 Worst Case 또는 Worst Case에 가까운 일이 발생하는 것을 줄일 수 있다.
3. 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) {…}
}Separate Chaining 방식을 사용하기 때문에, Java7에서의 put() 메서드 구현은 밑의 코드와 같다.
put() 메서드 구현
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에서는 예제 4에서 볼 수 있는 것보다 더 발전된 방식을 사용한다.
4. Java8 HashMap에서의 Separate Chaining
Java 2부터 Java 7까지의 HashMap에서 Separate Chaining 구현 코드는 조금씩 다르지만, 구현 알고리즘 자체는 같았다. 만약 해시 함수 값이 균등 분포(uniform distribution) 상태라고 할 때, get() 메서드 호출에 대한 기대값은
이다. 그러나 Java 8에서는 이보다 더 나은
을 보장한다. 데이터의 개수가 많아지면, Separate Chaining에서 링크드 리스트 대신 트리를 사용하기 때문이다.
데이터의 개수가 많아지면
과
의 차이는 무시할 수 없다. 게다가 실제 해시 값은 균등 분포가 아닐 뿐더러, 설사 균등 분포를 따른다고 하더라도 birthday problem이 설명하듯 일부 버킷 몇 개에 데이터가 집중될 수 있다. 그래서 데이터의 개수가 일정 이상일 때는 링크드 리스트 대신 트리를 사용하는 것이 성능상 이점이 있다.
링크드 리스트를 사용할 것인가 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 키-값 쌍의 개수이다. 예제 5에서 보듯 Java 8 HashMap에서는 상수 형태로 기준을 정하고 있다. 즉 하나의 해시 버킷의 9개의 키-값 쌍이 모이면 링크드 리스트를 트리로 변경한다. 만약 해당 버킷에 있는 데이터를 삭제하여 개수가 6개에 이르면 다시 링크드 리스트로 변경한다. 트리는 링크드 리스트보다 메모리 사용량이 많고, 데이터의 개수가 적을 때 트리와 링크드 리스트의 Worst Case 수행 시간 차이 비교는 의미가 없기 때문이다. 8과 6으로 2 이상의 차이를 둔 것은, 만약 차이가 1이라면 어떤 키-값 쌍이 반복되어 삽입/삭제되는 경우 불필요하게 트리와 링크드 리스트를 변경하는 일이 반복되어 성능 저하가 발생할 수 있기 때문이다.
Java8 HashMap의 TREEIFY_THRESHOLD와 UNTREEIFY_THRESHOLD
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6; 5. Java 8 HashMap의 Node 클래스
Java 8 HashMap에서는 Entry 클래스 대신 Node 클래스를 사용한다. Node클래스 자체는 사실상 Java 7의 Entry 클래스와 내용이 같지만, 링크드 리스트 대신 트리를 사용할 수 있도록 하위 클래스인 TreeNode가 있다는 것이 Java 7 HashMap과 다르다.
이때 사용하는 트리는 Red-Black Tree인데, Java Collection Framework의 TreeMap와 구현이 거의 같다. 트리 순회 시 사용하는 대소 판단 기준은 해시 함수 값이다. 해시 값을 대소 판단 기준으로 사용하면 Total Ordering에 문제가 생기는데, Java 8 HashMap에서는 이를 tieBreakOrder() 메서드로 해결한다.
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
// 클래스 이름은 다르지만, Java 7의 Entry 클래스와 구현 내용은 같다.
}
// LinkedHashMap.Entry는 HashMap.Node를 상속한 클래스다.
// 따라서 TreeNode 객체를 table 배열에 저장할 수 있다.
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;
// Red Black Tree에서 노드는 Red이거나 Black이다.
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
final TreeNode<K,V> root() {
// Tree 노드의 root를 반환한다.
}
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
// 해시 버킷에 트리를 저장할 때에는, root 노드에 가장 먼저 접근해야 한다.
}
// 순회하며 트리 노드 조회
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {}
final TreeNode<K,V> getTreeNode(int h, Object k) {}
static int tieBreakOrder(Object a, Object b) {
// TreeNode에서 어떤 두 키의comparator 값이 같다면 서로 동등하게 취급된다.
// 그런데 어떤 두 개의 키의 hash 값이 서로 같아도 이 둘은 서로 동등하지
// 않을 수 있다. 따라서 어떤 두 개의 키에 대한 해시 함수 값이 같을 경우,
// 임의로 대소 관계를 지정할 필요가 있는 경우가 있다.
}
final void treeify(Node<K,V>[] tab) {
// 링크드 리스트를 트리로 변환한다.
}
final Node<K,V> untreeify(HashMap<K,V> map) {
// 트리를 링크드 리스트로 변환한다.
}
// 다음 두 개 메서드의 역할은 메서드 이름만 읽어도 알 수 있다.
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {}
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {}
// Red Black 구성 규칙에 따라 균형을 유지하기 위한 것이다.
final void split (…)
static <K,V> TreeNode<K,V> rotateLeft(…)
static <K,V> TreeNode<K,V> rotateRight(…)
static <K,V> TreeNode<K,V> balanceInsertion(…)
static <K,V> TreeNode<K,V> balanceDeletion(…)
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
// Tree가 규칙에 맞게 잘 생성된 것인지 판단하는 메서드다.
}
}6. 해시 버킷 동적 확장
해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능상 손실이 발생한다. 그래서 HashMap은 키-값 데이터 개수가 일정 개수 이상이 되면, 해시 버킷의 개수를 두 배로 늘린다. 이렇게 해시 버킷 개수를 늘리면
.png)
값도 작아져, 해시 충돌로 인한 성능 손실 문제를 어느 정도 해결할 수 있다.
해시 버킷 개수의 기본값은 16이고, 데이터의 개수가 임계점에 이를 때마다 해시 버킷의 개수의 크기를 2배씩 증가시킨다. 버킷의 최대 개수는 2^30개다. 그런데 이렇게 버킷 개수가 두 배로 증가할 때마다, 모든 키-값 데이터를 읽어 새로운 Separate Chaining을 구성해야 하는 문제가 있다. HashMap 생성자의 인자로 초기 해시 버킷 개수를 지정할 수 있으므로, 해당 HashMap 객체에 저장될 데이터의 개수가 어느 정도인지 예측 가능한 경우에는 이를 생성자의 인자로 지정하면 불필요하게 Separate Chaining을 재구성하지 않게 할 수 있다.
Java 7 HashMap에서의 해시 버킷 확장
// 인자로 사용하는 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;
}
}
}해시 버킷 크기를 두 배로 확장하는 임계점은 현재의 데이터 개수가 load factor * 현재의 해시 버킷 개수에 이를 때이다. 이 load factor는 0.75 즉 3/4이다. 이 load factor 또한 HashMap의 생성자에서 지정할 수 있다.
임계점에 이르면 항상 해시 버킷 크기를 두 배로 확장하기 때문에, N개의 데이터를 삽입했을 때의 키-값 쌍 접근 횟수는 다음과 같이 분석할 수 있다.
즉 기본 생성자로 생성한 HashMap을 이용하여 많은 양의 데이터를 삽입할 때에는, 최적의 해시 버킷 개수를 지정한 것보다 약 2.5배 많이 키-값 쌍 데이터에 접근해야 한다. 이는 곧 수행 시간이 2.5배 길어진다고 할 수 있다. 따라서 성능을 높이려면, HashMap 객체를 생성할 때 적정한 해시 버킷 개수를 지정해야 한다.
그런데 이렇게 해시 버킷의 크기를 두 배로 확장하는 것에는 결정적인 문제가 있다. 해시 버킷의 개수 M이 2^a 형태가 되기 때문에, index = X.hashCode() % M을 계산할 때 X.hashCode()의 하위 a 비트만 사용하게 된다는 것이다. 즉 해시 함수가 32비트 영역을 고르게 사용하도록 만들었다 하더라도 해시 값을 2의 승수로 나누면서 해시 충돌이 쉽게 발생할 수 있다.
이 때문에 보조 해시 함수가 필요하다.
7. 보조 해시 함수
index = X.hashCode() % M을 계산할 때 사용하는 M값은 소수일 때 index 값 분포가 가장 균등할 수 있다. 그러나 M값이 소수가 아니기 때문에별도의 보조 해시 함수를 이용해서 index 값 분포가 가급적 균등할 수 있도록 해야 한다.
보조 해시 함수(supplement hash function)의 목적은 '키'의 해시 값을 변형하여, 해시 충돌 가능성을 줄이는 것이다. 이 보조 해시 함수는 JDK 1.4에 처음 등장했다. Java 5 ~ Java 7은 같은 방식의 보조 해시 함수를 사용하고, Java 8부터는 다시 새로운 방식의 보조 해시 함수를 사용하고 있다.
Java 7 HashMap에서의 보조 해시 함수
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 8에서는 Java 7보다 훨씬 단순한 형태의 보조 해시 함수를 이용한다.
Java 8 HashMap에서의 보조 해시 함수
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 위의 코드에서 볼 수 있는 것처럼, Java 8 HashMap 보조 해시 함수는 상위 16비트 값을 XOR 연산하는 매우 단순한 형태의 보조 해시 함수를 사용한다. 이유로는 두 가지가 있는데, 첫 번째는 Java 8에서는 해시 충돌이 많이 발생하면 링크드 리스트 대신 트리를 사용하므로 해시 충돌 시 발생할 수 있는 성능 문제가 완화되었기 때문이다. 두 번째로는 최근의 해시 함수는 균등 분포가 잘 되게 만들어지는 경향이 많아, Java 7까지 사용했던 보조 해시 함수의 효과가 크지 않기 때문이다. 두 번째 이유가 좀 더 결정적인 원인이 되어 Java 8에서는 보조 해시 함수의 구현을 바꾸었다.
개념상 해시 버킷 인덱스를 계산할 땐느 index = X.hashCode() % M처럼 나머니 연산을 사용하는 것이 맞지만, M값이 2^a일 때는 해시 함수의 하위 a비트 만을 취한 것과 값이 같다. 따라서 나머지 연산 대신 '1 << a - 1'와 비트 논리곱(AND,&)연산을 사용하면 수행이 훨씬 빠르다.
8. String 객체에 대한 해시 함수
String 객체에 대한 해시 함수 수행 시간은 문자열 길이에 비례한다.
따라서 JDK 1.1에서는 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;
}위의 코드에서 볼 수 있듯이 모든 문자에 대한 해시 함수를 계산하는 게 아니라, 문자열의 길이가 16을 넘으면 최소 하나의 문자를 건너가며 해시 함수를 계산했다.
그러나 이런 방식은 심각한 문제를 야기했다. 웹상의 URL은 수십 글자에 이르면서 앞 부분은 동일하게 구성되는 경우가 많다. 이 경우 서로 다른 URL의 해시 값이 같아지는 빈도가 매우 높아질 수 있다는 문제가 있다. 따라서 이런 방식은 곧 폐기되었고, 예제 11에서 보는 방식을 현재의 Java 8까지도 계속 사용하고 있다.
Java String 클래스 함수
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;
}위의 코드는 Horner's method를 구현한 것이다. Horner's method는 다항식을 계산하기 쉽도록 단항식으로 이루어진 식으로 표현하는 것이다. 즉 위의 코드에서 계산하고자 하는 해시 값 h는 다음과 같다.
이렇게 단항식을 재귀적으로 사용하여 다항식 연산을 표현할 수 있다.
String 객체 해시 함수에서 31을 사용하는 이유는, 31이 소수이며 또한 어떤 수에 31을 곱하는 것은 빠르게 계산할 수 있기 때문이다. 31N=32N-N인데, 32는 2^5이니 어떤 수에 대한 32를 곱한 값은 shift 연산으로 쉽게 구현할 수 있다. 따라서 N에 31을 곱한 값은, (N << 5) - N과 같다. 31을 곱하는 연산은 이렇게 최적화된 머신 코드로 생성할 수 있기 때문에, String 클래스에서 해시 값을 계산할 때에는 31을 승수로 사용한다.
9. Java 7에서 String 객체에 대한 별도의 해시 함수
JDK 7u6부터 JDK 7u25까지는 HashMap에 저장된 키-값 쌍이 일정 개수 이상이면 String 객체에 한하여 별도의 해시 함수를 사용할 수 있게 하는 기능이 있다. 이 기능은 JDK 7u40부터는 삭제되었고, 당연히 Java 8에도 해당 기능은 없다. 여기서 말하는 '일정 개수 이상'이나 '별도의 해시 함수 사용 여부 지정'은 JVM을 가동할 때 옵션으로 지정할 수 있다.
Java 7의 String에 대한 hash32() 메서드
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
….
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
….
// String 클래스에 있는 hash32() 메서드
int hash32() {
int h = hash32;
if (0 == h) {
h = sun.misc.Hashing.murmur3_32(HASHING_SEED, value, 0, value.length);
h = (0 != h) ? h : 1;
hash32 = h;
}
return h;
}JDK 7u6부터 JDK 7u25까지는 jdk.map.althashing.threshold 옵션을 지정하면, HashMap에 저장된 키-값 쌍이 일정 개수 이상일 때 String 객체에 String 클래스의 hashCode() 메서드 대신 sun.misc.Hashing.stringHash32() 메서드를 사용할 수 있게 했다. sun.misc.Hashing.stringHash32() 메서드는 String 클래스의 hash32() 메서드를 호출하게 한 것이고, hash32() 메서드는 MurMur 해시를 구현한 것이다. 이 MurMur 해시를 이용하여 String 객체에 대한 해시 충돌을 매우 낮출 수 있었다고 한다.
그러나 부작용도 있다. MurMur 해시는 hash seed를 필요로 하는데, 이를 위한 것이 sun.misc.Hashing.randomHashSeed() 메서드다. 이 메서드에서는 Random.nextInt() 메서드를 사용한다. Random.nextInt() 메서드는 compare and swap 연산(이하 CAS 연산)을 사용하는 AtomicLong을 사용하는데, CAS 연산은 코어가 많을수록 성능이 떨어진다. 즉 JDK 7u6부터 등장한 String 객체에 대한 별도의 해시 함수는 멀티 코어 환경에서는 성능이 하락했고, 이런 문제로 인해 JDK 7u40부터는 해당 기능을 사용하지 않는다. 당연히 Java 8도 사용하지 않는다.
10. Thread Safe : Hashtable vs Thread Unsafe : HashMmap
Hashtable 코드 일부
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
/**
* Removes the key (and its corresponding value) from this
* hashtable. This method does nothing if the key is not in the hashtable.
*
* @param key the key that needs to be removed
* @return the value to which the key had been mapped in this hashtable,
* or {@code null} if the key did not have a mapping
* @throws NullPointerException if the key is {@code null}
*/
public synchronized V remove(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)tab[index];
for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
modCount++;
count--;
V oldValue = e.value;
e.value = null;
return oldValue;
}
}
return null;
}메소드에 synchronized라는 예약어를 붙여 쓰레드에 안전하게 구현했다.
HashMap 코드 일부
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 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;
}
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}HashTable과 다르게 메소드에 synchronized라는 예약어가 없어 쓰레드에 안전하지 않다.
대략적으로 HashTable과 HashMap의 차이점을 정리하면 다음과 같다.
Hashtable 클래스는 Map 인터페이스를 구현하기는 했지만 일반적인 Map 인터페이스를 구현한 클래스들과는 다르다. 이 두 종류의 다른 점을 간단하게 정리하면 다음과 같다.
- Map은 컬렉션 뷰(Collection View)를 사용하지만, Hashtable은 Enumeration 객체를 통해서 데이터를 처리한다.
- Map은 키, 값, 키-값 쌍으로 데이터를 순환하여 처리할 수 있지만, HashTable은 이 중에서 키-값 쌍으로 데이터를 순환하여 처리할 수 있다.
- Map은 이터레이션을 처리하는 도중에 데이터를 삭제하는 안전한 방법을 제공하지만, HashTable은 그러한 기능을 제공하지 않는다.
크게 봤을 때 Map 인터페이스와 Hashtable 클래스의 차이는 이 정도이다.
그런데, HashMap 클래스와 Hashtable 클래스는 다음과 같은 차이가 있다.
| 기능 | HashMap | Hashtable |
| 키나 값에 null 저장 가능 여부 | 가능 | 불가능 |
| 여러 쓰레드 안전 여부 | 불가능 | 가능 |
특히, Hashtable을 제외한 나머지 Map으로 끝나는 클래스들은 여러 쓰레드에서 동시에 접근하여 처리할 필요가 있을 때에는 다음과 같이 선언해서 사용해야만 한다.
Map m = Collections.synchronizedMap(new HashMap(...));11. HashSet
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
/**
* Removes the specified element from this set if it is present.
* More formally, removes an element {@code e} such that
* {@code Objects.equals(o, e)},
* if this set contains such an element. Returns {@code true} if
* this set contained the element (or equivalently, if this set
* changed as a result of the call). (This set will not contain the
* element once the call returns.)
*
* @param o object to be removed from this set, if present
* @return {@code true} if the set contained the specified element
*/
hashCode() 메소드와 equals() 메소드를 통해 값을 비교하여 모두 참이면 저장하지 않는다.
12. ConcurrentHashMap
위에서 보았다시피 Hashtable은 메소드 전체에 synchronized이 적용되어 있고,
Map m = Collections.synchronizedMap(new HashMap(...));을 통해 HashMap에 synchronized를 적용시키는 이 방법 또한 마찬가지이다.
반면, ConcurrentHashMap은 특히 쓰기 작업에서 Thread-Safe를 보장하면서도 위의 방법보다 높은 성능을 가지고 있다. 그 이유는 위의 경우는 자기 자신이 lock 객체(this)가 되는 반면 ConcurrentHashMap은 메소드의 일부에만 synchronized 블록을 선언하기 때문이다.
put 함수는 크게 2가지 경우로 나눌 수 있는데, 새로운 노드가 들어갈 배열의 인덱스가 비어있는 경우와 이미 기존 노드가 있는 경우이다.
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
//1. 빈 해시 버킷에 노드를 삽입하는 경우, lock을 사용하지 않고, Compare and Swap(cas)을 이용하여 새로운 노드를 해시 버킷에 삽입한다.(원자성 보장)
//1-1. 무한 루프. table은 내부적으로 관리하는 가변 배열이다.
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh; K fk; V fv;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//1-2. 새로운 노드를 삽입하기 위해, 해당 버킷 값을 가져와(tabAt) 함수 비어있는지 확인한다.(==null)
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//1-3. 다시 Node를 담고 있는 volatile 변수에 접근하여 Node와 기대값(null)을 비교하여(casTabAt 함수) 같으면 새로운 Node를 생성해 넣고, 아니면 (1)번으로 돌아간다(재시도).
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else if (onlyIfAbsent // check first node without acquiring lock
&& fh == hash
&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
&& (fv = f.val) != null)
return fv;
else {
V oldVal = null;
// 2. 이미 노드가 존재하는 경우는 synchronized (노드가 존재하는 해시 버킷 객체)를 이용해 하나의 쓰레드만 접근할 수 있도록 제어한다. 서로 다른 쓰레드가 같은 해시 버킷에 접근할 때만 해당 블록이 잠기게 된다.
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 2-1. 새로운 노드로 교체
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
// 2-2. Separate Chaining에 추가
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value);
break;
}
}
}
// 2-3. 트리에 추가
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}synchronized 안의 로직은 HashMap과 비슷한 로직이다. 동일한 Key이면 Node를 새로운 노드로 바꾸고, 해시 충돌(Hash Collision)인 경우에는 Separate Chaining에 추가하거나, TreeNode에 추가한다. TREEIFY_THRESHOLD 값에 따라 체이닝을 트리로 바꾼다.
@SuppressWarnings("unchecked")
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getReferenceAcquire(tab, ((long)i << ASHIFT) + ABASE);
}
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSetReference(tab, ((long)i << ASHIFT) + ABASE, c, v);
}volatile 변수에 2번 접근하는 동안 원자성(atomic)을 보장하기 위해 기대되는 값과 비교(Compare)하여 맞는 경우에 새로운 노드를 넣는다(Swap).
CAS 구현은 java.util.concurrent.atomic 패키지의 Atomic* 클래스들과 동일하게 내부적으로 sun.misc.Unsafe을 사용하고있다.
참고
- https://doorisopen.github.io/developers-library/Java/2020-07-08-java-hashmap-and-thread-safe
- http://blog.breakingthat.com/
- https://cornswrold.tistory.com/209
https://jdm.kr/blog/197 - https://tomining.tistory.com/169
- https://dogcowking.tistory.com/279
- https://deepblue28.tistory.com/entry/Java-SynchronizedCollections-vs-ConcurrentCollections
- https://d2.naver.com/helloworld/831311
- https://velog.io/@adam2/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94
- https://pplenty.tistory.com/17
