[자료구조] 해시 테이블(Hash Table)

  해시 테이블(Hash Table)이란, 키와 값을 대응시켜 저장하는 데이터 구조입니다. 키를 배열의 인덱스로 그대로 사용하면 메모리 낭비가 심해질 수 있습니다. 해시 테이블에서는 이러한 문제를 해결하여 키를 간단한 함수를 사용해 변환한 값을 배열의 인덱스로 이용하여 항목을 저장합니다. 이를 해싱(Hashing)이라고 합니다. 해싱에 사용되는 함수를 해시 함수(Hash Function), 해시 함수가 계산한 값을 해시값(Hash value) 또는 해시 주소라고 합니다.

 

  배열을 이용하여 해시 테이블 직접 구현한 코드

class HashTable {
    Integer[] table;
    int elementCount;

    HashTable() {}
    HashTable(int size) {
        this.table = new Integer[size];
        this.elementCount = 0;
    }
    public int getHash(int key) {
        return key % this.table.length;
    }
    public void setValue(int key, int data) {
        int index = this.getHash(key);
        this.table[index] = data;
        this.elementCount++;
    }
    public int getValue(int key) {
        int index = this.getHash(key);
        return this.table[index];
    }
    public void removeValue(int key) {
        int index = this.getHash(key);
        this.table[index] = null;
        this.elementCount--;
    }
}

 

  두 개 이상의 항목을 해시 테이블의 동일한 원소에 저장되는 것처럼, 서로 다른 키들이 동일한 해시값을 가질 때 충돌(Collision)이 발생했다고 합니다.

  충돌 해결 방법은 크게 두 가지로, 개방 주소 방식(Open Addressing)과 폐쇄 주소 방식(Closed Addressing)으로 나뉩니다. 개방 주소 방식은 충돌된 키를 해시 테이블 전체를 열린 공간으로 여기어 비어 있는 곳을 찾아 항목을 저장합니다. 세부적으로는 비어 있는 공간 탐색 방법에 따라 분류하는데 선형 탐사법(Linear Probing), 제곱 탐사법(Quadratic Probing), 이중 해싱(Double Hashing)이 있습니다.

 

  선형 탐사법 구현 코드

class HashTable2 extends HashTable {
    HashTable2(int size) {
        super(size);
    }
    public void setValue(int key, int data) {
        int index = this.getHash(key);
        if (this.elementCount == this.table.length) {
            System.out.println("Hash table is full");
        } else if (this.table[index] == null) {
            this.table[index] = data;
        } else {
            int newIndex = index;
            while (true) {
                newIndex = (newIndex + 1) % this.table.length;
                if (this.table[newIndex] == null) {
                    break;
                }
            }
            this.table[newIndex] = data;
        }
        elementCount++;
    }
}

  선형 탐사법은 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사합니다. 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 일차 군집화 문제가 발생할 수 있습니다.

 

  제곱 탐사법 구현 코드

class HashTable3 extends HashTable {
    HashTable3(int size) {
        super(size);
    }
    public void setValue(int key, int data) {
        int index = this.getHash(key);
        if (this.elementCount == this.table.length) {
            System.out.println("Hash table is full");
        } else if (this.table[index] == null) {
            this.table[index] = data;
        } else {
            int newIndex = index;
            int count = 0;
            while (true) {
                newIndex = (newIndex + (int)Math.pow(2, count)) % this.table.length;
                if (this.table[newIndex] == null) {
                    break;
                }
                count++;
            }
            this.table[newIndex] = data;
        }
        this.elementCount++;
    }
}

  제곱 탐사법은 충돌 발생 지점부터 이후의 빈 공간을 n제곱만큼의 간격을 두고 탐사합니다. 일차 군집화 문제는 일부 보완할 수 있으나 이차 군집화 문제가 발생할 수 있습니다.

 

  이중 해싱 구현 코드

class HashTable4 extends HashTable {
    int c;
    HashTable4(int size) {
        super(size);
        this.c = this.getHashC(size);
    }
    public int getHashC(int size) {
        int c = 0;
        if (size <= 2) {
            return size;
        }
        for (int i = size - 1; i > 2; i--) {
            boolean isPrime = true;
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                c = i;
                break;
            }
        }
        return c;
    }
    public int getHash2(int key) {
        int hash = 1 + key % this.c;
        return hash;
    }
    public void setValue(int key, int data) {
        int index = this.getHash(key);
        if (this.elementCount == this.table.length) {
            System.out.println("Hash table is full");
        } else if (this.table[index] == null) {
            this.table[index] = data;
        } else {
            int newIndex = index;
            int count = 1;
            while (true) {
                newIndex = (newIndex + this.getHash2(newIndex) + count) % this.table.length;
                if (this.table[index] == null) {
                    break;
                }
                count++;
            }
            this.table[newIndex] = data;
        }
        this.elementCount++;
    }
}

 

  이중 해싱은 해시 함수를 이중으로 사용합니다. 처음으로는 최초 해시를 구할 때 사용하고, 두 번째로는 충돌 발생 시 탐사 이동 간격을 구할 때 사용합니다. 선형 탐사법과 제곱 탐사법에 비해 데이터가 골고루 분포된다는 장점이 있습니다.

 

  분리 연결법 구현 코드

class Node {
    int key;
    int data;
    Node next;
    Node() {}
    Node(int key, int data, Node next) {
        this.key = key;
        this.data = data;
        this.next = next;
    }
}
class LinkedList {
    Node head;
    LinkedList() {}
    LinkedList(Node node) {
        this.head = node;
    }
    public boolean isEmpty() {
        return this.head == null;
    }
    public void addData(int key, int data) {
        if (this.head == null) {
            this.head = new Node(key, data, null);
        } else {
            Node cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = new Node(key, data, null);
        }
    }
    public void removeData(int data) {
        if (this.isEmpty()) {
            System.out.println("List is empty");
        }
        Node cur = this.head;
        Node pre = cur;
        while (cur != null) {
            if (cur.key == data) {
                if (cur == this.head) {
                    this.head = cur.next;
                } else {
                    pre.next = cur.next;
                }
                break;
            }
            pre = cur;
            cur = cur.next;
        }
    }
    public Integer findData(int data) {
        if (this.isEmpty()) {
            System.out.println("List is empty");
            return null;
        }
        Node cur = this.head;
        while (cur != null) {
            if (cur.key == data) {
                System.out.println("Data exist");
                return cur.data;
            }
            cur = cur.next;
        }
        System.out.println("Data not found");
        return null;
    }
}
class HashTable5 {
    LinkedList[] table;
    HashTable5(int size) {
        this.table = new LinkedList[size];
        for (int i = 0; i < this.table.length; i++) {
            this.table[i] = new LinkedList(null);
        }
    }
    public int getHash(int key) {
        return key % this.table.length;
    }
    public void setValue(int key, int data) {
        int index = this.getHash(key);
        this.table[index].addData(key, data);
    }
    public int getValue(int key) {
        int index = this.getHash(key);
        int data = this.table[index].findData(key);
        return data;
    }
    public void removeValue(int key) {
        int index = this.getHash(key);
        this.table[index].removeData(key);
    }
}

  반면에 폐쇄 주소 방식은 해시값에 대응하는 해시 테이블 원소에, 즉 충돌이 발생한 키를 동일한 해시 주소에 저장합니다. 그 중 하나가 분리 연결법(Separate Chaining)입니다. 이는 해시 테이블을 연결 리스트로 구성하여 충돌 발생 시 연결 리스트를 이용하여 해당 테이블에 데이터를 연결합니다. 그러나 원하는 값을 얻고자 할 때 (충돌이 발생하여) 일대일 대응이 아닐 수도 있는 탓에 앞선 탐사법에 비하면 느릴 수 있다는 단점이 있습니다.

 

  이외에도 기존의 해싱 방법을 융합하거나 변형한 새로운 해싱 방법도 많습니다. 체이닝과 개방 주소 방식을 통합한 융합 해싱(Coalesced Hashing), 체이닝과 동일하나 두 개의 해시 함수를 이용하여 연결 리스트의 길이가 짧은 쪽에 새 키를 저장하는 2-방향 체이징(Two-way Chaining), 두 개의 해시 함수와 두 개의 해시 테이블을 가지고 키들을 알고리즘에 따라 저장하는 뻐꾸기 해싱(Cuckoo Hashing) 등이 있습니다. 이상적인 해시 함수는 키를 균등하게(골고루 분포되게) 해시 테이블의 인덱스로 변환하는 함수입니다.

  어떤 해싱 방법도 해시 테이블에 비어있는 원소가 적으면, 삽입에 실패하거나 해시 성능이 급격히 저하되는 현상을 피할 수 없습니다. 이러한 경우, 해시 테이블을 확장시키고 새로운 해시 함수를 사용하여 모든 키를 새로운 해시 테이블에 다시 저장하는 재해시(Rehash)가 필요합니다. 이는 오프라인에서 이루어지고 모든 키를 다시 저장해야 하므로 O(n) 시간이 소요됩니다.

  동적 해싱(Dynamic Hashing)은 대용량 데이터베이스를 위한 해시 방법으로 재해싱을 수행하지 않고 동적으로 해시 테이블의 크기를 조절합니다. 대표적인 동적 해싱에는 디렉터리를 메인 메모리에 저장하고 데이터는 디스크 블록 크기의 버킷 단위로 저장하는 확장 해싱(Extendible Hashing)과 디렉터리 없이 삽입할 때 버킷을 순서대로 추가하는 선형 해싱(Linear Hashing)이 있습니다.

 

  ※ "자바와 함께하는 자료구조의 이해"라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추가하여 작성된 부분이 있습니다. 문제가 되거나 부정확한 부분이 있다면 알려주시면 감사하겠습니다.

  ※ 책은 게시글보다 정확한 내용을 담고 있으며 코드, 그림, 예제를 이용하여 개념을 자세히 설명합니다.