공부기록
Hash 본문
Hashing?
key 값에 hash function을 적용하여 hash table의 주소 (entry index)를 산출하여 데이터를 탐색하는 것을 hashing이라고 한다. 데이터를 담은 자료구조를 모두 탐색하는 것이 아닌 키 값을 통해 빠르게 탐색하기 위해 사용한다. O(1)의 복잡도를 기대할 수 있다.
hash에서 value를 담는 자료구조를 table이라고 하고 table에 대한 CRUD는 key에 의해 관리된다. hash(key)해서 나온 값이 곧 table의 인덱스이고, 인덱스에 대응하는 entry에 필요한 정보를 저장하게 된다. 당연한 이야기지만, table은 인덱스에 대해 정렬되어 있다.
Collision
key값에 hash function을 적용하여 주소값을 산출하다 보면 같은 key가 아님에도 같은 hash value가 나오는 경우가 있다. 이를 collision이라고 하며 충돌하는 key가 value를 넣도록 하기 위한 기술이 필요하다. 이를 위해 open hashing과 chained hashing이 있다.
open hashing
단순한 open hashing은 충돌하는 entry의 index이후의 빈 자리가 있는 entry에 정보를 저장하게 된다. 즉, hash(key)해서 나온 인덱스에 있는 값이 실제 key에 대응되는 값이 아닐 수 있기에 value를 담는 자료구조와 key를 담는 자료구조가 요구된다. 또한 value의 index와 key의 index는 서로 대응되어야 한다.
해시함수 자체를 collision 빈도를 줄어들도록 조정할 필요가 있다. 이를 위해 division hash function, mid-sqaure hash function, multiplicative hash function 이 있다.
- division hash funciton
테이블 사이즈가 4K+3 의 소수일 때 좋다. - mid-square function
키는 자신을 곱한 수로 바뀐다. 해시함수는 결과값 중간의 정수들을 리턴한다. - multiplicative hash function
- 키는 1보다 작은 소수를 곱한 수로 바뀐다. 소수 부분 첫 부분 부터의 몇 개를 취해 결과를 리턴한다.
아래의 코드는 division hash function의 간단한 예이다.
public static class HashTable {
public String key;
public Object value;
public Item(String key, Object value){
this.key = key;
this.value = value;
}
}
public static class HashTable{
private static int HASH_TABLE_CAPACITY = 1000;
private Item[] data = new Item[HASH_TABLE_CAPACITY];
private int size = 0;
private int getHash(String key){
int hash = 0;
for(int i=0; i<key.length(); i++){
char val = key.charAt(i);
hash = (hash + val*(i+1)) % HASH_TABLE_CAPACITY;
}
return hash;
}
public Object get(String key){
if(key != null){
int hash = getHash(key);
while(data[hash] != null & !data[hash].key.equals(key)){
hash = (hash+1) % HASH_TABLE_CAPACITY;
}
return data[hash] != null ? data[hash].value : null;
}
}
public void put(String key, Object value){
if(key != null){
int hash = getHash(key);
while(data[hash] != null && !data[hash].key.equals(key)){
hash = (hash + 1) % HASH_TABLE_CAPACITY;
}
if(data[hash] == null)
size++;
data[hash] = new Item(key, value);
}
}
public Object remove(String key){
Object removed = null;
if(key != null){
int hash = getHash(key);
while(data[hash] != null && !data[hash].key.equals(key)){
hash = (hash + 1) % HASH_TABLE_CAPACITY;
}
if(data[hash] != null){
removed = data[hash];
data[hash] = null;
size--;
}
}
return removed;
}
public int size(){
return size;
}
}
//출처 https://codechacha.com/ko/java-simple-hashtable-implementation/Clustring Problem
해시 함수가 선형 탐색을 할 때 문제가 생길 수 있다. table index가 산출되고 빈자리를 찾기 위해 선형으로 탐색을 하게 된다. 이 때 처음에 같은 인덱스가 나온 key가 많을 때 군집을 이루는 문제가 생긴다. 그리고 테이블이 채워질 수록 이 군집은 더욱 커지게 되고 O(N)의 복잡도를 보이게 된다.
Double Hashing
군집을 줄이기 위해 double hashing 기법을 쓰게 된다. hash(key)를 사용하고, 충돌이 일어나면 hash2(key)를 사용한다. hash(key)와 hash2(key)가 hashing하는 방법은 달라야 한다.
hash(key)이후의 index는 (i + hash2(key)) % table.length가 되어야 한다. (i는 반복 횟수)
Chained Hashing
체인 해싱은 테이블이 하나 이상의 원소를 담을 수 있는 배열을 포함한다.
충돌이 일어나면 key에 대응하는 배열의 원소 맨 뒤에 하나의 원소를 새로 삽입하고 정보를 담는다. 이는 링크드리스트를 사용하여 구현이 가능하다.
아래는 링크드리스트를 사용하여 구현한 예시이다.
import java.util.*;
public class LinkedHash {
static class HashNode <K, V>{
K key;
V value;
final int hashCode;
HashNode<K, V> next;
public HashNode(K key, V value, int hashCode){
this.key = key;
this.value = value;
this.hashCode = hashCode;
}
}
static class Map<K, V>{
private ArrayList<HashNode<K,V>> bucketArray;
private int numBuckets;
private int size;
public Map(){
bucketArray = new ArrayList<>();
numBuckets = 10;
size = 0;
for(int i=0; i<numBuckets; i++)
bucketArray.add(null);
}
}
public int size(){ return size; }
public boolean isEmpty(){ return size() == 0; }
private final int hashCode(K key){
return Objects.hashCode(key);
}
private int getBucketIndex(K key){
int hashCode = hashCode(key);
int index = hashCode % numBuckets;
index = index < 0 ? index * -1 : index;
return index;
}
public V remove(K key){
int bucketIndex = getBucketIndex(key);
int hashCode = hashCode(key);
HashNode<K, V> head = bucketArray.get(bucketIndex);
HashNode<K, V> prev = null;
while(head != null){
if(head.key.equals(key) && hashCode == head.hashCode)
break;
prev = head;
head = head.next;
}
if(head == null)
return null;
size--;
if(prev != null)
prev.next = head.next;
else
bucketArray.set(bucketIndex, head.next);
return head.value;
}
public V get(K key){
int bucketIndex = getBucketIndex(key);
int hashCode = hashCode(key);
HashNode<K,V> head = bucketArray.get(bucketIndex);
while(head != null){
if(head.key.equals(key) && head.hashCode == hashCode)
return head.value;
}
return null;
}
public void add(K key, V value){
int bucketIndex = getBucketIndex(key);
int hashCode = hashCode(key);
HashNode<K, V> head = bucketArray.get(bucketIndex);
while(head != null){
if(head.key.equals(key) && hash.hashCode == hashCode){
head.value = value;
return;
}
}
size++;
head = bucketArray.get(bucketIndex);
hashNode<K, V> newNode = new HashNode<K,V>(key, value, hashCode);
newNode.next = head;
bucketArray.set(bucketIndex, newNode);
if((1.0 * size) / numBuckets >= 0.7){
ArrayList<HashNode<K,V>> temp = bucketArray;
bucketArray = new ArrayList<>();
numBuckets = 2 * numBuckets;
for(int i=0; i<numBuckets; i++){
buckets.add(null);
}
for(HashNode<K,V> headNode : temp){
while(headNode != null){
add(headNode.key, headNode.value);
headNode = headNode.next;
}
}
}
}
//출처 : https://www.geeksforgeeks.org/implementing-our-own-hash-table-with-separate-chaining-in-java/
}
Uniform hashing
hash table에 가능한 키 값을 균일하게 뿌리는 것을 uniform hashing이라고 한다.
'CS > Data Structure' 카테고리의 다른 글
| Linked List (0) | 2021.05.29 |
|---|---|
| Stack (0) | 2021.05.29 |
| Heap (0) | 2021.05.28 |
| Tree (0) | 2021.05.28 |
| Array vs List (0) | 2021.05.28 |