알고리즘 이론 11강. 해시 테이블

 

[해시 테이블]

: 해시 테이블은 사전(dictionary)을 구현하는 가장 효율적인 자료구조.

: 해시 테이블에서 원소를 찾는건 연결리스트에서 원소를 찾는 것만큼 오래 걸릴수 있지만, 실제론 성능이 탁월.

 

 

 

[해싱의 시간 복잡도]

- 해싱 평균 시간복잡도 : O(1)

- 해싱 최악 시간복잡도 : O(n)

: 기존의 자료에 대한 operation들은 O(n)의 시간복잡도.

: BST와 같은 트리 이용한 방식은 평균, 최악 시간복잡도는 O(logn)

 

 

 

[사전(Dictionary)과 해시 테이블(Hash Tables)]

- 사전(Dictionary)

  : key를 사용해 item들을 저장하는 동적 데이터 구조

  : 삽입, 검색, 삭제 연산을 제공

 

- 해시 테이블(Hash Table)

  : 사전을 구현하는데 효율적인 방법

  : 보통 배열의 일반화

 

---

 

[직접 번지 테이블(Direct-address Tables)]

: 일반적인 배열의 방식

: 키들의 전체집합이 작고, 어떤 두 원소도 같은 키를 가지고 있지 않을때 잘 작동하는 단순 기법.

: 삽입, 검색, 삭제 연산의 시간복잡도는 O(1)

 

 

 

[해시 테이블(Hash Table)]

: 직접 번지 테이블의 방식은 키들의 전체집합이 커지면 문제(최대값과 같은 크기의 배열을 생성 필요)

: 키들이 실제 저장되는 개수에 비해 전체 크기가 너무 크므로 비효율

 

: 해시 테이블은 원소 검색에 소요되는 시간 O(1)을 유지하며 더 작은 공간을 필요로 한다.

: 원소 K를 해시함수에 넣어 h(K) 해시테이블 T에 h(K)위치에 넣는다.

: 해시함수 정의 필요.

 

 

 

[해시 함수 예시]

ex) h(i) = i % 10 k = {41, 34, 7, 18} 이면 실제 해시 테이블 T에 k값들이 들어가는 위치는 각각 h(k) = {1, 4, 7, 8} 이다.

: 해시 테이블은 정렬된 값에 대한 정보가 없다. (해시함수로 인해 값들 위치가 바뀜)

=> getMin, getMax, removeMin, removeMax, sorted order과 같은 작업에서 해시 테이블은 비효율

 

---

 

[충돌(Collisions)]

 : 해시함수로 인해 여러 key들이 매핑되는 중 서로 다른 key가 같은 공간에 배치되는 경우 발생하는 문제

 : 이러한 충돌을 최소화 하는 해시 함수를 디자인해야한다.

 

 case 1) 주어진 key가 해시테이블 크기 m보다 작거나 같을때 : 해시 함수에 전적으로 충돌 여부 달려있다.

 case 2) 주어진 key가 해시테이블 크기 m보다 클때 : 무조건 충돌 발생(key값이 테이블 크기보다 무조건 크기때문)

 

 

 

[충돌문제 해결 방법]

1. Chaining

  : 해시 테이블의 같은 slot에 연결 리스트의 형태로 요소들을 저장하는 방식

2. Open Addressing

 : 모든 원소들이 스스로의 hash 테이블에 저장

 : 충돌발생시, 체계적인 절차를 통해 테이블 내 자유 slot에 저장한다.

 

 

 

[Chaining을 이용한 해싱]

# Chaing Hasing 연산자

1. Chained-Hash-Insert(T, x) : key값 x에 해당되는 해시테이블 위치의 head에 삽입(worst : O(1))

2. Chained-Hash-Delete(T, x) : key값 x를 해시테이블 T에서 제거

 : 단일 연결 리스트일시 해당 연결리스트의 길이만큼 시간복잡도 늘어나고, 다중 연결리스트이면 O(1)의 최악 시간복잡도

3. Chained-Hash-Search(T,k) : key값 k 검색 (worst : 약 list의 길이 = O(n))

 

 

 

[Chaining을 이용한 해싱의 시간복잡도]

: key 검색에 걸리는 시간

1. 최악 케이스(Worst case)

 : 테이블내 한 slot에 모든 원소들이 연결리스트 형태로 들어가 있을때.

 : ⊙(n)

2. 평균 케이스(Average case)

 : 해시 함수가 key들을 얼마다 테이블에 적절히 배치하냐에 따라 달려있다.

 

# 해시테이블의 적재율 : a = n/m (n = table에 저장된 요소개수, m = table의 slot 개수)

 

 

 

[해시테이블 검색에 따른 시간 복잡도]

: 결과만 기억..

# 1. 검색 실패 : O(1) + a = Θ(1+a) : (a = 적재율, O(1) = 해시함수 계산시간)

# 2. 검색 성공 : O(1+a) = O(1+1+a/2-a/2n)

: key 삽입의 worst case는 O(1) 이다.

: key 삭제의 worst case는 O(1) 이다. (단, 양방향 연결 리스트일때)

: 즉, 모든 chaining 방식의 해시 테이블 연산들은 평균적으로 O(1)의 시간을 소모한다.

 

---

 

[해시 함수(Hash Functions)]

: 주어진 key값을 해시 테이블 주소값으로 변환시키는 함수

 

# 좋은 해시함수

 : 쉬운 계산 / 무작위 랜덤 함수 (모든 입력과 출력이 그럴듯하게 똑같게)

 : 매우 비슷한 key값들이 같은 slot에 배치되는것을 최소화 해야한다.

 

 

 

[해시함수 1 - Division 방법]

h(k) = k mod m

: 주어진 k값을 해시함수의 슬롯개수 m으로 나눈 나머지 값을 해시 주소로 사용

: 빠르지만, 특정 m값들에 대해서는 좋지 않다(2, non-소수등)

: m이 소수인 경우에 좋은 방법

 

 

 

[해시함수 2 - Multiplication 방법]

h(k) = floor(m*(kA - floor(kA))) = floor(m(k*A mod 1))

1) 주어진 k값을 상수 A와 곱한다 (0 < A < 1)

2) kA의 일부분(소수부분)을 추출

3) 추출한 일부분을 m으로 곱한후 floor를 취한다.

: 느리지만, 해시테이블 크기 m값과 큰 상관이 없이 독립적이다.

# 해시함수 예시

k = 3, m = 8 슬롯, 상수 A = .61 일때 1) kA = 1.83 2) floor (f m) = floor(.83 * 8) = floor(6.64) = 6

 

 

 

[Universal Hashing]

: 악의적인 사람이 일부로 같은 슬롯에 모든 key값들을 매핑하는 해시 함수를 선택하는 것을 방지하기 위한 것.

: 매번 다른 해시 함수를 사용하는 방식

: 두 키 사이의 충돌 가능성은 무작위이고 독립적으로 두 슬롯을 선택할 수 있는 확률의 1/m이다.

: 이 방식은 일반적으로 좋은 결과를 보여주고, 악의적으로 worst-case 도출하기 매우 어렵다(랜덤)

 

---

 

[Open Addressing]

: 충돌 문제를 해결하는 두번째 방법 (첫번째 : chaining)

: 모든 키값들을 저장하기 위한 공간이 충분히 있을때(m > keys) => 테이블 스스로 key를 저장

: 연결리스트 사용 X

- 삽입 : 슬롯이 차있으면, 다른 공간에 삽입 시도를 삽입될때까지 반복한다 (체계적 규칙 기반)

- 검색 : 동일한 규칙 기반으로 따라간다(해당 규칙의 길이에 따라 소모 시간 결정)

- 삭제 : 보다 어렵다

 

 

 

[Open Addressing 방법들]

: 테이블내 삽입되는 특정 key값 위치가 차있을때 사용하는 규칙들

1. Linear probing

2. Quadratic probing

3. Double hashing

 

 

 

[규칙 1. Linear probing(선형적 방식)]

: 충돌 발생시, 테이블내 해당 슬롯의 다음 슬롯 검사해나가는 방식

probe sequence : <h(k), h(k)+1, h(k)+2 ... >

# 검색

 case1 ) 검색한 key값과 동일한 key값이 h(k)에 저장되어있는 경우

 case2 ) 검색한 key값에 대한 슬롯이 비어있는 경우

 case3 ) 검색한 key값의 슬롯 위치 h(k)가 다른 값이 저장되어있는 경우

  : 검색한 key값을 찾거나 비어있는 슬롯을 찾을때까지 다음 index를 검색한다.

# 삭제

 : 슬롯이 비어있는지 확인해볼수가 없고, 슬롯이 찬 이후에 삽입된 key들을 되찾아오는것은 불가능하다.

 => 해결책 : 슬롯을 감시하는 값 DELETED로 마킹한다. (이런 deleted slot은 삽입에서도 사용될수 있다)

 

 

 

[주요 근접 문제(Primary Clustering Problem)]

: Linear probing 방식의 주요 문제점

: 특정 슬롯들은 값들이 들어올 확률이 높다 => 평균 삽입 및 검색 소요 시간이 증가

모든 슬롯이 비어있을때 모든 슬롯은 key값들어올 확률이 1/m이다. 하지만 key값들이 들어오며, 특정 비어있는 슬롯들에 값이 들어올 확률은 증가한다. ex) 슬롯명 a, b, c, d, e, f ... 이 있을때, 슬롯 a, b, c가 차있는 상태에서 슬롯 d에 값이 들어올 확률은 4/m 이다.

 

 

 

[규칙 2. Quadratic probing(2차함수 방식)]

k = key값, i = probe number 값 h(k,i) = (h'(k) + c1*i + c2*i^2) mod m

: linear때 생기는 clustering 문제 해소 위해 만든 방법

 

 

 

[규칙 3. Double Hashing]

: 첫번째 슬롯 결정 위해 첫번째 해시 함수만 사용

: probe sequence 증가에는 두번째 해시 함수를 사용한다.

h(k,i) = ( h1(k) + i*h2(k) ) mod m

# double hashing 예시

h1(k) = k mod 13  (해시함수 1 - division 방식) h2(k) = 1 + k mod 11 사용 한다할떄, ex) key = 14 삽입  h1(14,0) = 14 mod 13 = 1    //이때 해당 슬롯 차있으면 아래 실행  h(14,1) = (h1(14) + h2(14)) mod 13 = (1 + 4) mod 13 = 5  h(14,2) = (h1(14) + 2*h2(14)) mode 13 = 9