[자료구조] 해싱(Hashing)

"Hash"는 다양한 맥락에서 다양한 일반적인 의비로 사용되는 넓은 용어

"해시"는 입력 객체로 사용하여 문자열이나 숫자를 출력하는 해시 함수 h를 의미합니다. 입력 객체는 일반적으로 문자열, 정수 또는 사용자 정의 구조와 같은 다른 객체로 구성된 더 큰 데이터 유형의 구성원입니다. 출력은 일반적으로 숫자 또는 문자열입니다. 명사 "해시"는 종종 이 출력을 가리킵니다. 동사 "해시"는 종종 "해시 함수 적용"을 의미합니다.

(위키피디아+번역)

 

문제의 정의- 배열에서 특정 값을 어떻게 찾을 것인가. in non-sorted

 

해싱의 정의

- 데이터를 해시테이블(hash table)이라는 배열에 저장하는 것

- 데이터의 키 값을 적절한 해시함수를 이용하여 해시테이블 주소로 변환하여 데이터를 찾는 방법

- 키 값 비교(comparison)를 통한 탐색보다 빠르게 탐색 가능

- 레코드의 수가 증가해도 키 값을 통해 바로 해시테이블 주소 탐색(즉 데이터 수 n과 독립적-independent 하다.)

 

정적해싱(static hashing): 데이터 bucket이 항상 동일

동적해싱(dynamic hashing): 데이터 bucket이 레코드의 증감에 따라 늘거나 줄을 수 있음.

 

 

정적 해싱(Static Hahsing)

해시 테이블

- 데이터가 해시 테이블 ht에 저장

-  ht[0]~ht[b-1]의 b개 bucket으로 분할됨

- 한 버킷은 s개의 slot으로 구성됨.

- 한 슬롯에는 하나의 사전 상이 저장됨

- 키 값이 k인 데이터의 주소 또는 위치는 해시 함수 h에 의해 결정됨

- 해시 함수는 키 값을 버킷으로 사상(mapping) 시킴

- h(k): k의 해시 또는 홈 주소(home address)

- 해시 테이블의 키 밀도(key density): n/T // 전체 키 값들 중에서 현재 해시 테이블에서 사용 가능한 키 값의 정도

• n: 테이블에 있는 쌍의 수
• T: 가능한 키의 총 개수

- 해시 테이블의 적재 밀도(loading density): α = n/(s*b) // 해시 테이블에 저장 가능한 키 값의 수 중에서 현재 저장/사용되는 키 값의 정도

• s: slot 수
• b: bucket 수

- 키 밀도 n/T는 매우 작고 b도 T보다 작게 됨

- 동거자(synonym): k1, k2에 대해 h(k1) = h(k2)인 경우 k1, k2를 h에 대한 동거자라고 한다.

 

충돌(collision)

- 새로운 쌍의 삽입 시 홈 버킷에 비어있지 않은 경우(slot의 빈자리와 무관하게 non-empty인 경우를 통칭)

- k1, k2에 대해 h(k1)=h(k2)인 경우(: 해시값이 같은 경우)

 

오버플로(overflow)

- 버킷에 할당된 슬롯(slot)을 이미 소진하여 더 이상 버킷에 항목을 저장할 수 없는 경우 (여유 슬롯 없음)

 

오버 플로가 발생하지 않을 경우

- 삽입, 삭제, 탐색 시간: 사전의 엔트리 수인 n에 무관. 계산 시간과 버킷을 탐색하는데 소요 시간에만 좌우

- 버킷 크기는 작기 대문에, 버킷 내에서 탐색을 위해 순차 탐색 기법을 사용할 수 있음

 

일반적으로 오버플로는 필연적(=연역적?)으로 발생

 

해싱 기법

- 해시 함수를 사용하여 키를 해시 테이블 버킷에 사상

- 해시 함수는 충돌 수 최소화하도록 선택해야 함 (hash값 최대한 분산)

- 오버플로 처리 기법 필요

 

해시함수

-키를 해시 테이블 내의 버킷으로 사상시킴. 계산이 쉽고 충돌이 적어야함

- 균일 해시 함수(uniform hash function): h(k)=i가 될 확률은 모든 버킷 i에 대해서 1/b가 됨.(대응 확률이 모두 균일)

-다양한 종류의 균일 해시 함수가 사용됨.-키를 산술적 연산이 가능한 데이터 타입으로 변환 등

 

해시 함수의 조건

1) 계산이 쉬워야함.-비교 검색보다 빨라야 해싱의 의미가 있음

2) 충돌이 적어야함.

해시 테이블에 고르게 분포할 수 있도록 주소를 만들어야함.

 

제산(division)함수

- 실제로 가장 많이 쓰이는 해시 함수

- 키 값이 음이 아닌 정수라고 가정

- 홈 버킷은 모듈러(%)연산자에 의해 결정- h(k) = k%D

- D의 선택이 오버플로 발생 수에 영향

- D가 홀수가 되도록 제한, b=D가 되도록

- 배열 크기를 두배로 만들면 버킷 수가 b에서 2b+1로 증가

 

중간 제곱(mid-square) 함수

- 키를 제곱한 후에 결과의 중간에 있는 적절한 수의 비트를 취함

- 제곱 수의 중간 비트는 그 키의 모든 비트에 의존하므로 서로 다른 키들은 서로 다른 해시 주소를 갖게 될 확률이 높게 됨

- 사용되는 비트 수는 테이블 크기에 달려있음.- r개 비트 사용시 값의 범위는 0~2^r -1

 

접지(folding) 함수

- 숫자로 된 키 k를 몇 부분으로 나누는데, 마지막 부분을 제외하고는 모두 길이가 같음

- 각 부분들을 서로 더하여 k에 대한 해시 주소 만듦

두가지 접지 방식

-이동 접지(shift folding)

• 마지막을 제외한 모든 부분들을 이동 시킴
• 최하위 비트가 마지막 부분의 자리와 일치하도록 맞춤
• 서로 다른 부분들을 더하여 h(k)를 얻음

- 경계 접지(folding at the boundaries)

• 키의 각 부분들을 경계에서 겹치게 함
• 같은 자리에 위치한 수들을 더하여 h(k)를 얻음

-숫자 분석 함수(digit analysis)

• 키 값의 각 자릿수의 분포를 분석하여 해시 주소로 사용
• 각 키를 어떤 기수(radix) r을 이용해 하나의 숫자로 바꿈
• 이 기수를 이용해 각 키의 숫자들을 검사함
• 가장 편향된(skewed) 분산을 가진 숫자 생략
• 남은 숫자만으로 해시 테이블 주소를 결정

 

키를 정수로 변환

- 음이 아닌 정수로 키를 변환

- 유일한 정수일 필요는 없음

- 스트링을 동일한 정수로 변환시키기만 하면 됨.

 

오버플로 처리(overflow handling)

1) 개방 주소법(open addressing)

- 선형 조사법(linear probing)

- 이차 조사법(quadratic probing)

- 재해싱(double hashing)

- 임의 조사법(random probing)

 

2) 체인법(chaining): 임의의 버킷에 Assign(주소 개방X)

 

3) 선형 조사법

- 오버플로가 발생하면, 그 다음 버킷에 빈 슬롯이 있는지 조사

- ht[h(k)+1]%b의 순서에 따라 해시 테이블 버킷 검색

- 빈 버킷이 있으면 데이터가 그 버킷(슬롯)으로 삽입

- 빈 자리가 있는 버킷이 없으면 해시 테이블이 만원인 것(테이블 크기를 늘려야함)

- 테이블의 크기를 다시 정하려면 해시 함수 교체+사전 엔트리 다시 사상.

 

4) 2차 조사법(Quadratic Probing)

- 선형 조사법에서 발생하는 집중문제를 해결하기 위한 방법

- 특정한 수만큼 떨어진 곳을 순환적으로 빈 공간을 찾아 저장

- h(k), (h(k)+i)%b, (h(k)+i^2)%b, (0<=i<=(b-1)/2)

 

5) 재해싱(Rehashing, Double Hashing)

- 선형 조사법에서 발생하는 집중 문제를 해결하기 위한 방법

- 키 값에 대해 여러 해시 함수를 사용

- A popular second hash function = R - (key%R)

R은 cable size보다 작은 a prime number

 

선형 조사법이 효율이 좋지 않은 이유: 키를 탐색할 때 서로 다른 해시 값을 갖는 키와 비교

해결 방안: 각 버킷에 대해 동거자들을 키 리스트(linked list 형태)로 구성

- 불필요한 비교 제거

- 탐색 시 해시 주소 h(k)를 계산하여 h(k)에 대한 리스트만 검사

 

체인법

- 체인을 사용할 때 배열 ht[0:b-1]을 이용

- ht[i]는 버킷 i에 연결된 체인 중 첫 번째 노드를 가리킴

 

동적 해싱(Dynamic Hashing)--size 변동

동기

- 적재 밀도가 경계값을 넘을 대마다 해시 테이블 크기 증가.(D=b -> new D = 2b+1. 확장성 해싱-extendible hashing이라고도 불림)

- 원래의 해시 테이블의 값을 새로운 해시 테이블로 재조정 필요.(단순 복사X, 하나의 버킷 안에 있는 엔트리에 대해서만 홈 버킷 변경->재조정 시간 감소)

 

디렉토리를 사용하는 동적 해싱

- 버킷들에 대한 포인터를 저장하고 있는 디렉토리 d를 이용

- 디렉토리의 크기: h(k)의 비트 수에 좌우

- 디렉토리 깊이(depth)

• 디렉토리를 인덱싱하는 h(k)의 비트 수
• t: 깊이, 2^t: 디렉토리 크기
• 버킷 수 <= 디렉토리 크기