해시에 대해서

안녕하세요, 오늘 글을 끝으로 자료구조와 알고리즘 파트의 기초 개념 설명을 모두 마무리하려고 합니다.
마지막으로 알아볼 자료구조는 해시이며 양이 많지도 않고 크게 어렵지 않기 때문에 힘을 내서 공부해봅시다.

🔐 해시법이란?

해시법은 배열 속에 데이터를 저장할 위치를 간단한 연산으로 구하는 방법으로 검색뿐만 아니라 추가, 삭제도 효율적으로 수행할 수 있습니다. 아래의 그림에서 가장 위에 위치한 배열의 키 값인 배열 속 각각의 요소 값을 배열의 요솟수 13으로 나눈 후 나머지를 표로 정리하면 중간에 위치한 표와 같게 됩니다. 이렇게 표에 정리한 값을 해시 값이라고 하며 이러한 과정을 해시 함수라고 합니다.

 

그리고 이 해시 값이 기존의 배열 속 키 값들의 새로운 인덱스가 되도록 수정한 것이 아래의 그림 속 가장 아래에 위치한 배열이며 이를 해시 테이블이라고 부릅니다. 정리하자면 배열 속 각각의 키 값을 배열의 요솟수로 나눈 후 나머지를 해시 값이라고 하며 이 해시 값이 배열의 인덱스가 되도록 원래의 키 값을 저장한 배열을 해시 테이블이라고 부릅니다. 해시 값과 테이블의 개념은 중요합니다.

이번에는 해시 테이블에 숫자 35를 추가하는 경우를 생각해보겠습니다. 먼저 숫자가 배열에서 저장될 위치를 구하기 위해 35를 배열 요솟수인 13으로 나눕니다. 해시 함수를 통해 구한 해시 값이 9이므로 배열 속 9번 째 인덱스 자리에 숫자 35를 저장합니다. 이처럼 해시 테이블은 새롭게 값을 추가하더라도 기존의 일반적인 배열과 달리 해시 테이블 배열 속 다른 요소를 옮기지 않아도 되므로 기존의 배열보다 효율이 훨씬 좋은 모습을 볼 수 있습니다. 또한 해시 테이블의 각 요소를 버킷이라고 부르니 꼭 기억해주시기 바랍니다.

 

⛔️ 충돌이란?

앞에서 보았던 해시 테이블에 이번에는 숫자 18을 추가해보겠습니다. 먼저 숫자 18을 배열 요솟수인 13으로 나누어 해시 값을 구합니다. 해시 함수를 통해 구한 해시 값이 5이므로 배열 속 5번째 인덱스 자리에 숫자 18을 추가하려고 했으나 배열 속 5번째 인덱스인 이 버킷에는 이미 다른 숫자인 5가 저장되어 있는 상황입니다. 이처럼 특정 값을 저장할 버킷이 중복되는 현상을 충돌이라고 합니다.

 

이러한 상황에서 알 수 있듯이 해시 테이블에서는 키 값과 해시 값의 대응 관계가 반드시 1대 1이라는 보장이 없으며 보통 n 대 1의 관계를 가지고 있습니다. 그래서 해시 함수는 가능하면 해시 값이 치우치지 않도록 고르게 분포된 값을 만들어야 합니다. 하지만 그러는 것이 많이 힘들다는 것을 잘 알고 있기에 해시 테이블에서 충돌이 발생할 경우를 대비해 아래의 두 가지 방법을 제공하고 있습니다.

 

체인법 : 같은 해시 값을 갖는 요소를 연결 리스트로 관리합니다.

오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복합니다.

# 체인법

체인법은 같은 해시 값을 갖는 데이터를 쇠사슬 모양으로 연결 리스트에서 연결하는 방법으로 오픈 해시법이라고도 부릅니다. 아래는 해시를 체인법으로 구현한 예시이며 배열의 각 버킷에는 해당 인덱스를 해시 값으로 하는 연결 리스트의 첫 번째 노드에 대한 참조 값이 저장됩니다. 그러나 만약 해당 인덱스를 해시 값으로 하는 노드가 하나도 존재하지 않는다면 그 버킷의 값은 NULL이 저장됩니다.

 

본격적으로 체인법을 구현해보겠습니다. 먼저 해시 테이블에서 같은 해시 값을 갖는 노드들을 연결 리스트로 구성하기 위해 각각의 노드들에 대해서 알아봅시다. 아래는 체인법에서의 노드 클래스이며 3개의 필드가 존재합니다. key라는 변수는 특정 노드의 고유 키 값을 뜻하며 해시 테이블 속 한 버킷의 연결 리스트에서는 각각의 노드 별로 이 key 값이 무조건 달라야 합니다. 그리고 data 변수는 한 노드의 데이터 값을 의미합니다. key와 data 변수는 제네릭 형태의 자료형이므로 실질적인 value가 아닌 reference 변수입니다.

 

또한 next 변수는 같은 연결 리스트 내에 위치한 특정 노드의 다음 노드에 대한 참조 값이 저장됩니다. 이처럼 next 변수가 연결 리스트 내에서 각각의 노드들을 연결하는 과정이 체인 즉 쇠사슬과 유사하다는 점이 있어 체인법이라고 이름이 지어진 것입니다. 그러나 만약 연결 리스트 내에서 특정 노드의 뒤에 다음 노드가 존재하지 않을 경우에는 NULL이 대입되는 것을 기억해주시기 바랍니다.

class Node<K, D> {
    K key;
    D data;
    Node<K, D> next;
}

아래의 코드는 체인법을 바탕으로 해시의 다양한 기능들을 구현한 예제입니다. 체인법을 활용하면 해시 테이블에서 같은 해시 값을 가진 노드가 여러 개가 존재하더라도 연결 리스트 방식으로 문제를 해결할 수 있습니다. 각각의 메서드들에 대해서 한 개씩 설명을 해주면 좋으나 양이 많기도 하고 위에서 배웠던 내용으로 충분히 이해하실 수 있을 것 같아 코드에 대한 상세한 설명은 생략하겠습니다.

// 체인법을 통한 해시 클래스
public class ChainHash<K, D> {

    // 노드 클래스
    class Node<K, D> {
        private K key;
        private D data;
        private Node<K, D> next;

        // 생성자
        Node(K key, D data, Node<K, D> next) {
            this.key = key;
            this.data = data;
            this.next = next;
        }

        // 키 값을 반환하는 메서드
        K getKey() {
            return key;
        }

        // 데이터를 반환하는 메서드
        D getData() {
            return data;
        }

        // 키의 해시 값을 반환하는 메서드
        public int hashCode() {
            return key.hashCode();
        }
    }

    // 해시 테이블의 크기 & 해시 테이블 배열
    private int size;
    private Node<K, D>[] table;

    // 생성자
    public ChainHash(int capacity) {
        try {
            table = new Node[capacity];
            size = capacity;
        } catch (OutOfMemoryError e) {
            size = 0;
        }
    }

    // 해시 값을 구하는 메서드
    public int hashValue(K key) {
        return key.hashCode() % size;
    }

    // 키 값으로 요소를 검색하는 메서드
    public D search(K key) {
        int hash = hashValue(key);
        Node<K, D> p = table[hash];

        while (p != null) {
            if (p.getKey().equals(key)) return p.getData();
            else p = p.next;
        }
        return null;
    }

    // 요소를 추가하는 메서드
    public boolean add(K key, D data) {
        int hash = hashValue(key);
        Node<K, D> p = table[hash];

        while (p != null) {
            if (p.getKey().equals(key)) return false;
            else p = p.next;
        }
        Node<K, D> temp = new Node<>(key, data, table[hash]);
        table[hash] = temp;
        return true;
    }
    
    // 요소를 삭제하는 메서드
    public boolean remove(K key) {
        int hash = hashValue(key);
        Node<K, D> p = table[hash];
        Node<K, D> pp = null;

        while (p != null) {
            if (p.getKey().equals(key)) {
                if (pp == null) table[hash] = p.next;
                else pp.next = p.next;
                return true;
            }
            pp = p;
            p = p.next;
        }
        return false;
    }

    // 해시 테이블의 모든 내용을 출력하는 메서드
    public void dump() {
        for (int i = 0; i < size; i++) {
            Node<K, D> p = table[i];
            System.out.printf("%02d  ", i);

            while (p != null) {
                System.out.printf("-> %s (%s)  ", p.getKey(), p.getData());
                p = p.next;
            }
            System.out.println();
        }
    }
}

🌏 오픈 주소법

충돌 문제를 해결할 수 있는 두 번째 방법인 오픈 주소법은 충돌이 발생했을 때 재해시를 수행하여 해시 테이블 속에 비어있는 버킷을 찾아내는 방법으로 닫힌 해시법이라고도 불립니다. 아래는 오픈 주소법의 재해시를 이해하기 위해 간단한 예시를 표현한 것입니다.

 

아래의 해시 테이블에서 숫자 18을 추가하려고 합니다. 숫자 18의 해시 값은 5이므로 배열 속 5번째 인덱스 자리에 숫자를 추가하려고 했으나 충돌이 발생했습니다. 앞에서 배운 체인법은 문제를 해결하기 위해 연결 리스트를 구성했지만 오픈 주소법은 재해시를 수행합니다. 보통 재해시를 할 때는 기존에 추가하려는 숫자에 1을 더한 후 해시 값을 다시 구합니다. 아래의 상황에서 재해시를 한 후 새롭게 구한 해시 값이 6이므로 배열 속 6번째 인덱스에 기존의 숫자 18을 추가하려고 했으나 또다시 충돌 현상이 발생했습니다. 

 

다시 한번 더 재해시를 수행한 후 구한 해시 값이 이번에는 7이므로 배열 속 7번째 인덱스에 기존의 숫자 18을 추가합니다. 배열 속 7번 째 인덱스 즉 이 버킷에는 현재 다른 값이 존재하고 있지 않은 상황이기에 숫자 18을 문제없이 정상적으로 추가할 수 있습니다. 이처럼 오픈 주소법은 해시 테이블 내에서 빈 버킷을 만날 때까지 재해시를 여러 번 반복하는 과정을 보며 선형 탐사법이라고도 합니다.

 

그럼 지금부터 오픈 주소법을 구현해보도록 하겠습니다. 앞에서 배웠던 체인법에서의 해시 테이블 속 각각의 버킷은 같은 해시 값을 가지는 노드들의 연결 리스트 중 첫 번째 노드를 참조하는 역할을 한다고 했으나 실질적으로 버킷보다 노드의 역할이 더 컸습니다.

 

하지만 오픈 주소법은 연결 리스트를 따로 구성하지 않기에 노드가 존재하지 않으며 이를 대신해 버킷이 정말 중요한 역할을 합니다. 아래는 오픈 주소법의 버킷 클래스이며 3개의 필드가 존재합니다. 그중 key와 data 변수는 앞에서 보았던 체인법의 Node 클래스 속 변수와 같이 특정 버킷에 대한 고유 키 값 그리고 데이터를 의미하며 이들은 실질적인 value가 아닌 reference 변수입니다. 

class Bucket<K, D> {
    K key;
    D data;
    Status stat;
}

또한 이전의 Node 클래스에서는 존재하지 않던 stat이라는 변수가 Bucket 클래스에서 새롭게 추가되었습니다. 이는 해시 테이블 내의 각각의 버킷에 관한 상태를 나타냅니다. stat 변수의 자료형은 Status라는 Enum 클래스이며 OCCUPIED, EMPTY, DELETED와 같이 3가지의 상태 정보를 가지고 있습니다. 해시 테이블 내에서 데이터가 새롭게 추가되고 삭제되는 과정 속에서 각각의 버킷은 stat 변수를 상황에 맞게 업데이트합니다. Bucket 클래스에서 stat 변수는 정말 중요한 역할을 맡고 있으니 자세히 알아두세요!

enum Status {
    OCCUPIED,
    EMPTY,
    DELETED
}

아래의 코드는 오픈 주소법을 바탕으로 해시의 다양한 기능을 구현한 예제입니다. 위에서 설명했던 오픈 주소법의 개념만으로도 아래의 코드를 충분히 이해하실 수 있을 것이라고 생각해 이번 역시 상세한 설명은 따로 하지 않겠습니다. 오픈 주소법의 특징을 잘 기억하면서 코드를 천천히 분석해보시기 바랍니다. 특히 앞에서도 강조했던 stat 변수의 상태 변화를 유의 깊게 관찰하시기 바랍니다.

// 오픈 주소법을 통한 해시 클래스
public class OpenHash<K, D> {

    // 버킷 상태에 관한 이넘 클래스
    enum Status {
        OCCUPIED,
        EMPTY,
        DELETED
    }

    // 버킷 클래스
    static class Bucket<K, D> {
        private K key;
        private D data;
        private Status stat;

        // 생성자
        Bucket() {
            stat = Status.EMPTY;
        }

        // 모든 필드에 값을 추가하는 메서드
        void set(K key, D data, Status stat) {
            this.key = key;
            this.data = data;
            this.stat = stat;
        }

        // 버킷 상태를 업데이트 하는 메서드
        void setStat(Status stat) {
            this.stat = stat;
        }

        // 키 값을 반환하는 메서드
        K getKey() {
            return key;
        }

        // 데이터를 반환하는 메서드
        D getData() {
            return data;
        }

        // 키의 해시 값을 반환하는 메서드
        public int hashCode() {
            return key.hashCode();
        }
    }

    // 해시 테이블의 크기 & 해시 테이블 배열
    private int size;
    private Bucket<K, D>[] 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 = size;
        }
    }

    // 해시 값을 구하는 메서드
    public int hashValue(K key) {
        return key.hashCode() % size;
    }

    // 재해시 값을 구하는 메서드
    public int reHashValue(int hash) {
        return (hash + 1) % size;
    }

    // 키 값을 갖는 버킷을 검색하는 메서드 (아래의 search 메서드와 관련)
    private Bucket<K, D> searchNode(K key) {
        int hash = hashValue(key);
        Bucket<K, D> p = table[hash];

        for (int i = 0; p.stat != Status.EMPTY && i < size; i++) {
            if (p.stat == Status.OCCUPIED && p.getKey().equals(key)) return p;
            hash = reHashValue(hash);
            p = table[hash];
        }
        return null;
    }

    // 키 값으로 요소를 검색하는 메서드
    public D search(K key) {
        Bucket<K, D> p = searchNode(key);
        if (p != null) return p.getData();
        else return null;
    }

    // 요소를 추가하는 메서드
    public boolean add(K key, D data) {
        if (search(key) != null) return false;

        int hash = hashValue(key);
        Bucket<K, D> p = table[hash];

        for (int i = 0; i < size; i++) {
            if (p.stat != Status.OCCUPIED) {
                p.set(key, data, Status.OCCUPIED);
                return true;
            }
            hash = reHashValue(hash);
            p = table[hash];
        }
        return false;
    }

    // 요소를 삭제하는 메서드
    public boolean remove(K key) {
        Bucket<K, D> p = searchNode(key);
        if (p == null) return false;

        p.setStat(Status.DELETED);
        return true;
    }

    // 해시 테이블의 모든 내용을 출력하는 메서드
    public void dump() {
        for (int i = 0; i < size; i++) {
            System.out.printf("%02d  ", i);
            switch (table[i].stat) {
                case OCCUPIED:
                    System.out.printf("%s (%s)\n", table[i].getKey(), table[i].getData()); break;

                case EMPTY:
                    System.out.println("-- 미등록 --"); break;

                case DELETED:
                    System.out.println("-- 삭제 마침 --"); break;
            }
        }
    }
}

👍 글을 마치며

이렇게 해서 해시 자료구조에 대한 글 작성을 모두 마무리하였습니다. 앞에서도 말했듯이 오늘 작성한 글을 끝으로 자료구조와 알고리즘 파트의 기초 개념 설명을 모두 마무리하려고 합니다. 기본적인 자료구조는 거의 모두 공부한 것 같다는 판단이 들어 앞으로는 알고리즘 문제 풀이에 더욱 초점을 두어 공부할 생각입니다. 지금까지 자료구조 공부를 한다고 고생 많았으며 앞으로도 힘을 내서 함께 나아갑시다. 혹시 시간이 된다면 이전의 자료구조 내용들을 다시 한번 읽어보면서 복습하시는 것을 추천드립니다. 감사합니다.

 

참고 : Do it 자료구조와 함께 배우는 알고리즘 입문 자바 편