Hash 자료구조와 해시 충돌

Hash Table 이란

Hash Table은 데이터를 key-value 형식으로 보관하여 검색 · 삽입 · 삭제를 O(1) 시간 복잡도로 수행할 수 있는 자료구조이다.

 

Hash Table은 key 값을 통해 데이터를 다루기 때문에, key 값은 고유해야한다.

 

이러한 고유한 key 값을 만드는 작업은 해시 함수가 담당하는데,

 

대표적으로는 key 값의 ASCII 값을 합하여 만드는 간단한 방법이 있다.

 

이러한 해시 함수가 key를 만드는 과정에서, 의도하지 않게 우연히 key 값이 일치하는 경우가 발생할 수 있는데

 

💡 이를 해시 충돌이라고 한다.

 

해시 충돌이 발생하면, key 값이 중복되어 데이터가 사라질 수 있다. 따라서 해시 충돌이 발생하면 대처해야한다.

 

대표적인 방법으로는

 

1. 체인법 (Seperate Chaning)
2. 오픈 주소법 (Open Addressing) 

두가지 방법이 있다.

 

해시 충돌 대처법

 

체인법

체인법은 해시 값이 같은 데이터를 사슬(chain) 모양의 연결 리스트로 연결하는 방법이다.

 

위 그림과 같이 key 값이 152인 위치에 John Smith 데이터가 존재하는데

 

Sandra Dee 역시 key 값이 152 로 해시 충돌이 발생했다.

 

이런 경우 key 값에 해당하는 각 value는 연결리스트로 구성해놓고, value가 들어올때 마다 노드를 추가해주는 방식으로 대처할 수 있다.

 

🚨 참고로 연결리스트를 키 값을 해싱한 값으로 찾아가고, 연결리스트를 순회하면서 해싱하기 전 키 값과 일치하는 노드가 나올때까지 탐색하는 작업으로 원하는 노드를 찾을 수 있게 된다.

 

Node 정의

public class ChainHash<K, V> {

    class Node<K, V> {
        private K key;
        private V value;
        private Node<K, V> next;

        public Node(K key, V value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        K getKey() {
            return key;
        }

        V getValue() {
            return value;
        }

        public int hashCode() {
            return key.hashCode();
        }
 }

 

기본 구성 틀은 위와 같다.

 

키 값인 K에 해당하는 곳에 Node<K,V> 노드 클래스가 존재한다.

 

그리고 이 노드는 다음 노드를 참조할 수 있으므로, 해시 충돌이 발생했을 때 next 변수에 다른 노드를 연결시켜주면 된다.

 

 

Hash table 정의

public class ChainHash<K,V> {

    private int size;
    private Node<K, V>[] table;

    public ChainHash(int size) {
        try {
            table = new Node[size];
            this.size = size;
        } catch (OutOfMemoryError e) {
            this.size = 0;
        }
    }
    
    public int hashValue(Object key) {
        return key.hashCode() % size;
    }
}

이전에 정의한 Node를 활용하여 테이블을 생성한다.

 

검색

    public V search(K key) {
        // 키 값에 해당하는 해시 값으로 접근
        int hash = hashValue(key);
        Node<K, V> node = table[hash];

        // 해시값에 해당하는 연결리스트에 일치하는 키값을 가진 노드가 나타날 때까지 탐색
        while (node != null) {
            if (node.getKey().equals(key)) {
                return node.getValue();
            }
            node = node.next;
        }

        // 검색 실패
        return null;
    }

이전에 설명했듯, 키 값을 해싱한 값으로 연결리스트에 접근한다.

 

연결리스트에 접근해서는, 해싱하기 전 키 값과 일치하는 키를 가진 노드를 발견할때까지 순회한다.

 

추가

    public int add(K key, V value) {
        int hash = hashValue(key);

        // 해시값에 해당하는 연결리스트 접근
        Node<K, V> node = table[hash];

        // 빈 노드로 접근
        while (node != null) {
            // 만약 입력하려는 키 값에 해당하는 노드가 이미 존재한다면 
            if (node.getKey().equals(key)) {
                return 1;
            }

            node = node.next;
        }

        // 노드 생성 후 입력
        Node<K, V> temp = new Node<K, V>(key, value, table[hash]);
        table[hash] = temp;
        return 0;
    }

 

추가 역시, 검색과 유사하게, 해시 값에 해당하는 노드로 접근해서 빈 노드가 나올때까지 이동한 뒤

 

노드를 추가하는 방식으로 구현하면 된다.

 

오픈 주소법

체이닝 방식은 노드를 계속 추가해주다보면 추가적인 메모리를 사용하게 된다.

 

오픈 주소법은 추가 공간을 사용하지 않고 해결하는 방법이다.

 

💡 충돌이 일어났을 때, 정해진 규칙에 따라 다른 자리를 찾아 저장하는 방식으로 해시 충돌을 대처한다.

 

대표적으로는 충돌이 발생했을 때 재해시를 수행하여 비어있는 버킷을 찾아내는 방법이 있다.

 

Bucket 정의

public class OpenHash<K, V> {
    enum Status {OCCUPIED, EMPTY, DELETED}

    static class Bucket<K, V> {
        private K key;
        private V value;
        private Status status;

        public Bucket() {
            this.status = Status.EMPTY;
        }

        void set(K key, V value, Status status) {
            this.key = key;
            this.value = value;
            this.status = status;
        }

        void setStatus(Status status) {
            this.status = status;
        }

        K getKey() {
            return this.key;
        }

        V getValue() {
            return this.value;
        }

        public int hashCode() {
            return this.key.hashCode();
        }
    }

}

해시 테이블의 해시로 접근하면 위와 같은 버킷이 존재하고

 

각 버킷은 상태를 나타내는 status 필드를 갖는다.

 

이 status 필드를 갖는 이유는, 탐색 시 재 해시 하면서 버킷의 키와 일치하는지 확인해야하는데

 

3번 재해시 된 데이터를 찾는 경우, 2번째 재해시된 데이터가 삭제되면 데이터를 찾지 못하는 경우가 발생할 수 있기 때문에

 

데이터 삭제 시, DELETE 표시로 삭제 됨을 나타내주기 위함이다.

 

Hash Table 정의

public class OpenHash<K, V> {

    private int size;
    private Bucket<K, V>[] table;

    public OpenHash(int size) {

        try {
            table = new Bucket[size];
            for (int i = 0; i < size; i++) {
                table[i] = new Bucket<>();
            }
            this.size = size;
        } catch (OutOfMemoryError e) {
            this.size = 0;
        }
    }

    public int hashValue(Object key) {
        return key.hashCode() % size;
    }

    public int rehashValue(int hash) {
        return (hash + 1) % size;
    }
}

이전에 정의한 Bucket 을 갖는 배열을 생성해준다.

 

그리고, 해시 충돌 발생 시 다른 해시 값을 반환하도록 하는 rehashValue 메서드도 정의해준다.

 

검색

	public V search(K key) {
        Bucket<K, V> bucket = searchNode(key);

        return bucket == null ? null : bucket.getValue();
    }

    private Bucket searchNode(K key) {
        int hash = hashValue(key);
        Bucket<K, V> bucket = table[hash];

		// 버켓이 EMPTY 가 아닐때까지 검색, DELETE 된 버킷이어도 검색 진행 됨
        for (int i = 0; bucket.status != Status.EMPTY && i < size; i++) {
            if (bucket.status == Status.OCCUPIED && bucket.getKey().equals(key)) {
                return bucket
            }
            hash = rehashValue(hash);
            bucket = table[hash];
        }

        return null;
    }

검색 시, 버켓의 상태가 EMPTY 가 아니라면 재해시를 반복해서 원하는 키값을 가진 버켓이 발견될때까지 진행한다.

 

추가

    public int add(K key, V value) {
        // 이미 존재하는 경우
        if (search(key) != null) {
            return 1;
        }

        int hash = hashValue(key);
        Bucket<K, V> bucket = table[hash];
        for (int i = 0; i < size; i++) {
        	// 해당 버켓이 비어있거나 DELETED 된 상태인 경우 데이터 추가
            if (bucket.status == Status.EMPTY || bucket.status == Status.DELETED) {
                bucket.set(key, value, Status.OCCUPIED);
                return 0;
            }
            hash = rehashValue(hash);
            bucket = table[hash];
        }

        // 테이블이 가득 찬 경우
        return 2;
    }

추가하는 과정 역시, 재해시 과정을 거치면서 비어있거나 삭제되어 사용되지 않는 버켓을 찾고

 

그 버켓에 데이터를 집어 넣는 방식으로 동작한다.

 

체인법과 오픈 주소법의 특징(장단점)

💡 그렇다면 각 방식의 특징을 다시 정리해보자.

 

1. 체인법
   1. 연결 리스트를 사용하여 해시코드를 다시 계산해야하는 절차가 필요없다.
   2. 특정 해시 값에 연결 리스트가 많이 추가되면 성능이 저하되고 추가적인 메모리를 사용하게된다.
   3. 해시 테이블의 자체의 크기(노드 개수 말고)를 동적으로 조정하기 어렵다.
      
      
2. 오픈 주소법
   1. 추가적인 메모리 공간이 필요없다.
   2. 최악의 경우 테이블 전체를 검색해야할 수 있고 테이블의 로드 팩터(테이블의 가득 찬 정도)가 금방 도달하여 리사이징이 필요할 수 있다.
   3. 동적으로 크기를 조정하기 쉽다.