[알고리즘] 해시 테이블(Hash Table)

안녕하세요, 츄르 사려고 코딩하는 집사! 코집사입니다.

1. 저장/검색의 복잡도

    - 배열 -> O(n)

    - 이진검색트리 -> 최악의 경우 세타(n), 평균 세타(log n)

    - 균형잡힌 이진검색트리(레드블랙트리 등) -> 최악의 경우 세타(log n)

    - B-트리 -> 최악의 경우 세타(log n), Balanced binary search tree보다 상수 인자가 작다

    - 해시 테이블 -> 평균 세타(1)

2. 해시 테이블

    - 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조

    - 평균 상수 시간에 삽입, 삭제, 검색

    - 매우 빠른 응답을 요구하는 응용에 유용

    - 예 : 119 긴급구조 호출과 호출번호 관련 정보 검색

    - 예 : 주민등록 시스템

    - 해시 테이블은 최소 원소를 찾는 것과 같은 작업은 지원하지 않음

    - 입력 원소가 해시 테이블에 고루 저장되어야 함

    - 계산이 간단해야 함

    - 여러 가지 방법이 있으나 가장 대표적인 방법은 나누기 방법과 곱셈 방법

3. 해시 테이블의 주소 계산

4. 해시 테이블의 저장 예시

5. 해시 함수의 방법

   1) 나누기 방법

       - h(x) = x mod m

       - m : 해시 테이블 사이즈. 대개 소수임.

   2) 곱하기 방법

       - h(x) = (xA mod 1) * m

       - A: 0<A<1 인 상수

       - m은 굳이 소수일 필요 없음. 따라서 보통 2^p으로 잡는다.(p는 정수)

6. 해시 테이블의 충돌(Collision)

    - 해시 테이블의 한 주소를 놓고 두 개 이상의 원소가 자리를 다투는 것

    - 충돌 해결 방법은 크게 2가지 존재

    - 체이닝(Chaining), 개방주소 방법(Open Addressing)

7. 체이닝(Chaining)

    - 같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트(linked list)로 관리

    - 추가적인 연결 리스트 필요

8. 개방주소 방법(Open Addressing)

    - 충돌이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결

    - 추가적인 공간이 필요하지 않음

    - 빈자리가 생길 때까지 해시값을 계속 만들어냄

    - 선형 조사, 이차원 조사, 더블 해싱 방법 사용

8-1. 선형 조사(linear Probing)

       - 선형 조사는 1차군집에 취약

       - 1차군집 : 특정 영역에 원소가 몰리는 현상

8-2. 이차원 조사(Quadratic Probing)

      - 이차원 조사는 2차군집에 취약

      - 2차군집 : 여러 개의 원소가 동일한 초기 해시 함수값을 갖는 현상

8-3. 더블 해싱(Double Hashing)

      - 더블 해싱에서 삭제할 시 그 해싱 주소에 표식을 해두어 에러 발생하지 않게 처리

9. 해시 테이블에서의 검색 시간

    - 적재율 a : 해시 테이블 전체에서 얼마나 원소가 차 있는지를 나타내는 수치

    - 해시 테이블에 n개의 원소가 저장되어 있다면 a=n/m이다.

    - 해시 테이블에서의 검색 효율은 적재율과 밀접한 관련이 있음