본문 바로가기
CS/Data Structure

HashTable 특징 및 Hash 인덱스

by ilyadelavie 2023. 4. 9.

그간 자료구조에 대한 제대로 된 이해 없이 겉핥기식 공부했던걸 반성하면서

특히나 해시는 많이 사용되는 기본 자료구조인데 최근 동작 방식에 대해 묻는 질문에 정말 일차원적인 생각밖에 떠오르지 않아서 부끄러운 마음으로 오랜만에 포스트를 올려본다.

 

HashTable

우선 해시는 임의의 크기를 가진 데이터를 고정된 크기의 값으로 매핑하는 함수를 말하고 이렇게 변환된 값을 해시 값(Hash Value)이라고 한다. 해시 테이블은 이러한 해시 함수(Hash Function)를 사용하여 데이터를 저장하고 검색할 수 있는 자료 구조이다.

 

여기서 해시 함수는 예를 들어 5,8,13,21,27 이라는 값들이 있으면 이를 13으로 나눈 나머지 값인 5,8,0,8,1 해시값으로 변환시키는 기능을 하는데 해시 테이블에서는 이런 해시 함수를 이용해서 키 값을 변환한 해시 값을 배열의 인덱스로 사용하고 이를 인덱스에 해당하는 버킷에 담는다.

그런데 아까 변환된 해시값들을 보면 8,21의 해시값이 중복되고 있다. 그럼 데이터를 버킷에 담을 때 두 값은 어떤 기준에 의해 처리될까?

먼저 위와 같은 상황을 해시 충돌(collision)이라고 하는데 충돌을 해결하기 위한 제일 좋은 방법은 애초에 충돌 방지를 위해 해시 함수를 잘 설계하거나 테이블 크기를 적절히 설정하는 것이지만 완전히 해시충돌을 피할 수는 없기 때문에 보통은 두가지 방식을 통해 충돌을 완화한다.

 

1) Hash 충돌 처리 방식

  • Seperate Chaining
  • Open Addressing
    • 선형 탐색(Linear Probing): 다음 해시(+1)나 n개(+n)를 건너뛰어 비어있는 해시에 데이터를 저장
    • 제곱 탐색(Quadratic Probing): 충돌이 일어난 해시의 제곱을 한 해시에 데이터를 저장
    • 이중 해시(Double Hashing): 다른 해시함수를 한 번 더 적용한 해시에 데이터를 저장

먼저 Seperate Chaining는 Linked List를 이용하여 node 추가하여 데이터를 저장하는 방식이며 장점은 미리 저장 공간을 잡아둘 필요가 없어 상대적으로 적은 메모리를 사용한다. 그러나 같은 해시에 자료들이 계속 연결되면 테이블의 부하율에 따라 선형적으로 성능이 저하된다는 단점이 있어 해당 경우에는 Open Addressing 방식이 적합하다.

Open Addressing은 정해진 규칙에 따라 해쉬테이블의 비어있는 버킷을 찾아 데이터를 저장하는데 별도의 저장 공간이 필요로 하지않아 메모리 효율이 높다. 그러나 체이닝 방식과 마찬가치로 탐색 방식에 따라 테이블의 부하율이 높아질수록 비약적으로 성능이 저하된다. (같은 경우 체이닝 방식이 상대적으로 성능 면에서 더 우수함)

 

1-1) 시간복잡도

*a(1개의 해시당 평균 a개의 키가 있다고 가정)

 

Seperate Chaining

  • Insertion
    충돌이 일어났을 때 해당 해시가 가진 LinkedList의 head에 자료를 저장할 경우 O(1)의 시간복잡도를 가진다. 해당 해시를 산출하고 저장하면서 기존 값을 연결하는 행위만 하면 되기 때문이다.
    반면 tail에 자료를 저장할 경우 O(α)의 시간 복잡도를 가진다. 해당 해시를 저장할 때 모든 연결리스트를 지나서 tail에 접근해야 하기 때문이다. 한 개의 해시에 모든 자료가 연결되어 있을 수 있기 때문에 최악의 경우 O(n)의 시간 복잡도를 가진다.
  • Deletion & Search
    삭제와 검색은 둘다 산출된 해시의 연결리스트를 차례로 살펴보아야 하므로 O(α)의 시간 복잡도를 가지고 한 개의 해시에 모든 자료가 연결되어 있을 수 있기 때문에 최악의 경우 O(n)의 시간복잡도를 가진다.

Open Addressing

  • Insertion & Deletion & Search
    삽입,삭제,검색 모두 대상이 되는 해시를 찾아가는 과정에 따라 시간복잡도가 계산이 된다. 해시함수를 통해 얻은 해시가 비어있지 않으면 다음 버킷을 찾아가야 한다. 찾아가는 횟수가 많아지면 많아질 수록 시간복잡도가 증가한다.
    최상의 경우 O(1), 최악의 경우 O(n). 따라서 Open Addressing에서는 비어있는 공간을 확보하는 것(=버킷이 어느 정도 채워졌을 때 버킷의 사이즈를 늘려주는 것)이 필요하다. 최악의 경우 버킷을 모두 살펴보아야 하는 경우가 생길 수 있다.

 

2) Hash 자료 구조의 한계

해시 테이블은 키를 가지고 빠르게 value에 접근하고 조작할 수 있는 장점이 있어서 많이 사용되지만 아래 단점을 유의해야 한다.

  1. 순서가 있는 배열에는 적합하지 않다. 순서와 상관없이 key만을 가지고 hash를 찾아 저장하기 때문에 상하관계가 있거나 순서가 중요한 데이터의 경우 해시테이블은 적합하지 않다.
  2. 공간 효율성이 떨어진다. 데이터가 저장되기 전에 미리 저장공간을 확보해 놓아야 한다. 공간이 부족하거나 아예 채워지지 않은 경우가 생길 가능성이 있다.
  3. 해시 함수의 의존도가 높다. 평균 데이터 처리의 시간복잡도는 O(1)이지만, 이는 해시 함수의 연산을 고려하지 않는 결과이다. 해시 함수의 결과 값의 범위가 넓으면 그만큼 버켓이 많이 필요해져서 공간의 낭비가 커지고, 값의 범위가 너무 작으면 충돌되는 경우가 너무 많이 발생한다.

 

Hash 인덱스

해시테이블 구조에 대해 간단히 알아봤으니 인덱스 알고리즘으로 사용될 때의 해시테이블 특징에 대해서도 알아보자.

위에 언급했던 대로 데이터의 key를 알고 있으면 데이터에 O(1)의 시간 복잡도로 접근할 수 있다. 언뜻 보면 데이터베이스에 적합한 자료구조인 것 같은데 실제로 많은 DBMS들은 해시 테이블을 사용하지 않는다. 왜 그럴까?

왜냐하면 해시 테이블은 동등 비교 검색(equal 연산)에는 최적화 돼있지만 범위를 검색한다거나 정렬된 결과를 가져오는 목적으로는 사용할 수 없어서 부등호 연산에 부적합하기 때문이다.

해시 테이블 동작을 다시 떠올려보면 해시 함수를 이용하여 키 값을 해시 값으로 변환하여 저장하는 구조를 가지기 때문에 이를 기준으로 범위를 검색하거나 원본값을 기준으로 정렬하기 위해서는 해당 범위 내에 존재하는 모든 해시 값에 대해 버킷을 탐색해야하기 때문에 부등호 연산이 어렵거나 불가능한 것이다.

 

쿼리문으로 예시를 들어 자세히 확인해보쟈

 

해시 인덱스를 사용할 수 있는 쿼리

다음 패턴의 쿼리는 동등 비교 조건으로 값을 검색하고 있으므로 해시 인덱스의 빠른 장점을 그대로 이용할 수 있다.

SELECT .. FROM dodan WHERE column = '검색어';
SELECT .. FROM dodan WHERE column <=> '검색어';
SELECT .. FROM dodan WHERE column IN ('검색어', '검색어');
SELECT .. FROM dodan WHERE column IS NULL;
SELECT .. FROM dodan WHERE column IS NOT NULL;

 

해시 인덱스를 전혀 사용하지 못하는 쿼리 

대체로 범위 비교나 부정형 비교는 해시 인덱스를 사용할 수 없다.

SELECT .. FROM dodan WHERE column >= '검색어';
SELECT .. FROM dodan WHERE column BETWEEN 100 AND 120;
SELECT .. FROM dodan WHERE column LIKE '검색어%'
SELECT .. FROM dodan WHERE column <> '검색어';

 

그렇다고 해서 DBMS에서 해시 인덱스를 전혀 사용하지 않는 것은 아니다. (B-Tree만큼 범용적이지는 않지만)

해시 인덱스 알고리즘은 테이블의 인덱스뿐 아니라 InnoDB의 버퍼 풀에서 빠른 레코드 검색을 위한 Adpative Hash Index로 사용되기도 하고, 오라클과 같은 DBMS에서는 조인에 사용되기도 한다. 

 

 

 

자바에서 사용되는 해시에 대해서는 다음 편에~

https://ilyadelavie.tistory.com/126

 

자바에서의 Hash

 

ilyadelavie.tistory.com

 

참고

저작자표시 비영리 변경금지 (새창열림)

'CS > Data Structure' 카테고리의 다른 글

Dequeue(Double-ended Queue)  (0) 2022.09.11
Tree(트리)  (0) 2022.06.15
Graph(그래프)  (0) 2022.06.14

관련글

티스토리툴바