Hash Table

해시함수(hash function)

데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이 때 매핑 전 원래 데이터 값을 key, 매핑 이후 데이터의 값을 hash value , 매핑하는 과정을 hashing 이라고 합니다.

 

해시충돌(hash collision)

해시함수는 보통 키값의 개수보다 적은 해쉬값을 관리하므로 서로 다른 두 개 이상의 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생하게 됩니다. 현재까지 알려진 거의 모든 해시함수는 해시충돌을 일으킨다고 합니다. 이때문에 해시 충돌 자체를 줄이거나, 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하게끔 해야 합니다.

 

해시테이블의 장점

해시테이블은 매우 효율적인 데이터 관리 도구입니다. 주요 장점 중 하나는 대량의 데이터를 적은 리소스로 처리할 수 있다는 것입니다. 해시함수를 사용하여 무한에 가까운 데이터를 유한한 해시값으로 매핑함으로써, 캐쉬 메모리와 같은 제한된 저장 공간에서도 데이터를 효과적으로 관리할 수 있습니다.

또한, 해시테이블은 데이터 검색, 삽입, 삭제 등의 연산에서 빠른 성능을 보입니다. 해시함수를 통해 생성된 색인을 사용하면 데이터 집합 전체를 검토할 필요 없이 원하는 데이터에 빠르게 접근할 수 있습니다. 이는 특히 큰 데이터셋에서 매우 유용하다. 이러한 빠른 연산은 해시가 데이터 액세스 시 계산복잡성을 O(1)에 근접하게 만듭니다.

해시테이블과 다른 자료구조를 비교해보면, 이진탐색트리는 메모리 사용이 효율적이지만 데이터 탐색에는 O(\log N) 의 계산복잡성이 발생합니다. 반면, 배열은 데이터 액세스에 O(1)의 계산복잡성을 보이지만, 메모리를 미리 할당해야하는 단점이 있습니다.

해시테이블은 보안 분야에서도 중요한 역할을 합니다. 해시값과 원본 키 사이에는 직접적인 관계가 없어, 해시값만으로 원본 데이터를 복원하는 것이 어렵습니다. 그러나 해시충돌의 가능성이 항상 존재하므로, 충돌을 최소화하거나 충돌이 발생할 경우 적절히 처리하는 방안이 필요합니다.

 

해시테이블

해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조를 해시테이블(hash table)이라고 합니다. 이 때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot)이라고 합니다.

해시값을 사용하여 데이터의 값을 저장할 때, 해시충돌이 발생하는 경우를 고려해 아래와 같은 방법으로 이를 해결할 수 있습니다.

• Chaining
• Open Addressing
  • Linear Probing
  • Quadratic Probing
  • Double Hashing

 

Chaining

해시충돌의 간단한 해결책 중 하나입니다. 해시값에 대응하는 한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써 모든 자료를 해시테이블에 담는 것입니다. 해당 버킷에 데이터가 이미 있다면 체인처럼 노드를 추가하여 다음 노드를 가리키는 방식으로 구현합니다. 유연하다는 장점을 가지나 메모리 문제를 야기할 수 있습니다.

아래 그림에서 김길동 과 홍길동 의 해시키가 같은 값으로 변환 되어 해시 충돌이 일어났지만 Bucket을 연결리스트로 저장해 두어 여러 값을 저장할 수 있습니다.

아래 결과물 처럼 동일한 hashKey 값이 나오더라도 LinkedList 를 통해 여러개의 value 가 들어가 있는 것을 확인할 수 있습니다.

public static void chainingTable() {
    HashTable<String, String> chainingHashTable = new ChainingHashTable<>(10);
    chainingHashTable.put("1", "010-1111-1111");
    chainingHashTable.put("2", "010-2222-2222");
    chainingHashTable.put("3", "010-3333-3333");
    chainingHashTable.put("4", "010-4444-4444");
    chainingHashTable.put("5", "010-5555-5555");
    chainingHashTable.put("6", "010-6666-6666");
    chainingHashTable.put("7", "010-7777-7777");
    chainingHashTable.put("8", "010-8888-8888");
    chainingHashTable.put("9", "010-9999-9999");
    chainingHashTable.put("10", "010-0000-0000");
    chainingHashTable.put("11", "011-1111-1111");

    System.out.println(chainingHashTable);
}

/*
i: 0, values: [{key=10, value=010-0000-0000}, {key=5, value=010-5555-5555}, {key=4, value=010-4444-4444}, {key=1, value=010-1111-1111}]
i: 1, values: []
i: 2, values: [{key=11, value=011-1111-1111}, {key=7, value=010-7777-7777}, {key=6, value=010-6666-6666}, {key=3, value=010-3333-3333}, {key=2, value=010-2222-2222}]
i: 3, values: []
i: 4, values: []
i: 5, values: []
i: 6, values: []
i: 7, values: []
i: 8, values: [{key=9, value=010-9999-9999}, {key=8, value=010-8888-8888}]
i: 9, values: []
*/

ChainingHashTable:

import java.util.LinkedList;

public class ChainingHashTable<K, V> implements HashTable<K, V> {

    private LinkedList<Entry<K, V>>[] table;
    private int numberOfItems;
    private int capacity;


    public ChainingHashTable(int capacity) {
        this.capacity = capacity;
        table = new LinkedList[this.capacity];
        numberOfItems = 0;
        for (int i = 0; i < capacity; i++) {
            table[i] = new LinkedList<>();
        }
    }

    @Override
    public int hash(Object key) {
        int hashcode = 0;
        for (char c : key.toString().toCharArray()) {
            hashcode += c;
        }

        return hashcode & capacity;
    }

    @Override
    public void put(K key, V value) {
        int indexOfBucket = this.hash(key);
        LinkedList<Entry<K, V>> bucket = table[indexOfBucket];

        bucket.add(0, new Entry<>(key, value));
        numberOfItems++;
    }


    @Override
    public void remove(K key) {
        if (isEmpty()) {
            throw new RuntimeException("Hash Table is Empty");
        }

        int indexOfBucket = this.hash(key);
        LinkedList<Entry<K, V>> bucket = table[indexOfBucket];

        for (Entry<K, V> entry : bucket) {
            if (entry.getKey().equals(key)) {
                bucket.remove(entry);
                numberOfItems--;
            }
        }
    }

    @Override
    public V get(K key) {
        int indexOfBucket = this.hash(key);
        LinkedList<Entry<K, V>> bucket = table[indexOfBucket];

        for (Entry<K, V> entry : bucket) {
            if (entry.getKey().equals(key)) {
                return entry.getValue();
            }
        }

        return null;

    }

    @Override
    public boolean isEmpty() {
        return numberOfItems == 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < table.length; i++) {
            sb.append("i: ")
                .append(i)
                .append(", values: ")
                .append(table[i]).append("\n");
        }
        return sb.toString();
    }
}

 

Open Address

Open Addressing은 Chaining과 달리 한 버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시테이블 입니다. 하지만 해시함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있습니다. 메모리 문제가 발생하지 않으나 해시충돌은 발생합니다.

아래 그림에서 김길동과 홍길동의 해시키가 같은 값으로 변환 되어 해시 충돌이 일어났지만 2번 index는 비어있으므로 홍길동의 값을 2번 index에 삽입합니다.

 

Probing

Open Addressing의 해시충돌은 탐사(probing) 방식으로 해결할 수 있습니다. 여기서 탐사란, 해시충돌이 발생한 경우 해시테이블 내 새로운 주소를 찾는 과정입니다.

탐사 방식에는 아래와 같은 방법이 있습니다.

• 선형 탐사(Linear Probing)
  • 가장 간단한 방식
  • 최초 해시값에 해당하는 버킷에 다른 데이터가 있다면 고정 폭(예시에선 1칸)만큼 옮겨가며 비어있는 버킷을 찾는다.
• 제곱 탐사(Quadratic Probing)
  • 탐사하는 폭을 제곱수로 늘립니다. (1^2, 2^2, 3^2 ...)
  • 동일한 초기 해시값을 갖을 때 취약합니다.
    (초기 해시값이 7인 데이터들은 제곱 수의 폭만큼 넓게 움직이긴하지만 모두 같은 값으로 늘어남)
• 이중해싱(Double Hashing)
  
  • 2개의 해시함수를 사용합니다.
    최초의 해시값을 얻을 때, 해시충돌이 일어났을 때 탐사 폭을 얻을 때.

여기서는 Linear Probing만 구현하였습니다.

 

Linear Probing

아래 결과물 처럼 동일한 hashKey 값이 나오더라도 비어있는 다른 index를 찾게 됩니다. 

• key 값이 10 인 데이터를 넣었을 때, index 7을 할당 받습니다.
• index 7에는 key 값이 9 인 데이터가 이미 존재합니다.
• index 7의 다음값인 index 8이 비어있기 때문에 key 값이 10 인데이터는 index 8에 삽입됩니다.

public static void linearProbingTable() {
    HashTable<String, String> linearProbingHashTable = new LinearProbingHashTable<>(10);
    linearProbingHashTable.put("1", "010-1111-1111");
    linearProbingHashTable.put("2", "010-2222-2222");
    linearProbingHashTable.put("3", "010-3333-3333");
    linearProbingHashTable.put("4", "010-4444-4444");
    linearProbingHashTable.put("5", "010-5555-5555");
    linearProbingHashTable.put("6", "010-6666-6666");
    linearProbingHashTable.put("7", "010-7777-7777");
    linearProbingHashTable.put("8", "010-8888-8888");
    linearProbingHashTable.put("9", "010-9999-9999");
    linearProbingHashTable.put("10", "010-0000-0000");

    System.out.println(linearProbingHashTable);
}

 

/*
hash collision. key: 10, index: 7
i: 0, key: 2, value: 010-2222-2222
i: 1, key: 3, value: 010-3333-3333
i: 2, key: 4, value: 010-4444-4444
i: 3, key: 5, value: 010-5555-5555
i: 4, key: 6, value: 010-6666-6666
i: 5, key: 7, value: 010-7777-7777
i: 6, key: 8, value: 010-8888-8888
i: 7, key: 9, value: 010-9999-9999
i: 8, key: 10, value: 010-0000-0000
i: 9, key: 1, value: 010-1111-1111
*/

LinearProbingHashTable:

public class LinearProbingHashTable<K, V> implements HashTable<K, V> {

    private int maxSize, currentSize;
    private K[] keys;
    private V[] values;
    private final double DEFAULT_LOAD_FACTOR = 0.75;

    public LinearProbingHashTable(int capacity) {
        this.maxSize = capacity;
        this.currentSize = 0;
        //noinspection unchecked
        this.keys = (K[]) new Object[maxSize];
        //noinspection unchecked
        this.values = (V[]) new Object[maxSize];
    }

    @Override
    public int hash(Object key) {
        int hashcode = 0;
        for (char c : key.toString().toCharArray()) {
            hashcode += c;
        }

        return hashcode % maxSize;
    }

    @Override
    public void put(K key, V value) {
        int hashKey = hash(key);
        int i = hashKey;

        do {
            if (keys[i] == null) {
                keys[i] = key;
                values[i] = value;
                currentSize++;
                return;
            }

            if (keys[i].equals(key)) {
                values[i] = value;
                return;
            }
            System.out.println("hash collision. key: " + key + ", index: " + i);
            i = (i + 1) % maxSize;
        }

        while (i != hashKey);
    }

    @Override
    public void remove(K key) {
        if (isEmpty()) {
            throw new RuntimeException("Hash Table is Empty");
        }

        int i = hash(key);
        while (!key.equals(keys[i])) {
            i = (i + 1) % maxSize;
        }
        keys[i] = null;
        values[i] = null;
        currentSize--;

        for (i = (i + 1) % maxSize; keys[i] != null; i = (i + 1) % maxSize) {
            K tmpKey = keys[i];
            V tmpValue = values[i];

            keys[i] = null;
            values[i] = null;
            currentSize--;

            put(tmpKey, tmpValue);
        }
    }

    @Override
    public V get(Object key) {
        int i = hash(key);
        while (keys[i] != null) {
            if (keys[i].equals(key)) {
                return values[i];
            }
            i = (i + 1) % maxSize;
        }
        return null;
    }

    @Override
    public boolean isEmpty() {
        return currentSize == 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < maxSize; i++) {
            sb.append("i: ")
                .append(i)
                .append(", key: ")
                .append(keys[i])
                .append(", value: ")
                .append(values[i])
                .append("\n");
        }

        return sb.toString();
    }
}

 

참조:

https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/