[CS] Hash Table (해시 테이블)

Geunhyung Pyun·2024년 2월 20일

CS Hash Table 자료구조 해시테이블

CS가 엄청 약하다는 것을 다시 한 번 느껴본다. 너무 코테에만 집중했다.
일단 자료구조 중 하나인 해시 테이블을 정리해보자.

해시 테이블

개요

(key, value)로 이루어진 자료구조
키를 사용하여서 그 키에 해당하는 값을 찾기 위해 필요한 빠른 속도로 키를 검색할 수 있는 자료 구조

내부

버킷이라는 것을 사용하여 데이터를 저장하고 이를 이용하기에 검색속도가 빠르다.
- key 값에 해시함수를 적용하여 배열의 고유한 index를 생성
- 해당 index를 활용하여 값을 저장. 검색에 이용
- 실제 값이 저장되는 장소를 버킷이라 함.

시간 복잡도 및 성능

언제나 동일한 해시값을 리턴하고 해당 인덱스만 알면 크기에 상관없이 데이터에 접근할 수 있다. 인덱스는 상수시간으로 작동하기에 O(1)을 지향한다.
그러나 후술할 해시값의 충돌로 인해 최악의 경우 O(N)까지 시간 복잡도가 증가한다.
사용률이 70~80% 가 되더라도 충돌이 빈번하게 일어날 정도로 공간을 많이 사용하는데 충돌을 방지하는 방법들을 적용을 하면 공간을 더 사용하는 단점이 있다. 그렇기에 설계할 때 확장을 안 하게끔 해야한다.

해시값의 충돌

대부분 해시 테이블 설계에서는 불완전한 해시 함수(hash function)을 채용하고 있어 둘 이상의 키에 대한 동일한 인덱스를 생성할 수 있게 된다.

이에 따라 Chaning에 연결된 리스트들까지 검색해야 하므로 데이터 크기인 O(N)까지 시간복잡도가 증가한다.

이렇게 중복되는 인덱스를 해결하기 위해 2가지 방법이 있다.

분리 연결법 (Separate Chaining)
- 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장한다.
- 쉽게 얘기하면 동일한 버킷으로 접근하는 데이터들을 연결해서 관리
- 해시 테이블의 확장이 필요없다는 장점을 가지고 있으며 구현 및 삭제가 손쉽다.
- 다만 데이터 수가 많아질 수록 chaning 되는 데이터들이 많아질 수 있기에 캐시의 효율성이 감소한다.
개방 주소법 (Open Addressing)
- 비어있는 해시 테이블의 공간을 활용하는 방법
- 모든 데이터를 테이블에 저장하는 방식
- 데이터를 직접 모두 읽기에 포인터를 쓸 일이 없어 포인터로 인한 오버헤드를 방지할 있고 구현이 용이함.
  - Linear Probing(선형 탐사)
    - 현재의 버킷 index로부터 고정폭만큼 이동하여 차례대로 검색하여 비어 있는 버킷에 데이터를 저장하는 방식.
    - 버킷이 많아질수록 탐색 시간이 많이 소요된다.
  - Quadratic Probing(제곱 탐사)
    - 해시의 저장순서 폭을 제곱으로 저장하는 방식
    - 처음 시작 해시값이 같을 경우 모두 동일한 값을 가지게 되어 충돌이 반복적으로 일어나는 secondary clustering 이 일어남.
  - Double Hashing Probing(이중 해시)
    - 해시된 값을 한 번 더 해싱하여 규칙성을 없애버리는 방식.
    - 충돌을 모두 완화할 수 있다.