[Java] Hash Table

해당 글에서는 아래 hash() 메소드 활용

최상위 bit(부호 bit)를 제외시키기 위해 key와 0xfffffff에 대해 AND 연산 수행하여 얻은 31bit 양수를 해시테이블 크기인 M으로 나눈 나머지를 해시값으로 사용

private int hash(Key k) {
    return (k.hashCode() & 0x7fffffff) % M;
}

---

해시테이블

핵심 아이디어

O(logN) 시간보다 빠른 연산을 위해, 키와 1차원 배열의 인덱스 관계를 이용하여 키(항목)를 저장

• 키를 배열의 인덱스로 그대로 사용하면 차지 않은 빈 공간에 메모리 낭비가 심해지므로 키를 변환하여 배열의 인덱스로 사용
• 키를 간단한 함수를 사용해 변환한 값을 배열의 인덱스로 이용하여 항목을 저장하는 것을 해싱(Hasing)이라고 함
• 해싱에 사용되는 함수를 해시함수(Hash Function)라고 하고, 해시함수가 계산한 값을 해시값(Hash Value) 또는 해시주소라고 하며, 항목이 해시값에 따라 저장되는 배열을 해시테이블(Hash Table)이라고 함

해싱

항목의 키 집합 중 k 키 값을 해시 함수에 입력하면 결과 해시값 i가 나오는데 i에 해당되는 위치에 k를 저장

충돌

2개 이상의 항목을 해시테이블의 동일한 원소에 저장하여야 하는 경우 충돌 발생
(서로 다른 키들이 동일한 해시 값을 가질 때 충돌 발생)

해시함수

• 가장 이상적인 해시함수는 키들을 균등(uniformly)하게 해시테이블의 인덱스로 변환하는 함수
• 일반적으로 키들은 부여된 의미나 특성을 가지므로 키의 가장 앞 부분 또는 뒤의 몇 자리 등을 취하여 해시값으로 사용하는 방식의 해시함수는 많은 충돌을 야기시킴
• 균등하게 변환한다는 것은 키들을 해시테이블에 랜덤하게 흩어지도록 저장하는 것을 뜻함
• 해시함수는 키들을 균등하게 해시테이블의 인덱스로 변환하기 위해 의미가 부여되어 있는 키를 간단한 계산을 통해 ‘뒤죽박죽’ 만든 후 해시테이블의 크기에 맞도록 해시 값을 계산
• 하지만 아무리 균등한 결과를 보장하는 해시 함수이더라도 함수 계산 자체에 긴 시간이 소요된다면 해싱의 장점인 연산의 신속성을 상실하므로 그 가치를 잃음

대표적인 해시함수

• 중간제곱(Mid-square) 함수 : 키를 제곱한 후, 적절한 크기의 중간부분을 해시 값으로 사용
• 접기(Folding) 함수 : 큰 자릿수를 가지는 십진수를 키로 사용하는 경우, 몇 자리씩 일정하게 끊어서 만든 숫자들의 합을 이용해 해시값을 만든다.
• (예시) 123456789012에 대해서 1234 + 5678 + 9012 = 15924 계산 후 헤시테이블의 크기가 3이라면 15924의 끝에 3자리 수만을 해시값으로 사용
• 곱셈(Multiplicative) 함수 : 1보다 작은 실수 $\delta$를 키에 곱하여 얻은 숫자의 소수부분을 테이블 크기 M과 곱한다. 이렇게 나온 값의 정수부분을 해시값으로 사용.
  • h(key) = (int) (key * $\delta$) & 1) * M
  • Knuth에 의하면 $\delta = \frac{\sqrt{5} - 1}{2} \approx 0.61803$이 좋은 성능을 보인다. (경험적 숫자)

해시함수의 공통점

• 키의 모든 자리의 숫자들이 함수 계산에 참여함으로써 계산 결과에서 원래 키에 부여된 의미나 특성을 찾아볼 수 없게 된다는 점
• 계산 결과에서 해시테이블의 크ㅡ기에 따라 특정부분만을 해시 값으로 활용

가장 널리 사용되는 해시함수 : 나눗셈(Division) 함수

• 나눗셈 함수는 키를 소수(Prime) M으로 나눈 뒤, 그 나머지를 해시값으로 사용
• h(key) = key % M이고, 따라서 해시테이블의 인덱스는 0에서 M-1이 됨
• 여기서 제수로 소수를 사용하는 이유는 나눗셈 연산을 했을 때, 소수가 키들을 균등하게 인덱스로 변환시키는 성질을 갖기 때문임

※ key(피제수), M(제수)

자바의 hashCode()

• 자바의 모든 클래스는 32비트 int를 리턴하는 hashCode()를 포함하고 있고, hashCode()는 객체를 int로 변환하는 메소드
• 자바의 hashCode()는 이론적으로 어떤 종류의 객체(사용자 정의한 객체 포함)라도 해싱을 할 수 있도록 지원
• hashCode()는 key1.equals(key2)가 true 이면, key1.hashCode() == key2.hasyCode()가 성립한다는 조건 하에 구현되어 있음
  → 즉 2개의 키가 동일하면 각각의 hashCode 값도 같아야 함

자바의 여러 클래스에 선언되어 있는 hashCode() 메소드

Integer

아무런 계산 없이 그대로 key를 리턴

public final class Integer {
    private final int key;
    public int hashCode() {return key;}
}

Boolean

true이면 1231, false이면 1237을 각각 리턴

public final class Boolean {
    private final boolean key;
    public int hashCode() {
        if (key) return 1231;
        else return 1237;
    }
}

Double

key를 IEEE 64-bit 포맷으로 변환시킨 후, 모든 bit를 계산에 참여시키기 위해 최상위 32 bit와 최하위 bit를 XOR한 결과를 리턴

public final class Double {
    private final double key;
    public int hashCode() {
        long bits = doubletoLongBits(key);
        return (int) (bits ^ (bits >>>32));
    }
}

String

key의 문자 (char)를 31진수의 숫자로 간주하여 해시값을 계산

예를 들어 key = “ball”이라면 3016191 리턴
$hash = 98 * 31^3 + 97 * 31^2 + 108 * 31^1 + 108 * 31^0 = 3016191$

public final class String {
    private final char [ ] s;
    public int hashCode() {
        int hash = 0;
        for (int i = 0; i < length(); i++) {
            hash = s[i] + (31 * hash);
        }
        return hash;
    }
}

자바의 hashCode()의 공통점

• 자바의 hashCode()는 제각각 다른 값을 리턴하지만 hashCode()가 리턴하는 값이 모두 signed 32 bit 정수라는 공통점을 가짐
• 자바를 이용하여 해시테이블을 구현할 때엔 일반적으로 hashCode()를 override하여 해시함수 구현

오버플로우 해결

개방주소방식(Open Addressing)

해시테이블 전체를 열린 공간으로 가정하고 충돌된 키를 일정한 방식에 따라서 찾아낸 empty 원소에 저장 ↔ 폐쇄주소방식(Closed Addressing)의 충돌 해결방법은 키에 대한 해시값에 대응되는 곳에만 키를 저장

선형조사(Linear Probing)

$$
(h(key) + i) \bmod M, j = 0, 1, 2, 3, ...
$$

• 충돌이 일어난 원소에서부터 순차적으로 검색하여 처음 발견한 empty 원소에 충돌이 일어난 키를 저장
• h(key) = i라면, 해시테이블 a[i], a[i+1], a[i+2], …, a[i+j]를 차례로 검색하여 첫번째로 찾아낸 empty 원소에 key를 저장
• 해시테이블은 1차원 배열이므로, i+j가 M이 된다면 a[0]을 검색
• 순차 탐색으로 empty 원소를 찾아 충돌된 키를 저장하므로 해시테이블의 키들이 빈틈없이 뭉쳐지는 현상이 발생
  [1차 군집화(Primary Clustering)]
• 이러한 군집화는 탐색, 삽입, 삭제 연산 시 군집된 키들을 순차적으로 방문해야 하는 문제점을 야기
• 군집화는 해시테이블에 empty 원소 수가 적을수록 더 심화되며 해시성능을 극단적으로 저하시킴

public class LinearProbing<K, V> {
    private int M = 13;  // 테이블 크기
    private K[] a = (K[]) new Object[M];  // 해시테이블
    private V[] d = (V[]) new Object[M];  // key 관련 데이터 저장
    private int hash(K key) {
        return (key.hashCode() & ox7fffffff) % M;  // 나눗셈 함수
    }
    // 삽입 연산
    private void put(K key, V data) {
        int initialpos = hash(key);  // 초기 위치
        int i = initialpos, j = 1;
        do {
            // 삽입 위치 발견
            if (a[i] == null) {
                a[i] = key;
                d[i] = data;
                return;
            }
            // 이미 key 존재
            if (a[i].equals(key)) {
                d[i] = data;  // 데이터만 갱신
                return;
            }
            i = (initialpos + j++) % M;  // i = 다음 위치
        } while (i != initialpos);  // 현재 i가 초기위치와 같게되면 루프 종료
    }
    // 탐색 연산
    public V get(K key) {
            int initialpos = hash(key);
            int i = initialpos, j = 1;
            // a[i]가 empty가 아니면
            // 군집화 현상 때문에 null인 경우는 탐색 실패 
            while (a[i] != null) {
                if (a[i].equals(key))
                    return d[i];  // 탐색 성공
                i = (initialpos + j++) % M;  // i = 다음 위치  
            }
            return null;  // 탐색 실패
    }
}

이차조사(Quadratic Probing)

$$
(h(key) + j^2) \bmod M, j = 0, 1, 2, 3, ...
$$

• 이차조사는 선형조사와 근본적으로 동일한 충돌 해결방법
• 충돌 후 배열 a에서 선형조사보다 더 멀리 떨어진 곳에서 empty 원소를 찾음
• 이차조사는 이웃하는 빈 곳이 채워져 만들어지는 1차 군집화 문제를 해결하지만,
  같은 해시값을 갖는 서로 다른 키들인 동의어(Synonym)들이 똑같은 점프 시퀀스(Jump Sequence)를 따라 empty 원소를 찾아 저장하므로 결국 또 다른 형태의 군집화인 2차 군집화(Secondary Clustering)를 야기
• 점프 크기가 제곱만큼씩 커지므로 배열에 empty 원소가 있는데도 empty 원소를 건너뛰어 탐색에 실패하는 경우도 피할 수 없음

public class QuadProbing<K, V> {
    private int M = 13;  // 테이블 크기
    private K[] a = (K[]) new Object[M];  // 해시테이블
    private V[] d = (V[]) new Object[M];  // key 관련 데이터 저장
    private int hash(K key) {
        return (key.hashCode() & ox7fffffff) % M;  // 나눗셈 함수
    }
    // 삽입 연산
    private void put(K key, V data) {
        int initialpos = hash(key);  // 초기 위치
        int i = initialpos, j = 1;
        do {
            // 삽입 위치 발견
            if (a[i] == null) {
                a[i] = key;
                d[i] = data;
                return;
            }
            // 이미 key 존재
            if (a[i].equals(key)) {
                d[i] = data;  // 데이터만 갱신
                return;
            }
            i = (initialpos + j * j++) % M;  // i = 다음 위치
        } while (i != initialpos);  // 현재 i가 초기위치와 같게되면 루프 종료
    }
    // 탐색 연산
    public V get(K key) {
        int initialpos = hash(key);
        int i = initialpos, j = 1;
        // a[i]가 empty가 아니면 
        while (a[i] != null) {
            if (a[i].equals(key))
                return d[i];  // 탐색 성공
            i = (initialpos + j * j++) % M;  // i = 다음 위치  
        }
        return null;  // 탐색 실패
    }  
}

랜덤조사(Random Probing)

$$
(h(key) + rand) \bmod M
$$

• 랜덤조사는 선형조사와 이차조사의 규칙적인 점프시퀀스와 달리 점프 시퀀스를 무작위화 하여 empty 원소를 찾는 충돌 해결방법
• 랜덤 조사는 의사난수(psedo random) 생성기를 사용하여 다음 위치를 찾음
• 랜덤조사 방식도 동의어들이 똑같은 점프 시퀀스에 따라 empty 원소를 찾아 키를 저장하게 되고, 이 때문 3차 군집화(Tertiary Clustering)가 발생

import java.util.Random;
public class RandProbing <K, V> {
    private int M = 13;  // 테이블 크기
    private K[] a = (K[]) new Object[M];  // 해시테이블
    private V[] d = (V[]) new Object[M];  // key 관련 데이터 저장
    private int hash(K key) {
        return (key.hashCode() & ox7fffffff) % M;  // 나눗셈 함수
    }
    // 삽입 연산
    private void put(K key, V data) {
        int initialpos = hash(key);  // 초기 위치
        int i = initialpos;
        Random rand = new Random();
        rand.setSeed(10);
        do {
            // 삽입 위치 발견
            if (a[i] == null) {
                a[i] = key;
                d[i] = data;
                return;
            }
            // 이미 key 존재
            if (a[i].equals(key)) {
                d[i] = data;  // 데이터만 갱신
                return;
            }
            i = (initialpos + rand.nextInt(1000)) % M;  // i = 다음 위치
        } while (i != initialpos);  // 현재 i가 초기위치와 같게되면 루프 종료
    }
    // 탐색 연산
    public V get(K key) {
        int initialpos = hash(key);
        int i = initialpos, j = 1;
        // a[i]가 empty가 아니면 
        while (a[i] != null) {
            if (a[i].equals(key))
                return d[i];  // 탐색 성공
            i = (initialpos + rand.nextInt(1000)) % M;  // i = 다음 위치  
        }
        return null;  // 탐색 실패
    }  
}

이중해싱(Double Hashing)

$$
(h(key) + j \times d(key)) \bmod M, j = 0, 1, 2, 3, ...
$$

• 이중해싱은 2개의 해시함수를 사용
• 하나는 기본적인 해시함수 h(key)로 키를 해시테이블의 인덱스로 변환하고, 제2의 함수 d(key)는 충돌 발생 시 다음 위치를 위한 점프 크기를 다음의 규칙에 따라 정함
• 이중해싱은 동의어들이 저마다 제2 해시감수를 갖기 때문에 점프 시퀀스가 일정하지 않아 이중해싱은 모든 군집화 문제를 해결
• 제2의 함수 d(key)는 점프 크기를 정하는 함수이므로 0을 리턴해서는 안됨
• 제2의 함수 d(key)의 값과 해시테이블의 크기 M과 “서로소(Relatively Prime)” 관계일 때 좋은 성능을 보이므로 해시테이블 크기 M을 소수로 선택하면, 이 제약 조건을 만족

public class DobuleHashing<K, V> {
    private int M = 13;  // 테이블 크기
    private K[] a = (K[]) new Object[M];  // 해시테이블
    private V[] dt = (V[]) new Object[M];  // key 관련 데이터 저장
    private int hash(K key) {
        return (key.hashCode() & ox7fffffff) % M;  // 나눗셈 함수
    }
    // 삽입 연산
    private void put(K key, V data) {
        int initialpos = hash(key);  // 초기 위치
        int i = initialpos, j = 1;
        int d = (7 - (int) key % 7);  // 두 번째 해시 함수, d(key) = 7 - key % 7
        do {
            // 삽입 위치 발견
            if (a[i] == null) {
                a[i] = key;
                dt[i] = data;
                return;
            }
            // 이미 key 존재
            if (a[i].equals(key)) {
                dt[i] = data;  // 데이터만 갱신
                return;
            }
            i = (initialpos + j * d) % M;  // i = 다음 위치
        } while (i != initialpos);  // 현재 i가 초기위치와 같게되면 루프 종료
    }
    // 탐색 연산
    public V get(K key) {
            int initialpos = hash(key);
            int i = initialpos, j = 1;
            int d = (7 - (int) key % 7);
            // a[i]가 empty가 아니면
            while (a[i] != null) {
                if (a[i].equals(key))
                    return d[i];  // 탐색 성공
                i = (initialpos + j * d) % M;  // i = 다음 위치  
            }
            return null;  // 탐색 실패
    }
}

폐쇄주소방식(Closed Addressing)

• 폐쇄주소방식의 충돌 해결 방법은 키에 대한 해시값에 대응되는 곳에만 키를 저장
• 충돌이 발생한 키들은 한 위치에 모여 저장
• 이를 구현하는 가장 대표적인 방법 : 체이닝(Chaning)

public class Chaining<K, V> {
    private int M = 13;  // 테이블 크기
    private Node[] a = new Node[M];  // 해시 테이블
    public static class Node {  // Node 클래스
        private Object key;
        private Object data;
        private Node next;
        // 배열의 원소에는 연결리스트 Node를 가리키는 레퍼런스 저장
        // 키, 데이터, 다른 노드 참조 ref로 구성
        public Node(Object newkey, Object newdata, Node ref) {  // 생성자
            key = newkey;
            data = newdata;
            next = ref;
        }
        public Object getKey() { return key; }
        public Object getData() { return data; }
    }
    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) % M; }  // 나눗셈 연산
    public V get(K key) {  // 탐색 연산
        int i = hash(key);
        for (Node x = a[i]; x != null; x= x.next)  // 연결리스트 탐색
            if (key.equals.(x.key)) return (V) x.data;  // 탐색 성공
        return null;  // 탐색 실패
    }
    private void put(K key, V data) {  // 삽입 연산
        int i = hash(key);
        // 항상 앞으로 삽입
        for (Node x = a[i]; x != null, x = x.next) {
            if (key.equals(x.key)) {  // 이미 키 존재
                x.data = data;  // 데이터만 갱신
                return;
            }
        a[i] = new Node(key, data, a[i]); // 연결리스트의 첫 노드로 삽입
    }
}    

해싱 종류

정적 해싱 (Static Hashing)

고정 크기의 배열을 이용한 방법으로 구현이 쉽고 간단

재해시(Rehash)

• 어떤 해싱방법도 해시테이블에 비어있는 원소가 적으면, 삽입에 실패하거나 해시성능이 급격하게 저하되는 현상을 피할 수 없음
• 이러한 경우, 해시테이블을 확장시키고 새로운 해시함수를 사용하여 모든 키들을 새로운 해시테이블에 다시 저장하는 재해시(Rehash)가 필요
• 재해시는 오프라인에서 이루어지고 모든 키들을 다시 저장해야하므로 O(N) 시간이 소요
• 재해시 수행 여부는 적재율(Load Factor)에 따라 결정
• 적재율 α = (테이블에 저장된 키의 수 N) / (테이블의 크기 M)
• 일반적으로 α > 0.75가 되면 해시테이블 크기를 2배로 늘리고, α < 0.25가 되면 해시테이블을 1/2로 줄임

동적 해싱(Dynamic Hashing)

대용량의 데이터베이스를 위한 해시방법으로 재해싱을 수행하지 않고 동적으로 해시테이블의 크기를 조절

확장해싱

• 디렉터리(Directory)를 메인메모리(Main Memory)에 저장하고, 데이터는 디스크 블록(Disk Block) 크기 버킷(Bucket) 단위로 저장
• 버킷이란 키를 저장하는 곳
• 확장해싱에서는 버킷에 오버플로우가 발생하면 새 버킷을 만들어 나누어 저장하며 이때 이 버킷들을 가리키던 디렉터리는 2배로 확장

→ 디렉터리 확장

선형해싱

• 디렉터리 사용없이, 삽입할 때 버킷을 순서대로 추가하는 방식
• 추가되는 버킷은 삽입되는 키가 저장되는 버킷과 무관하게 순차적으로 추가
• 만일 삽입되는 버킷에 저장공간이 없으면 오버플로우 체인에 새 키를 삽입
• 체인은 단순연결리스트로서 오버플로우된 키들을 임시로 저장하고, 나중에 버킷이 추가되면 오버플로우 체인의 키들을 버킷으로 이동
• 오버플로우가 일어날 경우, 버킷 개수가 linear하게 (하나씩) 증가

해시방법의 성능 비교 및 응용

• 해시방법의 성능은 탐색이나 삽입 연산을 수행할 때 성공과 실패한 경우를 각가 분석하여 측정
• 선형조사는 적재율 α가 너무 작으면 해시테이블에 empty 원소가 너무 많고 α값이 1.0에 근접할수록 군집화가 심화됨
• 개방주소방식의 해싱은 α가 0.5에 가까울수록 즉, $M \approx 2N$일 때 상수시간 성능 보임
• 체이닝은 α가 너무 작으면 대부분의 연결리스트들이 emtpy가 되고, α가 너무 크면 연결리스트길이가 너무 길어져 해시성능이 매우 저하됨
• 일반적으로 M이 소수

 

 

[출처] 경기대학교 | 소프트웨어중심대학산업