9.1 해싱의 정의 및 필요성 9.2 정적 해싱(Static Hashing) 9.3 동적 해싱

9.1해싱의 정의 및 필요성 해싱의 정의 Key-to-address 데이터의 신속한 탐색을 위해 데이터를 해시테이블이라는 배열에 저장하고, 데이터의 키값을 주면 이를 적절한 해시 함수를 통하여 테이블의 주소로 변환하여 원하는 데이터를 찾아내는 방법 Key-to-address 특정 규칙에 따라 주어진 키 값을 주소로 변환하여 해시 테이블이라는 기억공간에 키의 레코드를 저장한다. 또한 해시 함수를 이용하여 필요한 레코드의 주소를 산출함으로서 검색작업을 수행한다

해싱함수 키(key) 수로변환 홈주소 기본 용어 해시표 : 레코드를 1개 이상 저장할 수 있는 버켓(bucket)들로 구성이 된 기억공간 해싱함수 : 해시표 내의 버켓 주소를 계산하여 일정한 규칙을 말한다 홈주소 : 해싱 함수에 의해 계산된 주소이다 버켓 : 홈주소를 갖는 기억 공간, 즉 어떤 키가 저장될 기억 공간을 말한다 동거자(synonym) : 충돌 현상이 발생되는 레코드들의 집합으로 같은 홈 주소를 갖는 레코드들의 집합을 말한다 충돌(collision or clash) : 해싱 함수에 의해 같은 홈 주소를 갖게 되는 현상

해싱 키 값의 비교를 통하여 탐색하는 것보다 빠르게 주소를 직접 얻는 것 키를 직접 주소로 변환하여 레코드를 탐색하는 해싱은 레코드의 수가 증가해도 탐색시간에는 큰 영향을 주지 않는다. 만일 충돌이 발생하지 않는다면 한번에 레코드를 탐색할 수 있다.

9.1.2 해싱의 장단점 (1)장점 (2)단점 레코드를 찾기 위하여 키 값을 모두 비교할 필요 없다. 킷 값을 직접 주소로 사용하는 경우보다 기억장소의 낭비를 줄일 수 있다. 레코드가 저장되어 있는 주소를 직접 계산에 의해 얻을 수 있으므로 탐색속도가 빠르다 오버플로우 또는 충돌이 발생하지 않으면 원하는 레코드에 한번에 접근할 수 있다 (2)단점 모든 키 값을 숫자(정수형)로 변환해야 한다. 키의 변환을 통하여 생성되는 주소가 주소공간에 적절히 분포될 수 있도록 하는 해시 함수를 구하는 문제가 존재한다 충돌이나 오버플로우가 발생했을 때 이를 해결하는 문제가 존재한다. 해시테이블을 위한 기억장소의 할당을 위한 버킷의 개수와 크기를 적절히 결정해 야 한다

해시 테이블 * 해시 함수에 의해 산출된 주소 값의 위치에 각 레코드를 기억 시킨 테이블 * 레코드를 한 개 이상 보관할 수 있는 버킷들로 구성된 기억 장소 * 버킷(bucket)들로 구성되며, 각각의 버킷은 슬롯(slot)으로 구성 * 하나의 버킷에 여러 개의 슬롯을 둠으로써 서로 다른 두개의 키 값이 해시 함수에 의해 동일한 주소로 변환되는 경우 두 키 값이 같은 버킷에 저장되도록 할 수 있다. 슬롯 0 1 m-1 버켓 1 … n-1 키1 키2 … 키m

* 버킷의 크기 : 일반적으로 한번 접근으로 탐색할 수 있는 레코드의 수 * 버킷의 크기가 증가하면 오버플로우의 발생 확률은 감소 * 한 버킷에서 레코드 탐색시간이 길어지고 특정 버킷에 동거자가 편중되면 다른 버킷의 낭비를 초래할 수 있다 * 버킷의 크기를 크게 하려면 동거자가 편중되지 않도록 해시 함수를 적절히 선택 * 해시테이블이 점차 채워지면 충돌이 발생할 가능성이 높아진다. * 해시테이블의 채워진 정도를 측정하는 적재밀도는 해시테이블에 채워진 레코드의수 적재밀도(적재율)= 버킷의 수 * 슬롯의 수

(1)중간 제곱(mid - square) 함수 해시함수(hash function) 입력된 키 값을 해시 테이블의 주소로 변환시켜주는 함수 해시 함수의 선택에 따라 레코드가 특정 버킷에 편중되지 않고 주소 공간에 균등하게 사상될 수 있도록 한다. (1)중간 제곱(mid - square) 함수 키 값을 제곱한 후 중간에 정해진 자리 수 만큼을 취해서 해시 테이블의 버킷 주소로 만드는 방법 키 값을 제곱한 결과 값의 중간의 수들은 키 값의 모든 자리들로부터 영향을 받으므로 버킷 주소가 고르게 분산될 가능성이 높다 해시 함수 : h(k) = k2 (예) 키 값 : 1234567 h(k) = (1234567)2 = 1524155677489  556 * 0.5 = 278 제곱한 수의 중간 세 자리 수 556을 취한다(주소 공간 : 500) 계산된 값이 주소 공간을 벗어나므로 조정 상수인 0.5를 곱한다. 그 값 278이라는 버킷의 주소를 계산

1 1 1 Ex)검색키가 5비트로 구성되어 있고, 버킷 주소도 5비트로 구성된 해시테이블에서 중간제곱함수를 이용한 해싱의 예 1 중간 5 비트를 버킷 주소로 취함 계산) 10110(2) = 22 22 * 22 = 484 484 = 111100100(2) 1

(2)나누기(division-remainder)함수 * 키 값을 테이블 크기로 나누어서 그 나머지를 버킷 주소로 변환하는 방법 H(k) = k mod m H(k) : 홈 주소 k : 키값 m : 소수 mod : modulo연산자 여기서 m은 버킷의 수에서 가장 가까운 소수이다 Ex) 5000개의 버킷을 갖는 주소 공간 일 경우 키 값이 1234567. 1234567 mod 5003 = 3495 나머지 연산을 이용하여 키 값 1234567의 나머지 : 3495 젯 수 : 5003 (버킷의 수 보다 크고 가장 가까운 소수) 해시 함수로 계산된 3495 : 주소 공간의 버킷 주소

(3) Folding 함수 키 값을 버킷 주소 크기만큼의 부분으로 분할한 후, 분할 한 것을 더하거나 연산하여 그 결과 주소의 크기를 벗어나는 수는 버리고 택하여 버킷의 주소를 만드는 방법 ① 이동 중첩법(shift folding) : 주어진 키를 몇 개의 동일한 부분으로 나누고 각 부분의 오른쪽 끝을 맞추어 더한 값을 홈 주소로 하는 방법

1 2 3 3 1 2 1 6 7 4 1 2 3 (예) 다음 주어진 키 값들을 3자리로 균등분할, 오른쪽 끝자리 수는 일치시킨다 4 1 2 3 3 1 2 1 4 1 2 3 1 2 3 3 1 계산결과는 1067 자리수를 벗어나는 1은 버리고 067로 버킷의 주소로 쓰인다 2 1 6 7 4 1 2 + 3

② 경계 중첩법 : 나누어진 부분들 간에 접촉될 때 하나 건너 부분의 값을 역으로 하여 더한 값을 홈 주소로 하는 방식 ② 경계 중첩법 : 나누어진 부분들 간에 접촉될 때 하나 건너 부분의 값을 역으로 하여 더한 값을 홈 주소로 하는 방식 1 2 3 3 1 2 1 4 1 2 3 1 2 3 1 3 2 1 2 1 4 671을 버킷의 주소로 취한다. 6 7 1 + 3

(4)기수(radix)변환법 주어진 키 값을 다른 진법의 수로 판단하고 , 이를 진법 변환을 통하여 버켓의 주소를 계산하는 방식 Ex) 크기가 1000인 해시테이블에 키 값이 23864(10)인 레코드를 저장하고자 할 때 23864(16) 145508(10) 해시 테이블의 크기가 1000이므로 하위3자리 수만을 선택하여 버킷의 주소로 사용 계산 23864(16) = 2*164 + 3*163 + 8*162 + 6*16 + 4* 160 = 131072 + 12288 + 2048 + 96 + 4 = 145508(10)

(5) 숫자 분석법(Digit-analysis) 모든 키를 분석해서 불 필요한 부분이나 중복되는 부분을 제거하여 홈 주소를 결정하는 방식. 이 방법은 모든 키들이 이미 알려진 경우에만 사용 새로운 레코드가 삽입되어 키의 분포 상태가 변하면 재분석 그러므로 삽입과 제거가 빈번히 요구되는 경우에는 비경제적이며, 비효율적.

(예) 해시 테이블의 크기가 1000이라 가정한다. 따라서 해시 테이블의 버킷 주소는 3자리로 변환 키 값 주 소 041 – 735 – 2316 041 – 736 – 3518 041 – 736 – 6435 041 – 735 – 2719 041 – 735 – 3113 041 – 735 – 1221 2 3 6 3 5 8 6 4 5 2 7 9 3 1 3 1 2 1

해싱의 문제점 * 충돌이 발생할 수 있다. : 해싱을 하는 경우 서로 다른 두 개 이상의 키 값들이 해시 함수에 의해 동일한 주소로 변환되는 경우 * 충돌의 발생이 빈번하면 발생 시간이 길어지는 등 성능이 저하되므로 해시 함수의 수정이나 해시 테이블의 크기가 적절히 조절되어야 한다. * 일반적으로 충돌이 발생할 경우 버킷이 여러 슬롯으로 구성되어 있다면 다른 슬롯으로 저장하면 된다. 그러나 모든 슬롯이 채워지면 오버플로우가 발생한다.

오버 플로우를 해결하는 방법들 (1)개방 주소법 생선된 버킷 주소에서 충돌이 발생하면 생성된 버킷의 주소로부터 비어있는 버킷이 발견될 때까지 찾는다. 만일 해시 테이블의 끝까지 빈 버킷을 찾지 못한다면 테이블의 처음부터 빈 버킷을 찾아 저장한다

① 선형 탐색법(linear probing) 충돌이 발생했을 경우 다음 버킷부터 차례로 빈 버킷을 찾음 간단하기는 하나 집중 현상 발생(검색시간이 늘어나 성능 저하) 집중 현상 : 키 값이 특정 버킷을 중심으로 편중되어 저장되는 현상 키 ki의 해시 테이블 주소가 h(ki)라 할 때 충돌이 발생 다음 버킷의 주소인 h(ki) + 1번지에 레코드 입력 만일 h(ki) + 1의 주소 버킷이 비어 있지 않으면 h(ki) + 2의 순서로 h(ki) + n의 빈 버킷을 계속 찾아 삽입

예 : 해시 함수 : h(k) = k mod 7 삽입 할 키 값 : 16, 38, 45, 33, 32 * 16 입력 : h(16) = 16 mod 7 = 2 2번 주소에 삽입 * 38 입력 : h(38) = 38 mod 7 = 3 3번 주소에 삽입 1 2 3 4 5 6 7 16 38 * 45 입력 : h(45) = 45 mod 7 = 3 3 버킷은 이미 38이 있기 때문에 (45 mod 7) +1로 비어있는 버킷을 찾아 45를 삽입 4번 주소에 입력 1 2 3 4 5 6 7 16 38 45

* 33 입력 : h(33) = 33 mod 7 = 5 5번 주소에 삽입 1 2 3 4 5 6 7 16 38 45 33 * 32 입력 : h(32) = 32 mod 7 = 4 4 버킷에서 충돌, h(32) + 1 = 5 5 버킷에 이미 33이 삽입 되어 있음 h(32) + 2 = 6에 삽입 따라서 6번 주소에 삽입 1 2 3 4 5 6 7 16 38 45 33 32

② 2차 탐색법(quadratic probing) 선형 방법에서 발생하는 집중문제해결하기 위한 방법 특정한 수만큼 떨어진 곳을 순환적으로 뒤져서 빈 공간을 찾아 저장하는 방법 h(k) + 12, h(k) + 22등의 순으로 h(k) + n2 (n=1,2,3….) k … 키값(ki)->해시함수(h)->h(ki) k와 충돌 발생 h(ki)+12 h(ki)+22 해시 테이블

③ 재해싱 집중 문제 해결하기 위한 방법 키 값에 대하여 두 번의 해싱이 이루어지는 방법 재해싱에서는 해시테이블의 크기가 소수이어야 한다. 이는 테이블의 크기가 소수가 아닌 경우 반복 찾아가는 빈 버킷이 항상 같기 때문에 모든 버킷을 방문할 수가 없다. 첫 번째 충돌 1 2 3 4 5 6 7 8 9 10 11 12 234 321 65 233 981 189 307 231 2 2 2 2

(2) 폐쇄 주소법(closed Addressing) 또는 체인법(chaining) : 충돌이 발생하는 동의어 별로 연결 리스트에 저장하는 방법 ① 합병 체인법 (coalesced chaining) 충돌이 발생하면 빈 버킷을 찾아 삽입하고 삽입된 위치를 포인터 부분에 기억시키는 방법 특징 충돌발생시 비어있는 버킷을 찾는 작업과 연결 포인터를 수정하는 작업이 요구되어 알고리즘 복잡 검색을 할 경우 찾고자 하는 키 값의 버킷이 자신의 버킷이 아닌 다른 버킷에 저장되어 탐색이 지연 ab - bg ak … kg aq ko my nj

② 분리체인법(separate chaining). 충돌이 발생한 키 값들을 연결리스트로 처리하는 방식 … ab bg bh kg km kb xy

9.3 동적 해싱 정적해싱의 경우 해시 테이블의 삽입과 삭제가 빈번히 발생하는 응용에는 적합하지 못하다 ㅡ> 동적해싱 또는 확장성 해싱으로 처리 트라이(trie)구조 이용 동적해싱에서는 빈번한 삽입, 삭제를 위해 테이블 대신 트라이 이용 트라이는 m-원 트리 여기서 m은 차수가 m인 트리를 말하는 것으로 10진수의 경우 10이 되고 영문자의 경우 26이 된다. 10진수로 표현되는 경우 10-윈트라이가 정의되어 사용