14 해싱 (C언어로 쉽게 풀어쓴 자료구조)

14.1 해싱이란?

-키값 비교로써 탐색하고자 하는 항목에 접근

-해싱(hashing): 키 값에 대한 산술적 연산에 의해 테이블의 주소를 계산하여 항목에 접근

-어떤 항목의 키만을 가지고 바로 항목이 들어 있는 배열의 인덱스를 결정

-해시 테이블: 키 값의 연산에 의해 직접 접근이 가능한 구조

14.2 추상 자료형 사전

사전의 개념

사전(dictionary): (키,값)쌍의 집합 (=맵, 테이블)

• 키(key): 사전의 단어처럼 항목과 항목을 구별시켜주는 것
• 값(value): 단어의 설명에 해당한다

-오직 키에 의해서 관리된다<->리스트: 위치에 의하여 관리

 

사전의 연산

add, delete, search

 

14.3 해싱의 구조

해시함수(hash function)

-탐색키를 입력받아 해시주소 생성

-이 해시주소가 배열로 구현된 해시테이블의 인덱스

-M개의 버킷으로 이루어진 테이블

-하나의 버킷은 s개의 슬롯을 가질 수 있다

 (이유: 서로 다른 두 개의 키가 해시함수에 의해 동일한 해시주소로 변환될 수 있기 때문에, 여러개의 항목을 동일한 버킷에 저장하기 위함)

-하나의 슬롯에는 하나의 항목이 저장된다

 

-해시테이블에 존재하는 버킷의 수가 M개->해시함수 h는 모든 키에 대하여 0≤h(x)≤M-1 의 범위의 값을 제공해야 한다

-충돌: 서로 다른 두 개의 키 k1과 k2에 대하여 h(k1)=h(k2)인 경우 (이때 k1과 k2는 동의어라고 한다)

-충돌이 발생하면 같은 버킷에 있는 다른 슬롯에 항목을 저장하게 된다

-충돌이 자주 발생하면 버킷 내부에서의 순차탐색 시간이 길어져서 탐색 성능이 저하될 수 있다(Sol: 해시함수 수정, 해시테이블 크기 조절)

 

-오버플로우(overflow): 충돌>버킷에 할당된 슬롯 수 -> 더이상 항목을 저장할 수 없게 되는 것

-if s=1이면 overflow

 

이상적인 해싱

-해시 테이블에 공간이 넉넉해서 하나씩 개별주소를 줄 수 있음->탐색시간이 O(1)이 되므로 이상적임

 

실제의 해싱

-해시테이블의 크기가 제한되어있음->하나의 키당 하나의 공간을 할당X

-키(k)/해시테이블의 크기(M)->그 나머지를 해시 테이블의 주소로!

  -키를 정수i라고 하면 0~M-1까지의 숫자가 생성된다

h(k)=k mod M

 

ex)하나의 버킷에 여러 개의 슬롯이 있는 경우(충돌+overflow)

p.542 quiz

14.4 해시 함수

<좋은 해시함수의 조건>

• 충돌이 적어야 한다
• 해시함수 값이 해시테이블의 주소 영역 내에서 고르게 분포되어야 한다
• 계산이 빨라야 한다

 

제산함수

-나머지 연산자(mod)를 사용하여 키를 해시 테이블의 크기로 나눈 나머지를 해시주소로 사용

h(k) = k mod M

 

-M의 범위가 0~M-1이어서 해시 테이블의 인덱스로 사용하기에 이상적인 값

-해시테이블의 크기 M은 주로 소수(Prime number)

-장점: 다양한 응용 분야에 쉽게 적용

          해시 주소를 고르게 분포시키는 좋은 방법

-M이 짝수-> k가 짝수->h(k)는 짝수

                           홀수->h(k)는 홀수

 

-0~M-1을 골고루 사용하는 값을 만들어내야해서 테이블 크기 M은 항상 홀수여야 한다. (그래서 소수이면 좋음)

-k mod M이 음수인 경우: 여기에 M을 더해서 결과값이 항상 0~M-1이 되도록 한다

int hash_function(int key)
{
    int hash_index = key%M;
    if (hash_index < 0)
        hash_index += M;
    return hash_index;
}

 

 

폴딩함수

-탐색키가 해시 테이블의 크기보다 더 큰 정수일 때 (ex.키는 32비트, 해시 테이블의 인덱스는 16비트 정수)

-폴딩(folding): 키의 일부만 사용하는 것이 아니고 키를 몇 개의 부분으로 나누어 이를 더하거나 비트별로 XOR 같은 부울연산을 하는 것

-ex) 32비트 키를 2개의 16비트로 나누어 비트별로 XOR 연산

hash_index = (short)(key^(key>>16))

-키를 여러 부분으로 나누어 모두 더한 값을 해시주소로 사용한다

 

<키를 나누고 더하는 방법>

-이동 폴딩(shift folding): 키를 여러 부분으로 나눈 값들을 더하여 해시주소로 사용

-경계 폴딩(boundary folding): 키의 이웃한 부분을 거꾸로 더하여 해시주소로 사용

 

중간제곱함수

탐색 키를 제곱한 다음, 중간의 몇 비트를 취해서 해시주소 생성

-제곱한 값의 중간 비트들은 대개 키의 모든 문자들과 관련이 있기 때문에 서로 다른 키는 몇 개의 문자가 같을 지라도 서로 다른 해싱 주소를 갖게 된다

 

비트 추출 방법

해시테이블의 크기가 M=2^k일 때 키를 이진수로 간주하여 임의의 위치의 k개의 비트를 해시 주소로 사용

-키의 일부 정보만을 사용하므로 해시 주소의 집중현상이 일어날 가능성

 

숫자 분석 방법

키 중에서 편중되지 않는 수들을 해시테이블의 크기에 적합한 만큼 조합하여 사용(ex 학번에서 필요한 숫자만 조합하여 사용)

-숫자로 구성된 키에서 각각의 위치에 있는 수의 특징을 미리 알고 있을 때 유용

 

탐색키가 문자열일 경우 주의할 점

-가장 간단한 방법: 문자의 아스키 코드값, 유니코드값 사용->첫 번째 문자로 구별 (이 경우 충돌이 넘 많다)

-가장 보편적인 방법: 각 문자의 아스키 코드 값을 모두 더하기 (cup과 puc을 구분하기 어렵다+아스키코드의 범위가 65~122니까 3자리로 이루어진 키라고 하면 195~336으로 해시코드가 집중된다)

-더 좋은 방법: 글자들의 아스키 코드 값에 위치에 기초한 값을 곱하는 것

ex)문자열 s가 n개의 문자를 가지고 있다고 가정, i번째 문자가 'u_i'라고 하면

계산량을 줄이기 위해 호너의 방법(Horner's method)을 사용하면

int hash_function(char *key)
{
    int hash_index = 0;
    while (*key)
        hash_index = g*hash_index + *key++;
    return hash_index;
}

-문제점: 긴 문자열로 되어있을 경우 오버플로우를 일으킬 수 있다. but C언어에서는 오버플로우를 무시하므로 여전히 유효한 해시 주소를 얻을 수 있다. 

-보통 g값으로는 31 사용

-오버플로우 발생 시 해시코드의 값이 음수가 될 수도 있다

p.546 quiz

 

14.5 개방 주소법

 

충돌과 오버플로우

충돌(collision): 서로 다른 키를 갖는 항목들이 같은 해시주소를 갖는 현상

-충돌이 발생하고, 해시주소에 더이상 빈 버킷이 남아있지 않으면 오버플로우 발생

-오버플로우 발생 시 해시테이블에 항목을 저장하는 것이 더이상 불가능

 

<오버플로우의 해결책>

• 개방 주소법(open-addressing): 충돌이 일어난 항목을 해시테이블의 다른 위치에 저장한다  (종류: 선형조사법, 이차조사법, 이중해시법, 임의조사법)
• 체이닝(chaning): 해시테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시테이블의 구조를 변경한다

 

선형 조사법

-조사(proving): 해시테이블에서 비어있는 공간을 찾는 것

 

<방법>

1. 충돌이 일어난 곳 다음, 그 다음 이렇게 찾아가면서 비어있는 공간이 나올 때까지 계속 조사한다
2. 만약 테이블의 끝에 도달하게 되면 다시 테이블의 처음으로 간다
3. If 조사를 시작한 곳으로 되돌아오면 테이블이 가득 찬 것으로 판단한다

조사위치: h(k), h(k)+1, h(k)+2, h(k)+3, ...

-군집화(clustering): 한 번 충돌이 시작되면 그 위치에 항목들이 집중되는 현상

 

장점

-간단

단점

-오버플로우가 자주 발생하면 군집화(clustering)과 결합(coalescing)에 의해 탐색의 효율이 크게 저하

 

 

이차 조사법

이차 조사법(quadratic probing): 선형조사법과 유사하지만 조사 위치가 좀 다르다

(둘다 충돌이 발생했을 때 해시 함수값에 어떤 값을 더해서 다음 위치를 얻는다)

-조사할 위치 식: (h(k) + inc*inc) mod M for inc=0, 1,...,M-1

-조사되는 위치: h(k), h(k)+1*1, h(k)+2*2, h(k)+3*3, ...

-모든 위치를 조사하려면 여전히 테이블의 크기는 소수여야 한다

 

-선형조사법의 문제인 군집과 결합을 크게 완화 가능

-얘도 2차 집중문제를 일으키긴 하는데 1차 집중처럼 심각하진 않다

-2차 집중의 이유: 동일한 위치로 사상되는 여러 키들이 같은 순서에 의하여 빈 버킷을 조사하기 때문(이중해싱법으로 해결 가능)

 

 

이중 해싱법(double hashing)

-이중 해싱법(double hashing)=재해싱(rehashing): 오버플로우가 발생함에 따라 항목을 저장할 다음 위치를 결정할 때, 원래 해시 함수와 다른 별개의 해시함수를 이용하는 방법

-장점: 항목들을 해시테이블에 보다 균일하게 분포시킬 수 있으므로 효과적인 방법이다

-선형조사법&이차조사법은 해시함수값이 같으면 조사되는 위치도 같다

 

-이중해싱법에서는 키를 참조하여 더해지는 값이 결정된다

-그래서 해시 함수값이 같더라도 키가 다르면 서로 다른 조사 순서를 갖는다->2차집중을 피할 수 있다

-해시함수: h'(k) = C - (k mod C)

->[1,...,C]사이의 값을 생성

-조사되는 위치: h(k), h(k)+h'(k), h(k)+2h'(k), h(k)+3h'(k),...

-C는 보통 테이블의 크기인 M보다 약간 작은 소수, M은 반드시 소수(같은 위치만 되풀이되는 것을 방지)

-이중해싱에서는 같은 버킷+같은 탐색순서를 가지는 요소들이 거의 없기 때문에 집중 현상이 매우 드물다

 

ex)

 

-문제점: 한 번도 사용되지 않은 위치가 있어야만 탐색이 빨리 끝난다

-거의 모든 위치가 사용되고 있거나 사용된 적이 있는 경우 테이블의 거의 모든 위치를 조사하게 된다(체이닝으로 해결)

p.558 quiz

14.6 체이닝

-선형조사법이 탐색시간이 많이 걸리는 이유: 충돌 때문에 해시 주소가 다른 키하고도 비교를 해야함

-해결: 해시 주소가 같은 키만을 하나의 리스트로 묶어둔다 (이때 리스트의 크기를 예측할 수 없으니 연결 리스트 사용)

 

체이닝(chaining): 오버플로우 문제를 연결리스트로 해결한다

-각 버킷에 고정된 슬롯을 할당(x) 삽입/삭제가 용이한 연결리스트 할당(o)

 

-연결리스트의 어디에다 새로운 항목을 삽입할것??

• 연결리스트의 처음에(만약 키들의 중복을 허용한다면)->가장 능률적
• 연결리스트의 뒤에(키들 중복 허용X면 어차피 연결리스트를 처음부터 탐색해야 하니까)

 

<체이닝의 구현>

p.564 quiz

14.7 해싱의 성능 분석

적재 밀도(loading density), 적재 비율(loading factor): 저장되는 항목의 개수(n)와 해시 테이블의 크기(M) 의 비율

 

-a=0이면 해시테이블은 비어있다

-a의 최댓값은 충돌 해결 방법에 따라 달라진다

 

• 선형조사법: 해시테이블이 가득 찬다면 각 버킷당 하나의 항목이 저장되기 때문에 1

<탐색을 위한 비교연산의 개수>

• 체인법: 저장할 수 있는 항목의 수가 해시 테이블의 크기를 넘어설 수 있기 때문에 a는 최댓값을 가지지 않는다

-a=항목의 개수/연결리스트의 개수 (=평균적으로 하나의 연결리스트당 몇 개의 항목을 가지고 있느냐)

-실패한 탐색: 찾고자 하는 위치에 연결리스트가 비어있다면 O(1)

-평균적인 경우: a만큼의 항목을 탐색해야 한다

-성공한 탐색: 항상 연결리스트에 항목이 존재할 것. 평균적으로 a만큼의 항목 비교+테이블에 존재하는 포인터까지 계산에 넣는다

a가 증가하더라도 성능이 급격하게 떨어지지 않지만 효율성을 위해 a를 유지할 필요가 있다

• 선형조사법: 적재밀도 0.5이하로 유지
• 이차조사법&이중해싱법: 적재밀도 0.7이하로 유지
• 선형조사법: 테이블의 크기에 따라 저장할 수 있는 요소들의 개수에 자연적으로 제한이 가해지게 된다(but 선형조사법이 적재밀도가 작은 경우에는 이차조사법/이중해싱보다 더 효율적일 수 있다)
• 체인법: 적재밀도에 비례하는 성능(장점: 성능을 저하시키지 않고 얼마든지 저장할 수 있는 요소의 개수를 늘릴 수 있다)(링크를 위한 메모리낭비문제는 저장되는 자료의 크기에 따라 달라진다)

 

<해싱 vs 이진탐색(배열 사용)>

-해싱이 더 빠름

-삽입이 쉬움

-이진탐색트리는 현재값 다음으로 큰 값/다음으로 작은 값을 쉽게 찾을 수 있다는 장점

-이진탐색트리에서는 값의 크기순으로 순회하는 것이 싶다

-해싱은 순서가 없다.

-해싱에서는 초기에 얼마나 공간을 할당해야하는지가 불명확하다

-해싱은 최악의 시간복잡도가 아주 나쁘다(모든 값이 하나의 버킨으로 집중되는 경우 O(n))

14.8 해싱의 응용 분야

-방대한 양의 데이터에 액세스해야하는 상황

-신속하게 정보검색 가능

-데이터베이스 인덱싱

-컴파일러에서 심볼 테이블 구현할 때

-인터넷 검색엔진