Hashing - Chaining, Open Addressing

# 해싱이란?

 대부분의 탐색 방법들은 탐색 키를 저장된 키 값과 반복적으로 비교하면서 탐색을 원하는 항목에 접근한다. 반면 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 이렇게 키 값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(hash table)이라 부르고, 해시 테이블을 이용한 탐색을 해싱(hashing)이라 한다.

 키들의 비교에 의한 탐색 방법은 정렬이 안 되어 있다면 O(n)이고 정렬이 되어 있다면 O(log_2n)이다. 정렬되어 있는 경우의 시간 복잡도가 O(log_2n)인 건 이진 탐색 알고리즘 혹은 이진 탐색 트리의 탐색 알고리즘의 시간복잡도를 생각하면 된다. 잘 모르겠다면 이진 탐색 또는 이진 탐색 트리 알고리즘 게시물을 참고하도록 하자.

 해싱이 나오게 된 배경은 위에서 설명한 시간복잡도 보다 더욱 빠른 탐색을 필요로 할 때다. 해싱은 이론적으로 O(1)의 시간 안에 탐색을 끝마칠 수도 있다. 해싱은 보통 사전(dictionary)과 같은 자료 구조를 구현할 때에 최상의 선택이 된다.


# 충돌(collision)

두 개 이상의 키가 동일한 위치로 해싱되는 경우
즉, 서로 다른 두 키 Key1과 Key2에 대하여 H(Key1) = H(Key2)인 상황
일반적으로 전체 사용가능한 Key에 비하여 실제로 사용하는 Key의 종류는 한정되어 있기 때문에 충돌이 발생할 수 밖에 없다. 하지만 데이터를 저장하기 위해서 배열의 크기를 무한정 키우는 것은 사용되지 않는 영역이 많아지기 때문에 효율적이지 못하다.

충돌이 발생할 경우 대처 방법이 필요하고 대표적으로 chaning과 open addressing이 있다.

 

# Chaining

동일한 장소로 해싱된 모든 키들을 하나의 연결리스트로 저장
최악의 경우는 모든 키가 하나의 슬롯으로 해싱되는 경우이고 전체적인 시간 복잡도는
키들이 얼마나 여러 슬롯에 잘 분배되어 있는지에 따라서 결정된다.

키의 삽입(Insertion)
키를 리스트의 맨 앞에 삽입 O(1)
만약 중복을 허용하지 않는다면 중복 검사를 수행하기 때문에 시간 복잡도는 리스트의 길이에 비례한다.

키의 검색(Search)
리스트에서 순차 검색
시간 복잡도는 리스트의 길이에 비례한다.

키의 삭제(Deletion)
리스트로부터 키를 검색한 뒤 삭제
삭제하는 것에는 O(1)의 시간 + 검색하는 시간이 소요된다.

 

# Open Addressing

모든 키를 해시 테이블에 저장하는 것으로 각 Slot에는 1개의 키만 저장된다.

Linear Probing

해싱한 뒤 해당 슬롯에 이미 데이터가 있는 경우에 다음 슬롯을 확인하는 것으로 가장 빨리 찾은 빈 슬롯에 데이터를 저장하는 방법이다.

Primary cluster는 데이터가 채워져있는 연속된 슬롯을 의미한다. 이러한 cluster는 점점 더 커지는 경향이 생기고
검색하는 시간이 cluster의 크기에 비례하기 때문에 바람직하지 못하다.

Quadratic Probing

충돌이 발생하는 경우 다음 Slot을 1^2 -> 2^2 -> 3^2 등으로 증가하며 찾는 방법이다.

 

Double Hashing

서로 다른 2개의 해시 함수를 사용하여 키를 찾는 방법이다.

Open Addressing 키의 삭제

단순히 키를 삭제하는 경우에는 cluster의 연결성이 깨지기 때문에 문제가 발생한다.
1번 2번 3번이 연결되어 있을 때 2번 데이터가 삭제된다면 1번에서 2번으로 넘어가는 순간 빈 슬롯을 발견해 탐색을 종료하기 때문이다.

적절한 해결책은 삭제될 슬롯에 있는 값과 같은 해시값을 가지는 cluster의 마지막 슬롯의 값을 삭제될 슬롯으로 가져와 연결성을 유지하는 방법이 있다.

 

출처, 참고
https://mattlee.tistory.com/62

<해싱 (Hashing)>: 기본 개념

https://ict-nroo.tistory.com/76

[Algorithm] 6-1. Hashing 개요 - Chaining, Open Addressing, SUHA