HashTable
key와 value를 저장하는 데이터 구조
ex) 5개의 과일이 들어있는 바구니(해쉬테이블)
key : 과일이름, value : 과일색
충돌 처리 방식에 따른 알고리즘 분류
해쉬 테이블에서는 근본적인 문제로 hash_function(key) / size_of_array의 값이 중복될 수 있다. 이 충돌을 해결하는 방법에 따라 여러가지 구현 방식이 존재한다.
ex) key가 정수, hash_function이 key%10, size_of_array가 10일 때, key 1, 11, 21, 31은 같은 index를 가지게 된다.
1. Separate chaining 방식
JDK내부에서도 사용하고 있는 처리 방식으로, Linked List를 이용하는 방식이다.
각 index에 데이터를 저장하는 Linked list에 대한 포인터를 가지는 방식이다.
(출처 :https://en.wikipedia.org/wiki/Hash_table )
동일한 index로 인해 충돌이 날 경우, 해당 index가 가리키고 있는 Linked list에 노드를 추가하여 값을 추가한다.
데이터를 추출할 때는, key에 대한 index를 구한 후 , index가 가리키고 있는 Linked list를 선형 검색하여, 해당 key에 대한 데이터가 있는지를 검색하여 리턴한다.
데이터를 삭제할 때는, key에 대한 index가 가리키고 있는 Linked list에서 그 노드를 삭제한다.
Separate chaining방식은 Linked list구조를 사용하고 있기 때문에, 데이터 수의 제약이 작다.
참고 : 동일 index에 대해서 데이타를 저장하는 자료 구조는 Linked List 뿐 아니라, Tree를 이용하여 저장함으로써, select의 성능을 높일 수 있다. 실제로, JDK 1.8의 경우에는 index에 노드가 8개 이하일 경우에는 Linked List를 사용하며, 8개 이상으로 늘어날때는 Tree 구조로 데이타 저장 구조를 바꾸도록 되어 있다.
2. Open addressing 방식
Linked List와 같은 추가적인 메모리 공간을 사용하지 않고, hash table array의 빈공간을 사용하는 방법으로, Separate chaining 방식에 비해 메모리를 덜 사용한다.
1)Linear Probing
충돌 발생 시, index 뒤에 있는 버킷 중에 빈 버킷을 찾아서 데이터를 넣는 방식
(출처:http://bcho.tistory.com/1072)
위 그림처럼, key 11 데이터는 key 1 데이터와 충돌이 발생하게 된다.
Linear Probing은 이 상황에, Separate Chaining처럼 노드를 추가하지 않고, 뒤의 버킷에 빈 공간이 있는지 탐색한 후, 해당 값을 넣는다.
따라서 key 11의 데이터는 가장 가까운 빈 버킷인 3번 버킷에 저장된다.
데이터 추출 시, hash_function(key) / size_of_array의 값에 따라 array[]를 탐색하게 된다.(ex : 11은 array[1]부터 검색)이때, key가 일치하지 않는 경우에는 뒤의 index를 검색하여 같은 키가 나오거나 또는 key가 없을때까지 검색을 진행한다.
데이터 삭제 시, 충돌에 의해 뒤로 저장된 데이터는 검색이 되지 않을 수 있다.
따라서 Linear Probing은 이러한 문제를 방지하기 위해 데이터를 삭제한 후, Dummy node를 삽입하여 데이터를 연결한다. 이러한 방법은 삭제가 빈번한 경우에 Dummy node로 인해, 많은 bucket을 연속적으로 검색해야 하기 때문에, Dummy Node의 개수가 일정 수를 넘겼을 경우에는 새로운 array를 만들어, 다시 hash를 리빌딩하여 dummy node를 없애서 성능을 유지한다.
ex)
(출처:http://bcho.tistory.com/1072)
해당 테이블에서 key 11을 탐색해보자, key11은 key%10의 값이 1이므로, array[1]부터 차례로 탐색을 진행한다. 여기서 index 2가 삭제되었으므로, index 2까지만 탐색을 진행하고, 탐색을 멈춘다.
이러한 문제를 막기위해 dummy node가 삽입된다.
2) Resizing
Open addressing의 경우, 고정 크기 배열을 사용하기 때문에, 데이터를 다 넣기 위해서는 배열을 확장해야 한다. 또한 Separate chaining의 경우에도 버킷이 일정 수준으로 차 버리면 각 버킷에 연결된 list의 길이가 늘어나기 때문에, 검색 성능이 떨어지게 되므로, 버킷의 개수를 늘려줘야한다.
이를 Resizing이라고 하며, 별 다른 기법은 없다.
더 큰 버킷을 가지는 array를 새로 만든 다음에, 다시 새로운 array에 hash를 다시 계산해서 복사해줘야 한다.
해쉬테이블 구현(JAVA)
(참고:https://ktko.tistory.com/entry/HashTable-Java%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0)
class HashTable{
//구현할 LinkedLsit
LinkedList<Node>[] data;
// hashtable 생성
public HashTable(int size){
this.data = new LinkedList[size];
}
// hashcode 생성
int getHashCode(String key){
int hashCode = 0;
for(char c : key.toCharArray()){
hashCode += c;
}
return hashCode;
}
//생성한 hashcode로 index를 만듦 key%size_of_array
int converToIndex(int hashCode){
return hashCode % data.length;
}
// 충돌하는 key가 있는지 찾음
Node searchKey(LinkedList<Node> list, String key){
if(list == null){return null;}
for(Node node : list){
if(node.key.equals(key)){
return node;
}
}
return null;
}
//Separte Chaining 구현 함수
void put(String key, String value){
int hashCode = getHashCode(key);
int index = convertToIndex(hashCode);
LinkedList<Node> list = data[index];
if(list == null){
list = new LinkedList<Node>();
data[index] = list;
}
Node node = searchKey(list, key);
if(node == null){
list.addLast(new Node(key, value))
}else{
node.setValue(value);
}
}
//추출 함수
public String get(string key){
int hashCode = getHashCode(key);
int index = convertToIndex(hashCode);
LinkedList<Node> list = data[index];
Node node = searchKey(list, key);
return node == null ? "Not found" : node.getValue();
}
class Node{
String key;
String value;
public Node(String key, String value) {
this.key = key;
this.value = value;
}
public String getValue() {
return this.value;
}
public void setValue(String value) {
this.value = value;
}
}
}