해시 테이블(Hash Table)

개념(Concept)

● 키(Key)를 이용하여 값(Value)를 저장하는 자료구조이다.

● 키(Key)를 특정 해시 함수(Hash Function)를 통해 해싱한 후 나온 결과(정수)를 배열의 인덱스로 사용하여 값(Value)를 찾는다.

● 검색 성능은 해시 함수의 성능과 해시 테이블의 크기에 좌우된다.

● { "연필" : 200, "볼펜" : 300, "샤프" : 3000, "필통" : 15000 } 의 데이터가 있으면 키(Keys)를 특정 해시 함수(Hash Function)을 사용하여 다음과 같은 해시 테이블의 인덱스 형태로 만든 후 값(Values)을 저장한다.

<해시 테이블 개념도>

장점(Advantage)과 단점(Disadvantage)

● 해싱된 키(Hash Key)를 가지고 배열의 인덱스로 사용하기 때문에 삽입, 삭제, 검색이 매우 빠르다.

● 해시 함수(Hash Function)를 사용하는데 추가적인 연산이 필요하다.

● 적은 데이터 저장시 구현 방식에 따라 연결리스트(Linked List)를 사용하는 경우 오버 헤드의 부담이 생기고, 캐시 효율이 떨어진다.

● 해시 테이블(Hash Table)의 크기가 유한적이고 해시 함수(Hash Function)의 특성상 해시 충돌(Hash Collision)이 발생할 수 밖에 없다.

● 충돌이 없거나 적으면  O(1)의 상수 시간에 가까워지고, 충돌이 발생하면 할수록 성능은 점점 O(n)에 가까워진다.

문제점(Problem)

● 해시 충돌(Hash Collision) : 해싱된 키(Hash Key)가 중복되어 해당 버킷(Bucket)에 이미 레코드가 존재하는 현상을 말한다.

● 오버플로우(Overflow) : 해시 충돌(Hash Collision)이 버킷(Bucket)에 할당된 슬롯(Slot) 수보다 많이 발생하면 더 이상 버킷에 값을 넣을 수 없다. 이러한 현상을 말한다.

● 클러스터링(Clustering) : 연속된 레코드에 데이터가 몰리는 현상을 말한다.

해시 함수(Hash Function)

※ 해싱(Hashing) 참고

http://dev-kani.tistory.com/2

해시 충돌(Hash Collision) 방지

● Separate Chaining(혹은 Closed Addressing) 방식

- 연결 리스트(Linked List)를 이용한 방식으로 JDK 내부에서도 사용된다.

- 키(Key)에 매핑된 인덱스가 가르키는 연결 리스트(Linked List)에 노드(Node)를 추가하여 값(Value)을 추가한다.

- 데이터의 주소 값(인덱스)이 바뀌지 않는다.

- 검색은 해시 함수(Hash Function)을 통해 인덱스를 구하고 해당 인덱스의 연결 리스트(Linked List)를 선형적으로 검사하여 해당 키(Key)의 노드(Node)가 존재하는지 확인하고 값(Value)를 리턴한다.

- 삭제는 검색과 동일하게 해당 인덱스의 연결 리스트(Linked List)를 선형적으로 검사하여 해당 키(Key)의 노드(Node)를 삭제하면 된다.

- 연결 리스트(Linked List)를 이용하기 때문에 추가할 수 있는 데이터의 제약이 적다.

- 부하율(Load Factor, 전체 버킷에서 사용중인 버킷의 비율)이 100%에 가까울수록 삽입, 삭제, 검색의 효율이 비약적으로 낮아진다. 일반적으로는 80%로 제한한다. (Java의 HashMap의 경우 75%)

- 구현하기 간단하고 기본적인 자료구조 정도만 요구한다.

- 해시 함수(Hash Function) 구현(선택)하는 관점에서, Chaining Hash Table의 경우 클러스터링(Clustering)에 거의 영향을 받지 않아 충돌의 최소화만 중점적으로 고려하면 된다.

- 해시 테이블의 버킷(Bucket)이 채워져도 성능 저하가 선형적으로 발생한다.

- 테이블의 높은 부하율(Load Factor)가 예상되거나, 데이터가 크거나, 데이터의 길이가 가변일 때 성능이 좋아진다.

※ JDK 1.8(Java 8)에서는 슬롯(Slot)의 갯수가 8개 이하일 경우 연결 리스트(Linked List)를 사용하며 그 이상의 경우는 트리(Tree) 구조를 사용하여 검색의 효율을 높이고 있다.

<충돌 방지 - 체이닝 방식>

● Open Addressing 방식

- 충돌이 발생했을 경우 연결 리스트(Linked List)같은 추가적인 메모리를 사용하지 않고 해시 테이블(Hash Table)의 빈 버킷(Bucket)을 이용하는 방법이다.

- 충돌이 발생하면 다른 버킷(Bucket)에 저장하기 때문에 데이터의 주소 값(인덱스)이 바뀐다.

- 삽입시 메모리 할당 오버헤드가 없으며, 메모리 할당자가 없이도 구현이 가능하다.

- 외부 저장공간이 없기 때문에 외부 공간에 필요한 추가적인 작업이 요구되지 않는다.

- 특히 선형 검색법(Linear Probing)에서 Separate Chaining보다 뛰어난 참조 지역성(Locality of reference, 하나의 자원에 여러번 접근하는 프로세스)을 가진다. 이러한 특성으로 적은 데이터에서 특히 Lookup 연산에서 Separate Chaining보다 좋은 성능을 보인다.

- 포인터(Pointer)를 사용하지 않음으로써 직렬화(Serialization)가 용이하다.

- 테이블에 모두 저장될 수 있고, 캐시 라인에 적합할 수 있을 정도로 데이터의 크기가 작을수록 성능이 좋아진다.

- 삭제의 경우 충돌(Collision)에 의해 뒤에 저장된 데이터가 검색되지 않을 수 있다. 이를 방지하기 위해 삭제한 위치에 Dummy Node를 삽입한다. Dummy Node는 실제 값을 가지지는 않지만, 검색할 때 다음 위치(인덱스)까지 연결해주는 역할을 한다. 하지만 삭제가 빈번히 일어날 경우 Dummy Node 수가 많아져서 검색할 경우에 많은 버킷(Bucket)을 연속적으로 검색해야 하기 때문에 이 Dummy Node의 개수가 일정 수 이상이 되었을 경우에 주기적으로 새로운 배열을 만들어고 재해시(Rehash)를 해줘야 성능을 유지할 수 있다.

- 선형 검색(탐사)법(Linear Probing)

· 충돌을 해결할 수 있는 가장 간단한 해결법이다.

· 충돌 발생시 새로운 키(Key)를 저장할 기억공간을 찾기 위해 충돌이 일어난 그 위치에서 선형적으로 검색하여 첫 번째 빈 영역에 키를 저장하는 방법이다.

· 테이블의 끝에 도달하게 되면 처음으로 되돌아 간다.

· 조사를 시작한 위치로 되돌아 오게 되면 테이블이 가득찬 것이다.

· 장점 : 구조가 간단하고 캐시의 효율이 높다.

· 단점 : 최악의 경우 해시 테이블(Hash Table) 전체를 검색해야 하는 상황이 발생할 수 있으므로 비효율적이고, 데이터의 클러스터링(Clustering)에 가장 취약하다.

<충돌 방지 - 선형 검색법>

- 2차 검색(탐사)법(Quadratic Probing)

· 선형 검색법(Linear Probing)에서 발생하는 제1밀집(primary clustering) 문제를 제거하는 방법이다.

· 같은 해시 값을 갖는 키(Key)에 대해서는 제2밀집(secondary clustering) 발생

· 원래 저장할 위치로부터 1, 4, 9, 16, ... 과 같이 떨어진 영역을 차례대로 검색하여 첫번째 빈 영역에 키를 저장하는 방법이다.

· 캐시 효율과 클러스터링(Clustering) 방지 측면에서 선형 검색법(Linear Probing)과 이중 해싱(Double Hashing)의 중간 정도의 성능이다.

<충돌 방지 - 2차 검색법>

- 이중 해싱(Double Hashing)

· 하나의 해시 함수(Hash Function)에서 충돌이 발생하면 2차 해시 함수를 이용해 검색 이동 거리를 얻는 방법이다.

· 캐시 효율은 떨어지지만 클러스터링(Clustering)에 영향을 거의 받지 않는다.

· 가장 많은 연산량을 요구한다.

<충돌 방지 - 이중 해싱>

- 무작위 검색법

· 충돌을 유발하는 키(Key)를 저장할 수 있는 가용 공간을 찾을 때까지 난수 계산 프로그램을 실행하여 해시 테이블(Hash Table)의 주소 값(인덱스)을 결정하는 방법이다.

● Coalesced Chaining(혹은Coalesced Hashing, 병합 체이닝)

- Separate Chaining과 Open Addressing을 혼합한 방식이다.

- 테이블 내의 버킷(Bucket)들끼리 서로 체인 링크(Chain Link)를 가지게 됨(Separate Chaining 방식은 각 버킷들끼리 고유한 체인 링크를 가짐)

- Separate Chaining 방식과는 다르게 버킷(Bucket)끼리 체인 링크(Chain Link)를 거는 방식이기 때문에 테이블 슬롯(Slot)보다 많은 수의 데이터를 저장할 수 없다.

- Separate Chaining 방식에 비해 메모리와 캐시 성능에서 우위를 가진다.

- Open Addressing 방식에 비해 클러스터링(Clustering)에 거의 영향을 받으며 실제로 테이블이 높은 밀도로 효과적으로 채워질 수 있다.

Resizing

Open Addressing에서 사용되는 고정 크기의 배열이 가득차거나 Separate Chaining에서 사용되는 연결 리스트(Linked List)가 길어지게 되면 검색 효율이 떨어지기 때문에 버킷(Bucket)의 갯수를 늘려줘야 한다. 이를 Resizing이라고 하며, 새로운 배열에 기존 배열의 키(Key)를 새롭게 재해싱(Rehashing)한다.

<오버플로우 발생 시 Resizing>

구현(Implementation)

● Java의 HashMap 클래스를 통해 구현해본 해시 테이블(Hash Table)이다.

● Separate Chaining 방식으로 충돌(Collision) 방지를 하였고, 문자열의 아스키(ASCII) 코드 값의 합을 이용하는 간단한 해시 함수(Hash Function)를 구현하였다.

※ 실제 OpenJDK의 내용을 살펴보려면 다음 링크를 참고 바람.

(http://www.grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/HashMap.java#HashMap)

class HashMap<K, V>
{
    // 기본 배열의 크기
    private final int DEFAULT_CAPACITY = 16;
    private Node[] array;
    
    // Separate Chaining 방식에서 사용될 Node 클래스
    static class Node<K, V>
    {
        Node<K, V> next;    // 다음 Node
        K key;                    // Node 안의 키
        V value;                // Node 안의 키가 가르키는 값
        
        Node(K key, V value, Node<K,V> next)
        {
            this.key = key;
            this.value = value;
            this.next = next;
        }
        
        public K getKey()
        {
            return key;
        }
        
        public V getValue()
        {
            return value;
        }
        
        public V setValue(V newValue)
        {
            V oldValue = value;
            value = newValue;
            
            return oldValue;
        }
        
        // Node의 요소를 출력하기 위해 Overriding한 메소드
        @Override
        public String toString()
        {
            if( next != null )
                return key + "->" + value + " | " + next.toString();
            
            return key + "->" + value;
        }
    }
    
    public HashMap()
    {
        array = new Node[DEFAULT_CAPACITY];
    }
    
    // 키에 대한 hash 값을 구하는 메소드
    // 단순히 키를 문자열로 바꾼후 해당 문자의 아스키(ASCII) 값의 합을 이용하는 해시 함수 사용
    // 배열의 크기를 넘지 않기 위해 나머지 연산(Modular)을 사용
    int hash(K key)
    {
        int hash = 0;
        
        for( int i = 0; i < key.toString().length(); ++i )
        {
            char c = key.toString().charAt(i);
            hash += (int) c;
        }
        
        return hash % DEFAULT_CAPACITY;
    }
    
    public V put(K key, V value)
    {
        return putVal(key, value, hash(key));
    }
    
    public V putVal(K key, V value, int hash)
    {
        Node<K, V> node = getNode(hash, key);
        
        if( node != null )
            return node.setValue(value);
        else
        {
            if( array[hash] == null )
                array[hash] = new Node(key, value, null);
            else
            {
                node = array[hash];
                
                while( node.next != null )
                {    
                    node = node.next;
                }
                node.next = new Node(key, value, null);
            }
        }
        
        print();
        return null;
    }
    
    public V get(K key)
    {
        Node<K, V> node = getNode(hash(key), key);
        
        return node == null? null: node.getValue();
    }
    
    // 배열 내에 키 값이 존재하지는 확인 후 존재하면 해당 키가 있는 Node 리턴
    public Node<K, V> getNode(int hash, K key)
    {
        Node<K, V> node = array[hash];
        
        while( node != null && node.next != null )
        {
            if( node.getKey().equals(key) )
            {
                return node;
            }
            
            node = node.next;
        }
        return null;
    }
    
    public V replace(K key, V value)
    {
        Node<K, V> node = getNode(hash(key), key);
        
        if( node != null )
            return node.setValue(value);
        
        return null;
    }
    
    public V remove(K key)
    {
        return removeNode(hash(key), key);
    }
    
    public V removeNode(int hash, K key)
    {
        Node<K, V> node = array[hash];
        Node<K, V> preNode = null;
        V oldValue = null;
        
        while( node != null )
        {
            if( node.getKey().equals(key) )
            {
                oldValue = node.getValue();
                
                if( preNode == null )
                    array[hash] = node.next;
                else
                    preNode.next = node.next;
                
                node = null;
                break;
            }
            
            preNode = node;
            node = node.next;
        }
        
        print();
        return oldValue;
    }
    
    // 배열 요소를 출력하기 위한 메소드
    void print()
    {
        for( int i = 0; i < array.length; ++i )
            System.out.println(array[i] == null? null: array[i].toString());
        System.out.println("--------------------------------------------------------------------");
    }
}

참고 자료(References)

[위키 피디아] https://en.wikipedia.org/wiki/Hash_table

[조대협의 블로그] http://bcho.tistory.com/1072

[Naver D2 Java HashMap은 어떻게 동작하는가?] http://d2.naver.com/helloworld/831311

[Egloos 수까락의 프로그래밍 이야기] http://egloos.zum.com/sweeper/v/925740

[Luyin 블로그] http://luyin.tistory.com/191

[KimKyungKun SlidesShare 해싱(Hashing)] https://www.slideshare.net/KimKyungKun/hashing-10748635