[알고리즘 5강] 해싱

1. 개념

삽입, 삭제, 탐색 연산이 지원되는 동적 자료구조

• 일반적인 배열 개념을 일반화 시킨 것
• 레코드.key -> 매핑 함수 -> 테이블의 인덱스(주소)
• 최악 $O(n)$, 평균 $O(1)$

직접 주소 테이블 ( direct addressing table)

키 값 자체를 해시 테이블의 인덱스로 사용

• $key -> T[key]$
  • key
    • $U = \{0, 1, ... m-1\}$
  • 테이블의 key
    • $T = \{0, 1, ... m-1\}$
• 키와 테이블의 키의 집합의 개수가 동일
• 키의 범위가 크지 않은 경우에만 가능
  
• 출처 : https://hyuuny.tistory.com/146

탐색

• return $T[key]$

삽입

• $T[key] = x$

삭제

• $T[key] = null$

-> $O(1)$

해싱이란?

키 값을 기반으로 데이터 저장위치를 직접 계산

• 상수 시간의 데이터 삽입/삭제/탐색 가능
  
• 출처 : https://hyuuny.tistory.com/146

Collision ( 충돌 )

• hash function $h(i)$ 값이 (테이블에 저장될 인덱스가) 겹치는 경우

---

2. 해시 함수

키 값을 해시 테이블 인덱스로 변환하는 함수

바람직한 해시 함수

• 계산이 용이해야함
• 각 키를 m개의 위치에 균등하게 사상시킬 수 있어야함

키의 범위

• 보통 $U = \{1, 2, 3, 4, ....\}$와 같은 자연수의 집합으로 간주

가) 나눗셈법

$h(k) = k\quad mod\quad m$

• 해시 테이블의 크기 m, 키 k
  • k를 m으로 나눈 나머지

m의 선택에 주의 필요 (성능과 직결)

• 2의 멱수와 상당한 차이가 있는 소수(prime number)로 선택
  • $m=2^r$인 경우, $h(k)$는 k의 하위 r비트의 값으로 구성

d진법의 키인 경우, $m=d^r\pm a$(r과 a는 작은 수)의 약수가 되지 않도록 구성

• $m=d-1$, k는 p개의 문자 -> 같은 문자열의 모든 순열
  • (ABC, ACB, BAC)는 같은 해시값을 가짐

나) 곱셈법

$h(k) = \lfloor m\{{h*\theta}\}\rfloor$

• $\{x\} = x - \lfloor x \rfloor$
  • x의 소수부
• 즉, h와 세타를 곱한 값의 소수부를 m과 곱연산 후 정수 부분만 추출

• $\theta$를 무리수라고 했을 때, 충분히 큰 n에 대해서
  $\{\theta\}, \{2\theta\},....,\{n\theta\}$는 $(0, 1]$에서 균등 분포
  • $\theta$를 황금율의 역수로 취하면 특히나 균등분포
    • $\theta = \phi^{-1} = \frac{\sqrt{5} - 1}{2} = 0.6186339.....$

장점

• m의 선택이 결과에 영향을 주지 않음
  • $m=2^p$ 가능

다) 유니버셜 해싱

해시 테이블을 새로 만들 때마다 해시 함수의 큰 집합으로부터
임의의 해시 함수를 선택하여 해싱하는 방법

• 해시 함수마다 좋지 않은 성능을 보이는 입력 데이터의 패턴이 존재한다

• 동적 데이터 집합의 경우 집합의 원소를 미리 알 수 없기 때문에
  적절한 해시 함수를 미리 만들 수 가 없다.

정의

H를 키의 전체 집합 $U$ 에서
$\{0, 1, ..., m-1\}$로의 해시 함수의 집합이라 하면,
서로 다른 $x,y\in U$에 대하여 다음을 만족하는 H를 유니버셜 해시라고 한다.

• $\frac{\vert \{h\in H : h(x) = h(y)\} \vert}{\vert H \vert} \leq \frac{1}{m}$

  • 상이한 두 키에 대하여 충돌을 일으키는 해시 함수의 개수가
    전체 해시 함수의 1/m개 이하

  • 유니버셜한 H에서 임의로 선택된 해시 함수는
    상이한 키에 대하여 충돌을 일으킬 확률이 1/m 이하

정리

$\vert U \vert = M$은 소수이고 $U=\{0, 1, ..., m-1\}$이라 했을 때,
임의의 두 수 $i\in \{1, 2,..., M-1\}$ $j\in \{0, 1, ... M-1\}$에 대하여
$h_{ij}= ((xi + j)\quad mod\quad M)\quad mod\quad m$이라 하면
$H = \{h_{ij}:1 \leq i < M\quad 이고\quad 0 \leq j < M\}$
는 유니버셜 함수 집합이다.

---

3. 충돌 해결 방법

용어 정리

충돌

키 $x \neq y$에 대하여 $f(x) = f(y)$

해시 테이블의 부하율

$\alpha=\frac{n}{m}$

• 해시 테이블이 얼마나 꽉 찼는지
  • 크기가 m인 T에 n개의 레코드가 저장된 경우

탐사 (probe)

해시 테이블의 키들을 조사하는 것

해결방안 1. 연쇄법 ( chaining )

충돌되는 모든 레코드들을 연결 리스트 형태로 저장

• $T[i]$ : 해시값 i의 연결 리스트 헤드 포인터

예시

• 키 : $\{3, 20, 9, 13, 26, 5\}$
• m : $7$ -> 테이블의 크기
• h(k) : $k\quad mod\quad 7$
  
• 출처: https://jsonsang2.tistory.com/14

장단점

• 장점 : 구현 용이, 레코드 추가/삭제 용이
• 단점 : 포인터 저장을 위한 추가 메모리 필요, 동적 기억저장소 할당 필요

성능

• 삽입 : $O(1)$, 연결 리스트 선두에 삽입
• 삭제 : $O(1)$, 이중 연결 리스트 사용
• 탐색 : 평균 $O(1)$
  • 최악 $O(n)$, 모든 키가 동일한 해시 값을 갖는 경우

연쇄법의 평균 탐색 성능

• 부하율 $\alpha$

  하나의 연결 리스트에 저장된 레코드의 평균 개수

• 키가 각 위치에 해시될 확률이 동일하다고 가정

  단순 균등 해싱 (simple uniform hashing)

• $F(\alpha)$ -> 탐색 실패 시, 평균 탐색 횟수

  • $h(k)$계산, 연결 리스트의 선두 포인터 획득 -> 1회 (상수 시간)
  • 연결 리스트의 평균 탐사 -> $\alpha$
  • $F(\alpha) = O(1+\alpha)$

• $S(\alpha)$ -> 탐색 성공 시, 평균 탐색 횟수

  $S(\alpha) = 1 + \frac{\displaystyle\sum_{j=1}^{n}{(1+\frac{j-1}{m})}}{n}$

  • $\frac{j-1}{m}$ - > j번째 원소의 삽입 전 리스트의 평균 길이
    
    
  • $(1+\frac{j-1}{m})$
    • 원소의 삽입이 리스트 끝에서 이루어진다면,
      성공적 탐색 시, 리스트 원소의 비교 횟수는
      그 원소가 리스트에 삽입될 때의 탐사 횟수에 1을 더한 것과 같다.
      
      
  • $S(\alpha) = O(1+\alpha)$
    • $n=O(m)$이면, $O(1)$

해결방안 2. 개방 주소법

모든 레코드를 해시 테이블 자체에 저장

• 연결 리스트 미사용
  
  
• 해시된 위치에 다른 레코드가 있으면,
  미리 정해진 방법에 따라 해시 테이블 내 다른 위치를 탐사

탐사 순서 ( probe sequence )

• 어떤 키를 위해 탐사하는 테이블 위치들의 순서
  • $H(k,p)$ -> 키 k를 위해 p번째 탐사되는 위치
    • 즉, p는 충돌 횟수랑 같다.

연산

• 삽입

  • 탐사 순서에 따라 빈 위치를 찾아서 삽입
    • 빈 위치 -> null 값이 저장된 위치

• 탐색

  • 키를 찾았거나, 빈 위치를 찾을 때까지 탐사 순서에 따라 계속 진행

• 삭제

  • 탐사 순서 유지를 위해 null 값 대신 삭제 표시를 함
  • 탐색 시간은 부하율의 함수가 아니다.
    • 키의 삭제가 반드시 필요할 경우, 연쇄법이 더 좋음

성능

탐사 순서를 계산하는 방법에 따라 달라짐

• 선형 탐사
• 이차형 탐사
• 이중 해싱

균등 해싱 가정

각 키에 대한 탐사 순서가 $\{0, 1, ... m-1\}$에 대한
$m!$개의 순열 중에서 어느 하나로 될 확률이 모두 같은 것.

개방 주소법의 부하율 범위

$\alpha = \frac{n}{m} \leq 1$

성능 정리

탐색 실패 시, 평균 탐사 횟수 $F(\alpha)$

• $F(\alpha) \leq \frac{1}{1-\alpha}$

탐색 성공 시, 평균 탐사 횟수 $S(\alpha)$

• $S(\alpha) \leq \frac{1}{\alpha}ln\frac{1}{1-\alpha}+\frac{1}{\alpha}$

선형 탐사

$H(k, i) = (h(k) + i)\quad mod \quad m$

• $i = 0, 1, .... m-1$

• 선형 탐사의 문제 점
  • 1차 클러스터링 ( primary clustering )
    • 충돌되는 위치가 연속적으로 테이블에 있으면 점점 더 커지는 현상
    • 평균 탐색 시간의 증가를 초래한다.
• 선형 탐사의 성능

  $F(\alpha) \approx \frac{1}{2}(1+\frac{1}{(1-\alpha^2)})$
  
  
  $S(\alpha) \approx \frac{1}{2}(1+\frac{1}{(1-\alpha)})$

  • 선형 탐사법은 $\alpha$가 0.5 이하일 때 사용 가능

이차형 탐사

$H(k, i) = (h(k) + ai + bi^2)\quad mod \quad m$

• $i = 0, 1, .... m-1$
• 탐사 위치가 탐사 번호 i에 대한 2차식으로 표현
• a, b, m의 선택이 매우 중요!!!

• 이차형 탐사의 문제
  • 2차 클러스터링 ( Secondary Clustering )
    • 두 키의 초기 탐사 위치가 동일하면, 전체 탐사 순서가 동일하다.

이중 해싱

두 개의 해시 함수를 이용해서 탐사 순서를 결정

• $H(k, i)=(h_i(k) + i*h_2(k))\quad mod\quad m$
  • $i = 0, 1, .... m-1$
    
    
• 탐사 순서에서 두번째 이후에 탐사되는 위치가
  첫번째 탐사 위치와 무관
  • 클러스터링 문제 해결

• T의 모든 위치를 포함하도록 $h_2(k)$의 선택이 매우 중요!!

  • $h_2(k) = 1$ -> 선형탐사

  • $h_2(k) = 0$ -> 충돌 해결 불가

  • $m$과 $h_2(k)$의 공약수가 $d$인 경우

    • $(\frac{m}{d}h_2(k))\quad mod\quad m = (m * \frac{h_2(k)}{d})\quad mod\quad m = 0$

    • m/d번째 탐사 위치가 첫번째 탐사 위치와 동일하다.

• 상이한 탐사 순서 $\theta(m^2)$개

  • 상이한 $(h_1(k), h_2(k))$ 쌍마다 다른 탐사 순서이며,
    k에 대하여 $h_1(k)$, $h_2(k)$는 서로 독립적으로 달라진다.

  • 탐사 순서가 $\theta(m)$개인 선형 탐사법 및 이차형 탐사법에 비해
    평균적으로 좋은 성능을 보이며, 균등 해싱에 잘 접근한 방법

---