[자료구조] 해싱(Hashing)

해싱(Hashing)

산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식이다.

 

검색방법

• 키 값에 대해서 해싱 함수를 계산하여 주소를 구하고,
• 구한 주소에 해당하는 해시 테이블로 바로 이동한다.
• 해당 주소에 찾는 항목이 있으면 검색 성공, 없으면 실패

 

해싱 용어 정리

• 충돌: 서로 다른 키 값에 대해 해싱 함수로 구한 버킷 주소가 같은 경우
• 동거자: 서로 다른 키 값을 가지지만 해싱 함수에 의해서 같은 버킷에 저장된 키 값들
• 오버플로우: 버킷에 비어 있는 슬롯이 없는 포화 버킷 상태에서, 충돌이 발생하여 해당 버킷에 키 값을 저장할 수 없는 상태
• 키 값 밀도: 사용 가능한 전체 키 값들 중 현재 해시 테이블에 저장되어서 실제 사용되고 있는 키 값의 개수 정도
• 적재 밀도: 해시 테이블에 저장 가능한 키 값의 개수 중에서 현재 해시 테이블에 저장되어서 실제 사용되고 있는 키 값의 개수 정도

 

해싱 함수의 조건

• 해싱 함수는 계산이 쉬어야 한다.
• 해싱 함수는 충돌이 적어야 한다.
• 해시 테이블에 고르게 분포할 수 있도록 주소를 만들어야 한다.

 

해싱 함수의 종류

• 중간 제곱 함수: 키 값을 제곱한 결과 값에서 중간에 있는 적당한 비트를 주소로 사용하는 방법
• 제산 함수: 함수는 나머지 연산자 mod를 사용하는 방법, 키 값 k를 해시 테이블의 크기 M으로 나눈 나머지를 해시 주소로 사용
• 승산 함수: 곱하기 연산을 사용하는 방법, 키 값 k와 정해진 실수 a를 곱한 결과에서 소수점 이하 부분만을 테이블의 크기 M과 곱하여 그 정수 값을 주소로 사용
• 접지 함수: 키의 비트 수가 해시 테이블 인덱스의 비트 수보다 큰 경우에 주로 사용

1) 이동 접지 함수: 각 분할 부분을 이동시켜 오른쪽 끝자리가 일치하도록 맞추고 더하는 방법

2) 경계 접지 함수: 분할된 각 경계를 기준으로 접으면서 서로 마주보도록 배치하고 더하는 방법

• 숫자 분석 함수: 키 값을 이루고 있는 각 자릿수의 분포를 분석하여 해시 주소로 사용하는 방법, 각 키 값을 적절히 선택한 진수로 변환한 후에 각 자릿수의 분포를 분석하여 가장 편중된 분산을 가진 자릿수는 생략하고, 가장 고르게 분포된 자릿수부터 해시 테이블 주소의 자릿수만큼 차례로 뽑아서 만든 수를 역순으로 바꾸어서 주소로 사용

 

안전 해싱 함수의 특성

• 약한 충돌 저항: x와 h(x)가 주어졌을 때 h(y) = h(x)인 y를 찾는 것이 어렵게 만드는 것
• 단방향 특성: h(k) = c를 만족하는 c가 주어졌을 때, k를 찾는 것을 계산적으로 어렵게 만드는 것
• 강한 충돌 저항: h(x) = h(y)를 만족시키는 (x,y) 쌍을 계산적으로 찾기 어렵게 만드는 것

 

오버 플로우 처리 방법

 

1. 개방 주소법(open addressing)

 

1) 선형 조사법

• 선형 조사법은 단순하지만, 충돌의 횟수가 증가함에 따라서 클러스터 현상(특정 영역에 데이터가 몰리는 현상)이 발생한다는 단점이 있다.
• 해시 테이블의 크기를 다시 정할 때, 해시 함수를 바꿔야 한다. 모든 사전 엔트리들은 새로 커진 테이블에 사상되어야 한다.

template<class K, class E>
pair<K,E>* LinearProbing<K,E>::Get(const K&K)
{
// 선형 조사법 해싱 테이블 ht에서 k를 탐색
// 이 키를 가진 쌍을 발견하면, 그 쌍을 가리키는 포인터를 반환
// 그렇지 않으면 0을 반환
    int i = h(k);
    int j;
    for(j = i; ht[j] && ht[j]->first != k;){
    	j = (j+1) % b;
        if(j==i) return 0;
    }
    if (ht[j]->first==k)
    return ht[j];
    return 0;
}

 

2) 이차조사법

클러스터 확대를 줄이기 위한 다른 방법

• 재해싱(rehashing): 여러 개의 해시 함수를 사용하는 방법
• 임의 조사법(random probing): h(k)와 (h(k)+s(i)) % b를 검사, 난수 발생시키는 1에서 b-1까지의 모든 수를 1번만 생성해야 함

 

2, 체이닝(chaining)

* 선형 조사법과 같은 방법들이 효율이 좋지 않은 이유는 키를 탐색할 때 서로 다른 해시 값을 가진 키와 비교를 해야 하기 때문이다.

 

해시 테이블의 구조를 변경하여 각 버킷의 하나 이상의 키 값을 저장할 수 있도록 하는 방법이다.

체인을 사용할 때 ChainNode<pari <K,E>>* 타입의 배열 ht[0:b-1]을 이용한다.

 

동적해싱(dynamic hashing)

재조정을 한 번 할 때마다 오직 하나의 버킷 안에 있는 엔트리들에 대해서만 홈 버킷을 변경하게 하여 재조정 시간을 줄인다.

 

디렉터리를 이용한 동적 해싱

• 버킷들에 대한 포인터를 저장하고 있는 디렉터리 d를 이용한다.
• 오버플로 발생 시 해결 방법: 오버플로가 된 버킷의 모든 키에 대해 h(k,u)가 같지 않게 하는 최하위 비트 u를 정한다.

 

디렉터리 없는 동적 해싱

• 버킷 포인터의 디렉터리 d 대신 버킷의 배열인 ht를 사용
• q와 r이라는 변수를 두어 활성화된 버킷에 대한 정보를 얻어낸다.