Yg-Hong
commented
10 months ago 서론
Hashing은 하나의 문자열을 더 짧은 길이의 키나 값으로 변환하는 기술이다. 문자열이 해시 함수를 통과하게 되면 유일성을 가진 값이 만들어지게 되며 사용자는 이를 통해 특정 값에 O(1)의 시간복잡도로 접근할 수 있다는 장점이 있다.
데이터를 키로 간소화하여 저장한다는 아이디어는 훌륭하지만 실제 해시 함수는 키의 유일성을 완벽하게 보장하지 않는다. 데이터가 너무 많아져서 해시 함수를 통과하여 나온 키가 우연히 이미 존재하던 키와 같다면 해시 기법을 사용하는 것은 의미가 없다. 해시 함수의 입력값은 무한하지만, 출력값은 유한하다는 한계 때문에 위 상황처럼 해시 충돌은 반드시 발생한다. 이를 비둘기집 원리라고 부른다.
본론
해시 충돌을 극복하기 위한 방법은 크게 두가지로 나뉜다. C++, JAVA, Go가 채택하고 있는 체이닝과 Ruby, Python이 채택하고 있는 오픈 어드레싱(개방 주소법)이다. 우리가 다룰 내용은 체이닝이지만 개방 주소법도 아주 살짝 언급하겠다.
Open Addressing(개방 주소법) 해시 충돌이 일어나면 다른 버켓으로 데이터 삽입을 유도한다. 특정 값만큼 건너 뛰어 데이터를 삽입(Linear Probing)하거나 제곱만큼 건너 뛰어 삽입(Quadratic Probing), 해시 결과를 다시 해시 함수에 넣는 방식(double Hasing)을 사용한다.
우리가 알아야 할 것은 체이닝_Seperate Chaining이다.
버켓 내에 데이터를 저장할 자료구조를 할당하여, 버켓에 데이터를 삽입하고 해시 충돌이 발생하면 자료구조를 활용해 데이터를 연결하는 방식이다.
JDK 7까지는 JDK 버전마다 세부적인 구현 코드는 조금씩 다르지만 구현 알고리즘 자체는 Linked List를 고정적으로 이용하여 동일하게 구성되었다. 하지만 데이터가 점점 더 많아지는 상황을 견디지 못하자 JDK 8부터 자료구조를 Linked List에서 Tree를 사용하도록 변경하였다. 그리고 이 Tree가 앞으로 서술할 Red-Black Tree이다.
WHY THEY USE TREE?
데이터의 갯수를 N, 해시 함수의 결과 버켓의 갯수를 M이라 하면 이미 잔뜩 포화 상태의 HashMap에서 데이터를 찾기 위해 걸리는 시간복잡도는 LinkedList 체인의 경우 O(N/M)이다. Tree를 사용한다면 O(log N/M)이므로 데이터 갯수가 일정 이상일 때, Tree가 최악의 경우 더 나은 시간복잡도를 보인다.
물론!
모든 경우에 대해서 트리를 사용하는 것은 아니다. HashMap을 자세히 뜯어보자.
/**
* 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;
static final int MIN_TREEIFY_CAPACITY = 64;하나의 해시 버켓에 Key-Value 쌍이 8개 이상이 되면 자료구조를 Tree로 변환하는 작업을 거치고 데이터를 삭제하여 Key-Value 쌍이 6개 이하가 되면 Tree 구조를 다시 Linked List로 변환하게 된다. Threshold의 차이가 2인 이유는 Table resizing issue 때문이다.
Red-Black Tree
JDK 8부터 HashMap 체이닝에 활용되는 Red-Black Tree는 Collection Framework의 TreeMap과 거의 동일한 구현을 가진다. 다만 트리 순회 시에 사용하는 대소 판단의 기준은 해시 값이 되는데 해시 값이 동일해도 임의로 대소 관계를 지정해야하기 때문에 이 때 tieBreakOrder()라는 메서를 사용한다.
아래 구현 코드의 골격으로 지금까지 내용을 확인해보자([출처](https://d2.naver.com/helloworld/831311)). //** 으로 시작하는 주석은 내 첨언이다.
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
// 클래스 이름은 다르지만, Java 7의 Entry 클래스와 구현 내용은 같다.
//** Entry 클래스는 LinckedList 구현을 위해 Java 7까지 사용했던 클래스이다.
}
// 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) {
// 링크드 리스트를 트리로 변환한다.
//** TREEIFY_THRESHOLD를 넘어도 MIN_TREEIFY_CAPACITY를 넘지 못하면
//** 트리로 변환되지 않는다.
}
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가 규칙에 맞게 잘 생성된 것인지 판단하는 메서드다.
}
}출처
https://d2.naver.com/helloworld/831311
👍 문제
자바에서 Map 인터페이스를 구현한 클래스에는 HashMap, TreeMap, LinkedHashMap이 있다. 이 중 HashMap 클래스는 Java 8 이후 Red-Black Tree를 활용해 해시 충돌 관리를 한다고 한다. 이 방식으로 충돌 관리를 했을 때, 기존 방식 대비 장점이 무엇일까?
✈️ 선정 배경
Red-Black Tree를 몰라서 검색해보다가, TreeMap 뿐 아니라 HashMap에서도 활용된다는 것을 알게 되었다. 이번 기회에 Red-Black Tree와 더불어 해시 충돌에 대해 정리해보면 좋을 것 같아서 선정하였다.
📺 관련 챕터 및 레퍼런스
story4. 어디에 담아야 하는지..
🐳 비고