해싱 (Hashing)

A Code AM·2020년 4월 22일

Algorithm

목록 보기

4/9

1. Hash Table

해쉬 테이블은 dynamic set을 구현하는 효과적인 방법 중 하나
적절한 가정하에서 평균 탐색, 삽입, 삭제시간 O(1)
보통 최악의 경우 O(n)

2. Hash Table이란

: 해쉬 함수(hash function) h를 사용하여 키 k를 T[h(k)]에 저장 = 하나의 큰 배열

h : U -> { 0, 1, ... , m-1 }
여기서 m은 테이블의 크기, U는 모든 가능한 키들의 집합
키 k가 h(k)로 해슁되었다고 말함.

index = h(k) -> 배열의 인덱스를 해쉬테이블의 주소라고 말한다

즉 각 키에 대한 해쉬함수값을 그 키를 저장할 배열 인덱스로 사용한다.

3. 해쉬 함수의 예

모든 키들을 자연수라고 가정 (어떤 데이터든지 자연수로 해석하는 것이 가능)
예 : 문자열
- ASCII 코드 : C = 67, L = 76, R = 82, S = 83
- 문자열 CLRS는 (67 128^3) + (76128^2) + (82128^1) + (83128^0) = 141,764,947 (128진수로 가정)
해쉬 함수의 간단한 예 :
- h(k) = k % m, 즉 key를 하나의 자연수로 해석한 후 테이블의 크기 m으로 나눈 나머지
- 항상 0 ~ m-1 사이의 정수가 됨

4. 충돌 (Collision)

두 개 이상의 키가 동일한 위치로 해슁되는 경우
즉 서로 다른 두 키 k1과 k2에 대해서 h(k1) = h(k2)인 상황
일반적으로 |U|>>m 이므로 항상 발생 가능 (즉 단사함수가 아님) - 단사함수가 되려면 배열(m)의 크기가 들어올 수 있는 데이터들(U)의 크기보다 크거나 같아야 한다. (일반적으로 담사함수가 될 수 없다)
==> 단사함수 : 1:1 함수(참고 : https://ko.wikipedia.org/wiki/%EB%8B%A8%EC%82%AC_%ED%95%A8%EC%88%98)
만약 |K|>m이라면 당연히 발생(여기서 k는 실제 저장된 키들의 집합)
충돌이 발생할 경우 대처 방법이 필요
대표적인 두 가지 충돌 해결 방법 : chaining과 open addressing

5. (seperate) chaining에 의한 충돌 해결

: 테이블의 각각의 칸에 직접 키를 저장하지 않고 한 칸에 대응(맵핑)되는 모든 키들을 연결리스트(Linked List)를 만들어서 실제 테이블에는 연결 리스트의 첫번째 주소를 저장함.

< Chaining >

키의 삽입(Insertion)
- 키 k를 리스트 T[h(k)]의 맨 앞에 삽입 : 시간 복잡도 O(1)
- k를 삽입하기 위해서는 k에 대한 해쉬함수를 먼저 계산한 후 테이블의 인덱스로 사용한다. 테이블의 각 칸에는 연결리스트가 달려있고 키를 연결리스트에 노드를 만들어서 추가하면 됨. ( 가장 쉬운 방법은 맨 앞에다 추가하는 것)
  - 중복된 키가 들어올 수 있고 중복 저장이 허용되지 않는다면 삽입시 리스트를 검색해야 함. 따라서 시간 복잡도는 "리스트의 길이에 비례" << 일반적
키의 검색(Search)
- 리스트 T[h(k)]에서 순차검색 -> 먼저 내가 검색할 키(k)에 대한 해쉬 함수를 계산한 다음에 해쉬 테이블의 그 인덱스 칸에 가면 연결리스트가 있고 그 연결리스트 안에서 순차검색 해야함. (정렬해도 시간복잡도 똑같아서 의미는 거의 없다)
- 시간 복잡도는 키가 저장된 "리스트의 길이에 비례"
키의 삭제(Deletion)
- 리스트 T[h(k)]로 부터 키를 검색 후 삭제
- 일단 키를 검색해서 찾은 후에는 O(1)시간에 삭제 가능 -> 단방향이면 키를 삭제하기 위해선 테크닉이 좀 필요함
최악의 경우는 모든 키가 하나의 슬롯으로 해슁되는 경우
- 길이가 n인 하나의 연결리스트가 만들어짐 (길이가 n인 연결리스트나 마찬가지)
- 따라서 최악의 경우 탐색시간은 O(n) + 해쉬 함수 계산 시간 (피해가긴 어렵다)
- |u|는 m보다 훨씬 큰 경우가 많고 어떤 한 집합은 |u|/m 보다 크거나 같다. 내가 실제로 저장하는 데이터 n은 항상 |u|/m보다는 작다. 고로 |u| > m*n이므로 크기 관계에 의해서라도 위의 상황은 존재할 수 밖에 없다.
- 평균시간복잡도는 키들이 여러 슬롯에 얼마나 잘 분배되느냐에 의해서 결정. 리스트의 길이에 비례한다.

SUHA(Simple Uniform Hashing Assumption)

각각의 키가 모든 슬롯들에 균등한 확률로 (equally likely) 독립적으로 (independently) 해슁된다는 가정
- 성능 분석을 위해서 주로 하는 가정임
- hash 함수는 deterministic (= 결정론 | 해쉬 함수는 랜덤함수가 아니다 => 같은 key에 대한 해쉬함수 값은 같아야 한다 ) 하므로 현실에서는 불가능
- universal hashing - randomize된 hashing function을 사용하는 기법
- 모든 가능한 키들의 집합 U가 있을때 테이블 안에 저장될 키들을 random selection 해서 hash table에 저장 (key가 랜덤이고 해쉬함수가 랜덤은 아님)
Load factor a = n / m :
- n : 테이블에 저장될 키의 개수
- m : 해쉬테이블의 크기, 즉 연결리스트의 개수
- 각 슬롯에 저장된 키의 평균 개수
연결리스트 T[j]의 길이를 n(j)라고 하면 E[n(j)] = a (SUHA가 성립하면 각각의 키들이 각각의 슬롯에 맵핑될 확률이 다 동일하다는 뜻)
만약 n = O(m)이면 평균 검색시간은 O(1) -> 그러니까 SUHA가 성립해야 O(1)인것 (가설임)