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

[자료구조] 해시테이블 (hashtable)CS/자료구조2023. 5. 29. 06:29@mag1c

Table of Contents

728x90

해시테이블 (hashtable)

출처 : https://beccacatcheserrors.tistory.com/37

Key, Value 로 데이터를 저장하는 자료구조 중 하나이며 데이터를 빠르게 검색할 수 있는 자료구조이다.

빠른 검색을 할 수 있는 이유는 내부적으로 버킷(배열)을 사용하여 데이터를 저장하기 때문이다.

해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

(Key, Value)가 ("Becca", "+1 424 999 0000")인 데이터를 해시 테이블에 저장한다고 할 때,

index = hash_function("Becca") % Index을 통해 Index값을 계산한 뒤, array[Index] = "+1 424 999 0000"으로 전화번호를 저장하게 된다.

해싱 구조로 데이터를 저장하는 해시테이블은, Key 값으로 데이터를 찾는데, 해당 Key값을 통해 Value를 찾는 해시 함수를 한 번만 수행하면 되므로 매우 빠르게 데이터를 저장하거나 삭제, 조회할 수 있다.(O(1)의 시간 복잡도를 가진다.)

해시 함수

해시 함수의 간단한 예시로 나눗셈을 들 수 있다. 어떠한 정수를 x로 나눈 나머지를 return하는 함수가 있다고 한다면, 이 함수는 해시함수이다. 무조건 0~x-1의 값이 리턴되기 때문이다.

해시 테이블에서 사용되는 대표적인 해시 함수는 아래의 세 가지가 있다.

1. 나눗셈법(Division Method)

>위의 예시처럼 나눗셈을 이용하는 방법

해당 주소값은 입력값 % 테이블의 크기이며테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 한다.)

2. 자리수 접기(Digit Folding)

각 Key의 문자열을 ASCII 코드로 바꾸어 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법

3. 곱셈법(Multiplication Method)

숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m를 사용하여 계산

h(k) = (kAmod1) x m

4. 유니버셜 해싱 (Univeral Hashing)

다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법.

해시 함수는 x의 길이를 갖는 메세지를 입력받아 고정된 길이의 해시값을 출력하는 함수이다. 어떤 입력값에도 그 입력값에 따른 고정된 길이의 해시값을 출력한다.

해시 함수를 통해 입력값은 완전히 새로운 모습의 데이터로 만들어지며 이를 눈사태 효과라고 한다. 눈사태 효과로 인해 결과값 만으로는 입력값을 유추할 수 가 없다. 이러한 특성 덕분에 암호화 영역에서 주요하게 사용되고 있으며, SHA 알고리즘이 대표적인 예시이다.

하지만 해시함수는 입력값의 길이가 어떻든 고정된 길이의 값을 출력하기 때문에, 종종 같은 결과값이 나오는 경우가 있으며, 이를 해시 충돌(hash collision)이라고 한다.

해시 충돌(hash collision)

출처 : https://medium.com/shell-tharsis/hash-collision-5891d7dde54f

키의 개수를 K, 해시 테이블의 크기를 N이라고 했을 때, 해당 해시 테이블의 적재율은 K/N이다.

충돌이 발생하지 않을 경우 해시 테이블의 탐색, 삽입, 삭제연산은 모두 O(1)에 실행되지만, 충돌이 발생할 경우에는 탐색과 삭제 연산이 O(K)만큼 걸리게 된다.

(데이터의 충돌이 발생한 경우 Chaining에 연결된 리스트들까지 검색을 해야 하므로

O(N)까지 시간복잡도가 증가한다.)

적재율

해시 테이블의 크기에 대한 키의 개수의 비율

해시 충돌이 발생하는 근본적인 원인은 비둘기집 원리이다.

해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재한다.

비둘기집 원리

n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이며, '서랍과 양말'로 비유하여 서랍 원칙 또는 디리클레의 방 나누기 원칙이라고 부르기도 하며 구두 상자의 원리라고도 한다.

해시 충돌이 1도 없는 해시 함수를 만드는 것은 불가능하기 때문에 해시 충돌에 대해 안전하다는 해시 함수는 충돌을 찾는게 거의 희박하다. 라고 해석할 수 있다. 또한 해시 테이블의 충돌을 완화하는 방향으로 문제를 보완해야 한다.

해시 충돌 완화

해시 충돌을 완화하는 방법으로는 크게 개방 주소법(open addressing)과 분리 연결법(seperate chaining)이 있다.

출처 : https://st-lab.tistory.com/240?category=856997

1. 개방 주소법(open addressing)

Open Addressing은 해시 테이블 크기는 고정하면서 저장할 위치를 찾는 방법으로 비어있는 테이블의 공간을 활용한다. 또한 데이터를 삭제하면 삭제된 공간은 더미 공간으로 활용되어, 해시테이블을 재정리 해주는 작업이 필요하다. 또한 테이블의 데이터 밀도가 높을수록(빈 공간이 적음 : 부하율) 성능이 급격히 저하된다.

아래의 세 가지 방식이 존재한다.

ⓐ 선형 조사(Linear Probing)

현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어있는 버킷에 데이터를 저장

ⓑ 제곱 탐사(이차 조사 : Quadratic Probing)

해시의 저장 순서폭을 제곱으로 저장하는 방식

처음 충돌이 발생한 경우에는 1만큼 이동하고, 그 다음 부터는 2^2, 3^2칸 씩 옮기는 방식

ⓒ 이중 해싱 탐사(Double Hashing Probing)

해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식

해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 연산을 많이 수행함

2. 분리 연결법 (seperate chaining)

분리 연결법은 개방 주소법과는 달리 한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않는다. 이 때 버킷에는 링크드리스트나 트리를 사용한다. 동일한 버킷으로 접근을 한다면 데이터들을 연결을 해서 관리해주고 있다. 일례로 Java8의 HashTable은 Self-Balancing Binary Search Tree 자료구조를 사용해 Chaining 방식을 구현하였다.

해시 충돌이 일어나더라도 linked list로 노드가 연결되기 때문에 index가 변하지 않고 데이터 개수의 제약이 없다는 장점이 있다.
하지만 메모리 문제를 야기할 수 있으며, 테이블의 부하율에 따라 선형적으로 성능이 저하된다. 따라서 부하율이 작을 경우에는 open addressing 방식이 빠르다.

출처 : https://velog.io/@edie_ko/hashtable-with-js

위의 2가지 방법 이외에도 해시 테이블의 적재율이 높아진 경우에는 크기가 더 큰 새로운 테이블을 만들어서 기존 데이터를 옮겨서 사용하는 방법이 있다. 혹은 분리 연결법을 사용했을 경우엔 재해싱을 통해서 너무 길어진 리스트의 길이를 나누어서 다시 저장할 수도 있다.

HashTable vs HashMap

synchronized 키워드를 주목하면 될 듯 하다.

병렬 처리 및 자원의 동기화 여부를 파악하여 상황에 맞게 알맞은 자료구조를 사용하면 될 것이다.

https://mag1c.tistory.com/367

//HashTable
public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }
    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    addEntry(hash, key, value, index);
    return null;
}

//HashMap
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

참조

https://mangkyu.tistory.com/102

https://velog.io/@edie_ko/hashtable-with-js

https://beccacatcheserrors.tistory.com/37

https://code-lab1.tistory.com/14

https://k39335.tistory.com/18

https://bcho.tistory.com/1072

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

https://medium.com/shell-tharsis/hash-collision-5891d7dde54f

https://medium.com/@matthewharrilal/open-addressing-resolving-collisions-one-day-at-a-time-49415ca73f71

https://st-lab.tistory.com/240?category=856997