해시함수에 대해서 정확하게 모르는데 사용하고 있다는 느낌을 가질 때가 종종 있었습니다.
내가 알던 해시테이블 ?
Hash 함수를 통해서 인엑스를 만들어서 거기에 데이터를 저장하고 꺼내 쓰는 테이블..?
뭐 맥락적으로는 맞겠지만 알고 쓴다는 느낌을 주기는 어렵다고 생각합니다.
그래서 직접 만들어보기로.. 했습니다..
우선 제가 해시테이블을 설계할 때 고려했던것들이 있습니다.
(제가 학습용으로 만든 해시테이블이기 때문에 실제 자바의 해시테이블 구조와 다를 수 있습니다...!)
- Linked List를 가지는 배열 구조
- 해싱 함수 사용
- 데이터 저장
- 데이터 가져오기
- 해시 버킷 동적 확장
실제로 구현한 MyHashTable Class 전체 소스코드
public class MyHashTable<K, V>{
private K key;
private V value;
class Node {
K key;
V value;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
private int count;
private int threshold; // capacity * loadFactor
private float loadFactor;
private static final int MAXIMUM_CAPACITY = (int) Math.pow(2, 30);
private LinkedList<Node>[] table;
public MyHashTable(int initialCapacity, float loadFactor) {
this.table = new LinkedList[initialCapacity];
this.loadFactor = loadFactor;
this.count = 0;
this.threshold = (int) Math.min(initialCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
public MyHashTable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
public MyHashTable() {
this(11, 0.75f);
}
public V get(K key) {
LinkedList<Node>[] tab = table;
int index = getHashTableIndex(key);
if (tab.length == 0) {
return null;
}
LinkedList<Node> list = tab[index];
Node node = searchKey(list, key);
if (node == null) {
return null;
}
return node.value;
}
public void put(K key, V value) {
int hashTableIndex = getHashTableIndex(key);
LinkedList<Node> list = this.table[hashTableIndex];
//todo 아직 안 쓴 인덱스에 리스트를 처음 넣는 경우
// 1. 기존의 count가 threshold 이상인지 체크 -> 이상이면 resize() 호출
// 2. 배열에서 몇 개의 인덱스를 사용하는지 count 갱신
// 3. 해당 인덱스 값을 list로 열어서 Node 저장할 준비
if (list == null) {
if (count >= threshold) {
resize();
}
count++;
list = new LinkedList();
table[hashTableIndex] = list;
}
Node node = searchKey(list, key);
if (node == null) {
list.add(new Node(key, value));
} else {
node.value = value;
}
}
private Node searchKey(LinkedList<Node> list, K key) {
if (list == null) {
return null;
}
for (Node node : list) {
if (node.key.equals(key)) {
return node;
}
}
return null;
}
private int getHashTableIndex(K key) {
// this.table.length 가 소수일때 가장 균등한 index 분포를 가질 수 있음
// key.hashCode() & 0x7FFFFFF -> 양수로 변환
return (key.hashCode() & 0x7FFFFFF) % this.table.length;
}
// threshold 갱신
private void resize() {
LinkedList<Node>[] oldTable = table;
int oldCapacity = oldTable.length;
// MAXIMUM_CAPACITY : 2의 30승
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = MAXIMUM_CAPACITY;
return;
}
int newCapacity = oldCapacity * 2 + 1; // << 1 + 1 == oldCapacity * 2^1 + 1
if (newCapacity > MAXIMUM_CAPACITY) {
newCapacity = MAXIMUM_CAPACITY;
}
table = new LinkedList[newCapacity];
threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
transferToNewTable(oldTable);
}
private void transferToNewTable(LinkedList<Node>[] oldTable) {
count = 0;
for (int i = 0; i < oldTable.length; i++) {
LinkedList<Node> list = oldTable[i];
if (list == null) {
continue;
}
for (Node node : list) {
put(node.key, node.value);
}
}
}
}
1. Linked List(Node)를 가지는 배열 구조
실제 자바의 HashTable은 내부적으로 Entry를 사용하고, Linked List를 사용하지는 않고 있는 것으로 알고 있습니다. 실제로 HashMap에서 Linked List를 사용하고 있는데 학습용으로 Linked List를 사용했습니다.
Linked List를 사용하는 이유 - Separate Chaining
해시 충돌이 날 때 데이터를 저장하는 방식은 크게 2가지가 있습니다. 비어있는 인덱스에 데이터를 저장하는 Open Addressing 방식이 있고 이미 저장되어 있는 데이터에 linked list로 chain을 걸어서 같은 인덱스에 저장하는 방식이 있습니다.
제가 사용하는 방식은 chain을 거는 방식으로 Separate Chaining 방식입니다.
class Node {
K key;
V value;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
LinkedList<Node>[] table; 2. 해싱함수 사용
private int getHashTableIndex(K key) {
// this.table.length 가 소수일때 가장 균등한 index 분포를 가질 수 있음
return (key.hashCode() & 0x7FFFFFF) % this.table.length;
}🔑 해싱함수는 해시 충돌을 최소화하기 위한 첫 번째 열쇠입니다. 실제 데이터가 저장되는 인덱스를 return 하는 것이 해싱 함수이며 해싱 함수는 어떠한 key가 매개변수로 들어오더라도 최대한 균등하게 인덱스를 return 해줘야만 합니다.
균등하게 만드는 방법
1. 해싱함수에 사용되는 나머지는 홀수여야만 한다.
2. key.hashCode()가 음수가 아니라 양수여야만 한다.
this.table.length는 5번에서 다룰 동적 확장을 진행할 때 마다 짝수가 아니라 홀수로 만들어줍니다.
그리고 key.hashCode()는 & 0x7FFFFF 연산을 통해서 양수로 만들어줍니다.
해싱함수의 경우 이후에 나올 데이터 가져오기 / 데이터 저장에 모두 사용됩니다.
3. 데이터 저장
- 기존의 count가 threshold 이상인지 체크 -> 이상이면
resize()호출 -> 이후 동적확장 부분에서 언급할 예정 - 배열에서 몇 개의 인덱스를 사용하는지 count 갱신
- 해당 인덱스 값을 list로 열어서 Node 저장할 준비
- 링크드리스트에 접근한 뒤 for문으로 돌면서 같은 key를 가지는 node가 없
으면 리스트에 새로운 노드(key,value) 추가 - 같은 key를 가지는 node가 이미 존재하면 해당 node의 value 값만 갱신
public void put(K key, V value) {
int hashTableIndex = getHashTableIndex(key);
LinkedList<Node> list = this.table[hashTableIndex];
//todo 아직 안 쓴 인덱스에 리스트를 처음 넣는 경우
// 1. 기존의 count가 threshold 이상인지 체크 -> 이상이면 resize() 호출
// 2. 배열에서 몇 개의 인덱스를 사용하는지 count 갱신
// 3. 해당 인덱스 값을 list로 열어서 Node 저장할 준비
if (list == null) {
if (count >= threshold) {
resize();
}
count++;
list = new LinkedList();
table[hashTableIndex] = list;
}
Node node = searchKey(list, key);
if (node == null) {
list.add(new Node(key, value));
} else {
node.value = value;
}
}4. 데이터 가져오기
- key를 기반으로 해시테이블의 인덱스 찾기
- 링크드리스트를 for문으로 돌면서 node.key가 key와 일치하는 node 찾고 그 node의 value 리턴
public V get(K key) {
LinkedList<Node>[] tab = table;
int index = getHashTableIndex(key);
if (tab.length == 0) {
return null;
}
LinkedList<Node> list = tab[index];
Node node = searchKey(list, key);
if (node == null) {
return null;
}
return node.value;
}private Node searchKey(LinkedList<Node> list, K key) {
if (list == null) {
return null;
}
for (Node node : list) {
if (node.key.equals(key)) {
return node;
}
}
return null;
}5. 해시 버킷 동적 확장
🔑 해시 버킷 동적 확장이 해시 충돌을 최소화하는 두 번째 열쇠입니다.
아무리 해시 함수를 균등하게 return 하도록 설계한다고 해도 버킷의 수가 적으면 충돌이 지속적으로 발생할 수 밖에 없습니다. 동적으로 버킷의 수를 지속적으로 늘려줘야 충돌 확률을 감소시킬 수 있습니다.
동적 확장 기본 원리
threshold(임계점)을 미리 설정해놓고 해당 threshold보다 배열이 더 많이 채워질 경우 동적 확장을 진행합니다.
- threshold 초기화 = initialCapacity * loadFactor
- count ≥ threshod 일 때 resize() 동작
- resize()는 (1)늘어난 Capacity를 가지는 배열을 새로 생성, (2)threshold 갱신하고, (3)새로 생긴 배열에 기존 배열 값들을 다시 인덱싱해서 다시 넣어주기
인스턴스 변수
private int count;
private int threshold; // capacity * loadFactor
private float loadFactor;
private static final int MAXIMUM_CAPACITY = (int) Math.pow(2, 30);해시테이블 생성자
public MyHashTable(int initialCapacity, float loadFactor) {
this.table = new LinkedList[initialCapacity];
this.loadFactor = loadFactor;
this.count = 0;
this.threshold = (int) Math.min(initialCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
public MyHashTable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
public MyHashTable() {
this(11, 0.75f);
} 동적확장함수
private void resize() {
LinkedList<Node>[] oldTable = table;
int oldCapacity = oldTable.length;
// MAXIMUM_CAPACITY : 2의 30승
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = MAXIMUM_CAPACITY;
return;
}
int newCapacity = oldCapacity * 2 + 1; // << 1 + 1 == oldCapacity * 2^1 + 1
if (newCapacity > MAXIMUM_CAPACITY) {
newCapacity = MAXIMUM_CAPACITY;
}
table = new LinkedList[newCapacity];
threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
transferToNewTable(oldTable);
}새로운 테이블로 데이터를 옮겨주는 함수
private void transferToNewTable(LinkedList<Node>[] oldTable) {
count = 0;
for (int i = 0; i < oldTable.length; i++) {
LinkedList<Node> list = oldTable[i];
if (list == null) {
continue;
}
for (Node node : list) {
put(node.key, node.value);
}
}
}HashTable에 데이터를 넣고 가져오기
import java.util.Hashtable;
public class Main {
public static void main(String[] args) {
MyHashTable<Integer, String> myHashTable = new MyHashTable();
myHashTable.put(1, "one"); // index : 1
myHashTable.put(12, "twelve"); // index : 1
myHashTable.put(2, "two");
myHashTable.put(3, "three");
myHashTable.put(4, "four");
myHashTable.put(5, "five");
myHashTable.put(6, "six");
myHashTable.put(7, "seven");
myHashTable.put(8, "eight");
myHashTable.put(9, "nine"); // 동적확장 resize() 함수 실행
myHashTable.put(10, "ten");
myHashTable.put(11, "eleven");
myHashTable.put(1, "oneone");
String one = myHashTable.get(1);
String twelve = myHashTable.get(12);
System.out.println("key1 : " + one); // oneone // index : 1
System.out.println("key12 : " + twelve); // twelve // index : 12
}
}key로 1을 넣은 데이터의 value가 "one"에서 "oneone"으로 update 된 것을 확인할 수 있고 기존 테이블 데이터를 새로운 테이블에 넣어줬기 때문에 key로 12를 넣은 데이터의 index도 늘어난 length에 맞게 (1 -> 12) 변경된 것을 볼 수 있습니다.
이렇게 실제로 HashTable을 간략하게 구현해보니 너무나도 많은 기능들이 자료구조에 내포되어 있다는 것을 알 수 있었네요... ㅎㅎ
기본적인 구조 파악에 집중했기 때문에 굉장히 간략하게 구현을 한 부분들이 많습니다. 하지만 기본적인 Hash Table의 흐름을 파악할 수 있네요..! 🙂🙃
There are no two words in the English language more harmful than “good job”.