해시 테이블(Hash Table)

해시 테이블(Hash Table)

해시 테이블(Hash Table)이란 Key-Value 쌍으로 데이터를 저장하는 자료구조이다.

배열에서 인덱스를 통해 값에 접근하듯이, 해시 테이블 역시 Key를 통해 Value에 접근한다.

배열의 인덱스는 중복되지 않는 정수이지만, 해시 테이블의 Key는 다양한 자료형이 올 수 있다.

하지만 기본적인 저장공간은 배열이기 때문에 결국 Key를 정수인 Index로 변환해야 한다.

이 변환해주는 함수를 해시 함수(Hash Function)라고 한다.

즉, Key를 해시함수 H를 통해 H(key)라는 인덱스를 만들고, 이를 통해 배열에 저장된 Value를 획득하는 방법이다.

해시값을 통해 접근하는 배열을 버킷(Bucket)이라고 한다.

결국 Key를 해시 함수에 한 번만 적용시키면 Value를 가져올 수 있으므로 시간 복잡도는 $O(1)$이다.

배열 역시 시간 복잡도는 $O(1)$이다. 하지만, 데이터 양이 많아지면 어떤 데이터가 몇 번째 인덱스에 있는지 알기 어렵다.

따라서 배열에서 성능이라는 장점을 그대로 가져가면서, 위 같은 단점을 Key와 해시함수를 통해 해결한 모델이 해시 테이블이다.

또한, 사이즈가 정적인 배열과 달리 해시 테이블은 Key-Value 쌍 개수에 따라 사이즈를 동적으로 변환시킨다.

그래서 대량의 데이터를 저장할 때는 해시 테이블을 자주 사용한다.

---

해시 함수

수학에서 정의역(X)과 공역(Y)이 일대일 대응(Mapping) 될 때 이를 함수라고 한다.

해시 함수 역시 특정 Key를 넣으면 그에 대한 해시값도 유일해야 한다.

하지만 수학에서 정의역과 공역의 범위가 주로 실수(Real Number)로 무한한 반면 컴퓨터는 한계가 있다.

우선 데이터를 배열에다가 저장해야 하기 때문에 공역의 범위는 배열 사이즈라고 할 수 있다.

반대로 정의역인 Key는 제한이 없기 때문에 범위가 더 큰 Key가 작은 Value로 일대일 대응될 수 없다.

따라서 충돌(Collision)이 일어날 수 있다. 충돌을 방지하기 위해서는 그만큼 배열 사이즈가 매우 커져야 한다.

하지만 이 경우 메모리 낭비가 심하므로 컴퓨터에서는 충돌 발생 시 이를 우회하거나 다른 자료구조를 도입해 해결한다.

또한 해시 함수 자체도 충돌 가능성이 최소가 되도록 견고하게 만들어야 한다.

 

아래는 몇 가지 예시이다. (Key-Value : 총 100개, Key는 단순히 0부터 시작하는 정수로 가정.)

1. 배열 사이즈 : 10

• 해시함수와 상관없이 100% 충돌

2. 배열 사이즈 : 100, H(x) = x % 10

• 공간은 넉넉하지만 해시 값이 0~9만 나오기 때문에 100% 충돌

3. 배열 사이즈 : 100, H(x) = x

• 모든 데이터가 배열에 정확히 다 들어감

4. 배열 사이즈 : 100, H(x) = x > 49 ? x : 1

• 50~99번 데이터는 잘 들어가지만, 0~49번 데이터는 1에만 들어가므로 50% 충돌

 

위는 단순히 충돌의 개념을 이해하기 위해 작성한 예시이고,

실제 해시 함수는 충돌 가능성을 최소화하기 위해 아래처럼 다양한 방법을 이용해 만들어진다.

1. Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.

(주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.

2. Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.

3. Multiplication Method: 숫자로 된 Key값 K와 0과 1 사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. $h(k)=(kAmod1)$ × m

---

해시 충돌 시

1. 개방 주소법(Open Addressing)

버킷 사이즈보다 저장된 데이터의 갯수가 적다면, 비어있는 공간이 있다는 의미이므로 메모리 공간을 추가로 사용하지 않고 빈 공간을 찾아 저장하는 방법이다.

버킷 사이즈가 일정 수준이상(일반적으로 75%) 찬다면 용량을 늘리고, 비어있는 공간을 찾는다.

개방 주소법은 주로 아래 3가지 방식이 있다.

1. 선형 탐사법(Linear Probing) : 현재 버킷의 인덱스부터 고정폭 만큼 이동하여 비어있는 버킷에 데이터를 저장. 버킷이 일정이상 차면 너무 많은 탐색이 이뤄짐.
2. 제곱 탐사법(Quadratic Probing) : 폭을 제곱수만큼 늘려서 이동하는 방법. 1칸 -> 4칸 -> 9칸 -> ...
3. 이중 해싱(Double Hashing Probing) : 해시 함수를 사용해서 이동폭을 결정하는 방법. 이동 폭이 해시함수에의해 변동되기 때문에 골고루 저장될 확률이 높아짐. 다른 방법보다 연산량은 많음.

 

개방 주소법에서 데이터를 삭제하면 삭제된 공간은 빈 공간(Dummy Space)으로 남아 메모리 낭비되기 때문에 이를 다시 정리해주는 작업이 필요하다. 따라서, 개방 주소법보다 아래 분리 연결법이 더 선호되는 방식이다.

2. 분리 연결법(Separate Chaining)

분리 연결법은 충돌이 난 데이터들을 다른 자료구조(리스트, 트리 등)를 활용해 연결하는 방법이다.

위 그림에서 "John Smith"와 "Sandra Dee"의 해시값이 152로 동일하여 충돌이 일어났다.

지금까지는 152번 버킷에 데이터를 바로 저장했지만, 분리 연결법에서는 152번에 해당하는 데이터들을 모아둔 다른 자료구조의 주소를 저장해 놓는다.

이 방법은 빈 공간을 찾지 않고 해당 버킷이 가리키는 자료구조에 저장하므로 간단하며, 버킷 용량을 늘리는 작업 횟수가 적어진다.

단, 충돌이 자주 일어나 한 버킷에 들어가있는 데이터 수가 많아진다면, O(1) 시간 안에 데이터를 찾을 수 없다.

리스트라면 O(N), 트리라면 O(log N)이 소요된다.

 

위에서 사용했던 예시를 이용해 충돌을 해결해보자.

Key-Value 데이터 : 100개 (Key는 0부터 시작하는 정수), 배열 사이즈 : 100, H(x) = x % 10
Key_0부터 순서대로 저장

1. Open Addressing(Linear Probing, 이동폭 = 10) : H(11) = 1이므로 충돌발생 => 이동폭 추가 => 11에 저장
    H(21) = 1이므로 충돌 => 이동폭 추가 => 충돌(11) => 이동폭 추가 => 21에 저장

2. Seperate Chaining : H(11) = 1 => 1번 버킷이 가리키고 있는 리스트에 저장

Open Addressing 과 Seperate Chaining 비교

---

HashMap.java

Java의 HashMap과 HashTable Seperate Chaining 방식을 이용해 충돌을 해결했다.

이때, 6과 8을 기준으로 Linked List와 Red-Black Tree로 구조를 동적으로 변환한다.

7이 아닌 이유는 한 개의 데이터 삽입/삭제로 인해 구조를 변경했을 경우 그에 대한 오버헤드가 크기 때문이다.

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
    static final float DEFAULT_LOAD_FACTOR = 0.75f; // 75%이상 시 용량 확장
    static final int TREEIFY_THRESHOLD = 8; // 버킷 데이터가 8개 이상 시 TREE로 구조 변경
    static final int UNTREEIFY_THRESHOLD = 6; // 버킷 데이터가 6개 이하 시 Linked List로 변경
    
    transient Node<K,V>[] table; //버킷 테이블

    final void treeify(Node<K,V>[] tab) {
      // 링크드 리스트를 트리로 변환한다.
    }

    final Node<K,V> untreeify(HashMap<K,V> map) {
      // 트리를 링크드 리스트로 변환한다.
    }
    
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    //index = X.hashCode % M을 계산할 때 M 값이 소수일 때 index 값 분포가 가장 균등할 수 있다.
    //하지만, M값이 소수라는 보장이 없으므로 보조 해시 함수를 이용해 가급적 균등할 수 있도록 한다.
    static final int hash(Object key) { //보조 해시 함수
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
       //초기화 코드
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
            
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode) //RBTree면 tree에 추가
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//아니면 list에 추가
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash); //임계치 넘어가면 트리로 변경
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

---

HashTable.java

HashTable은 멀티 스레드환경에서도 사용할 수 있도록 Synchronized 키워드가 붙어 있다. 따라서, 동기화된 상태로 데이터에 접근할 수 있다.

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    addEntry(hash, key, value, index);
    return null;
}

---

Ref.

https://mangkyu.tistory.com/102

https://d2.naver.com/helloworld/831311

https://overcome-the-limits.tistory.com/9