[자료구조] 해시테이블(Hash Table)

해시테이블 (Hash Table)이란?

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로, 빠르게 데이터를 검색할 수 있는 자료구조이다.

해시 테이블은 왜 빠를까 ? 🤔

내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문
각각의 key 값에 해시 함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 이용해 값을 저장하거나 검색 → 색인(index)에 해시 값을 사용함으로써 모든 데이터를 살피지 않아도 되기 때문

해시 함수

해시 함수에서 중요한 것은 고유한 인덱스 값이다.

해시 테이블에 사용되는 대표적인 해시 함수

Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산.( 주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다 ex) SHA 알고리즘
Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용
Multiplication Method: 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산. h(k)=(kAmod1) × m
Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법

해시 테이블 특징

기본 연산 : search, insert, delete
데이터 순차 저장 X
key를 통해 value를 얻을 수 있음(이진 탐색 트리, 배열에 비해 속도가 매우 빠름)
데이터를 해시 함수로 축약 가능 → 데이터 비교 효율적
수정 가능 (mutable)

해시 테이블은 key-value가 1:1 매핑되어 있기 때문에 검색, 삽입, 삭제 과정에서 모두 평균적으로 O(1)의 시간복잡도를 갖는다.
공간 복잡도는 O(N)인데 여기서 N은 키의 개수다.

Hash table time complexity in Big O notation
Algorithm	Average	Worst case
space	O(n)	O(n)
search	O(1)	O(n)
insert	O(1)	O(n)
delete	O(1)	O(n)

해시 충돌

그런데 만약, 서로 다른 두 개의 입력 값을 해시 함수에 돌렸을 때 결과가 같은 경우는 어떻게 해야할까 ? (중복된 인덱스 값이 생기는 경우)

다음 그림을 보자.

ARGOS와 MINIBEEF가 같은 해시 값을 가지며 충돌이 발생했다.

해시 충돌을 설명하기 위해서는 적재율(load factor)이라는 개념이 필요하다.
적재율이란 해시 테이블의 크기에 대한 키의 개수의 비율을 뜻한다. 즉 키의 개수를 K, 해시 테이블의 크기를 N이라고 했을 때 적재율은 K/N이다.
만약 충돌이 발생하지 않을 경우 해시 테이블의 탐색, 삽입, 삭제 연산은 모두 O(1)에 실행되지만, 충돌이 발생할 경우에는
탐색과 삭제 연산이 O(K)만큼 걸리게 된다.

이 해시 충돌이 발생하는 근본적인 원인은 비둘기집 원리다. 즉, 해시 함수에 입력하 ㄹ수 있는 데이터의 가짓수는 무한한데, 출력으로 나올 수 있는 해시 값이 유한하기 때문에 발생하는 것이다. 비둘기집 원리 에 의해 해시 충돌이 전혀 1도 없는 해시 함수를 만드는 것은 불가능하다. 따라서 우리는 충돌이 가급적 발생하지 않는 방법에 대해 고민해야한다.

해시 값 충돌 문제 해결 방법 2가지

분리 연결법(Separate Chaining)
개방 주소법(Open Addressing)

분리 연결법(Separate Chaining)

분리 연결법은 한 버킷 당 들어갈 수 있는 엔트리 수에 제한을 두지 않는다. 이때 버킷에는 링크드리스트나 트리를 사용한다.

해시 충돌이 일어나더라도 노드가 연결되어 있기 때문에 index가 변하지 않고 데이터 개수의 제약이 없다는 장점이 있다.

단점 : 메모리 문제 야기 가능, 테이블 부하율에 따라 선형적으로 성능 저하

개방 주소법(Open Addressing)

open addressing은 한 버킷 당 들어갈 수 있는 엔트리는 하나지만, 다른 주소에 데이터를 저장할 수 있도록 허용하는 방법이다.

이 방법은 부하율이 높을수록(테이블에 저장된 데이터의 밀도가 높을수록) 성능이 급격하게 저하된다.

이 방법의 주 목적은 저장할 엔트리를 위한 다음 slot을 찾는 것으로3가지 방법이 있다.

(1) 선형 탐사법

말 그대로 간단하게 선형으로 순차적 검색을 하는 방법이다. 해시 함수로 나온 해시 index에 이미 다른 값이 저장되어 있다면, 해당 해시값에서 고정 폭을 옮겨 다음 해시 값에 해당하는 버킷에 엑세스 하는 벙법이다ㅏ.

단점 : 이 경우는 특정 해시 값의 주변이 모두 채워져 있는 일차 군집화 문제에 취약하다.

(2) 제곱 탐사법 (Quadratic Probing)

선형 탐사법과 동일하지만, 고정폭이 아니라 제곱으로 늘어난다. 이 경우는 데이터의 밀집도가 선형 탐사법보다 낮기 때문에 다른 해시 값까지 영향을 받아 연쇄적으로 충돌이 발생할 가능성이 적다.

단점 : 캐시의 성능이 떨어져서 속도의 문제가 발생한다.

(3) 더블 해싱

이 방법은 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한 번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 연산이 많다.

해시 테이블 시간 복잡도

각각의 Key 값은 해시 함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간 복잡도로 데이터를 조회할 수 있다. 하지만, 데이터의 충돌이 발생한 경우 Chaining에 연결된 리스트까지 검색을 해야하므로 O(N)까지 증가할 수 있다.

충돌을 방지하는 방법들은 클러스터링을 방지하기 위한 방식이지만, 공간을 많이 사용한다는 단점이 있다. 만약, 테이블이 꽉 차있으면 테이블을 확장해주어야하는데, 이는 매우 심각한 성능 저하를 불러온다.

그럼 HashMap이랑 다른 점이 뭐야 ?

Java에서는 Key-Value로 저장하는 익숙한 자료구조인 HashMap이 있다. HashMap과 HashTable의 차이는 동기화 지원 여부에 있다.

코드를 봐보자. 아래 코드는 HashMap의 put이다.

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

다음은 HashTable의 put이다.

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;
}

여기에는 synchronized가 붙어있는 것을 확인할 수 있는데, 이는 병렬 프로그래밍을 할 때 동기화를 지원해준다는 것을 의미한다. 만약, 병렬 처리를 하면서 자원의 동기화를 고려해야 한다면 해시 테이블을, 그렇지 않다면 해시맵을 사용하면 된다.

Reference

저작자표시