해시 테이블(Hash Table)

해시 테이블이란?

• 해시 함수를 사용하여 입력 키 값으로부터 해시 값을 얻어 그것을 인덱스로 사용하여 효율적인 검색 방식을 제공하는 자료구조
  • 원소가 저장될 자리가 원소의 값에 의해 결정됨
  • 매우 빠른 응답을 요하는 경우에 유용하게 사용됨
    • ex) 주민 등록 시스템과 같은 호출 번호 관련 검색

해시 함수

• 해시 함수를 적용하여 입력 키값으로부터 해시 값을 얻었을 때 입력 원소가 해시 테이블에 골고루 저장되어야 한다.
• 계산이 간단해야 하며 대표적으로 나누기 방법과 곱하기 방법이 있다.
  • 나누기 방법(Division Method)
    • h(x) = x mod m
    • m: 해시 테이블 사이즈, 보통 소수로 지정
  • 곱하기 방법(Multiplication Method)
    • h(x) = (xA mod 1) * m
    • A: 0<A<1인 상수
    • m은 굳이 소수일 필요 없음, 보통 2^p(p는 정수)로 지정

예를 들어 해시 함수 h(x) = x mod 13 일 때 크기가 13인 해시 테이블에 5개의 원소가 저장된 상황이다.

입력 : 25, 13, 16, 15, 7

0	13
1
2	15
3	16
4
5
6
7	7
8
9
10
11
12	25

이 때 20이 추가로 입력되면 20 mod 13 = 7 이 되므로 7번 인덱스에 저장돼야 한다. 하지만 이미 7이 있기 때문에 들어갈 수 없는데 이와 같이 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 해시 충돌이라고 한다.

해시 충돌 해결 방법

해시 충돌의 해결 방법은 크게 2가지가 있다.

1. 체이닝(Chaining)
   • 같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트(Linked List)로 관리한다.
   • 추가적인 연결 리스트가 필요하다.

2. 개방주소 방법(Open Addressing)
   • 충돌이 일어나더라도 빈자리가 생길 때까지 해시값을 계속 만들어서 어떻게든 주어진 테이블 공간에서 해결한다.
     • h0(x), h1(x), h2(x), ...
   • 추가적인 공간이 필요하지 않다.

개방주소 방법을 구현하기 위한 3가지 방법

1. 선형 조사
   • hi(x) = (h(x) + i) mod m

예를 들어 해시 함수 h(x) = x mod 13 이고 hi(x) = (h(x) + i) mod 13 일 때 크기가 13인 해시 테이블에 10개의 원소가 저장되는 상황이다.

입력 : 25, 13, 16, 15, 7, 28, 31, 20, 1, 38

2. 이차원 조사
   • hi(x) = (h(x) + ai^2 + bi) mod m
   • a와 b는 상수

예를 들어 해시 함수 h(x) = x mod 13 이고 hi(x) = (h(x) + i^2) mod 13 일 때 크기가 13인 해시 테이블에 6개의 원소가 저장되는 상황이다.

입력 : 15, 18, 43, 37, 45, 30

하지만 이차원 조사는 선형 조사에 비해 더 효율적이라고 말할 수 없다.

그 이유는 hi(x) = (h(x) + ai^2 + bi) mod m에서 ai^2 + bi는 x값이 아닌 i값에 의해 결정되므로 hi(x) = (h(x) + i) mod m와 별반 다르지 않기 때문이다. 이와 같은 문제를 해결하기 위해 사용하는 것이 더블 해싱이다.

3. 더블 해싱
   • hi(x) = (h(x) + if(x)) mod m

예를 들어 해시 함수 h(x) = x mod 13, f(x) = x mod 11 이고 hi(x) = (h(x) + if(x)) mod 13일 때 크기가 13인 해시 테이블에 5개의 원소가 저장되는 상황이다.

입력 : 15, 19, 28, 41, 67

위와 같은 개방주소 방법을 사용하여 해시 테이블을 구성했다면 삭제할 때 주의해야할 점이 있다.

다음과 같이 hi(x) = (h(x) + i) mod 13일 때 크기가 13인 해시 테이블에 10개의 원소가 저장된 상황이라고 하자.

0	13
1	1
2	15
3	16
4	28
5	31
6	38
7	7
8	20
9
10
11
12	25

이 해시 테이블에서 원소 1이 삭제된다.

0	13
1
2	15
3	16
4	28
5	31
6	38
7	7
8	20
9
10
11
12	25

이 상황에서 38을 검색해보면 12번 인덱스부터 1씩 올라오면 1번 인덱스가 비어있기 때문에 38이 존재하지 않는다는 결과를 반환할 것이다. 그림으로 나타내면 다음과 같다.

이 때 다음과 같이 1이 삭제된 상태라는 표시를 해두면 문제가 해결된다.

0	13
1	DELETED
2	15
3	16
4	28
5	31
6	38
7	7
8	20
9
10
11
12	25

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

검색 시간은 적재율 α와 관련이 있다.

적재율은 해시 테이블 전체에서 원소가 얼마나 많이 차 있는지를 나타내는 수치로, 적재율 α는 크기가 m인 해시 테이블에 n개의 원소가 저장되어 있을 때 α = n / m이다.

1. 체이닝에서의 검색 시간
   • 체이닝을 이용하는 해싱에서 적재율이 α일 때, 실패하는 검색에서 조사 횟수의 기대치는 α이다.
   • 체이닝을 이용하는 해싱에서 적재율이 α일 때, 성공하는 검색에서 조사횟수의 기대치는 1 + α/2 + α/2n이다.
     
2. 개방주소 방법에서의 검색 시간
   (조사 순서 h0(x), h1(x), …, hm-1(x)가 0부터 m-1 사이의 수로 이루어진 순열을 이루고, 모든 순열은 같은 확률로 일어난다고 가정한다.)
   
   • 개방주소 방법을 이용하는 해싱에서 적재율이 α일 때, 실패하는 검색에서 조사횟수의 기대치는 최대 1/(1- α )이다.
   • 개방주소 방법을 이용하는 해싱에서 적재율이 α일 때, 성공하는 검색에서 조사횟수의 기대치는 최대 (1/ α) log(1/(1- α))이다.