해싱의 개요및 특징  출처: |
Hashing은 하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것이다. 짧은 해시 키를 사용하여 항목을 찾으면 원래의 값을 이용하여 찾는 것보다 더 빠르기 때문에, 해싱은 데이터베이스 내의 항목들을 색인하고 검색하는데 사용된다. 또한 해싱에 의해 정렬된 이름들 각각은 데이터베이스 내에서 개인들 데이터의 키가 될 수 있다. 데이터베이스 검색 수법은 일치하는 것이 먼저 발견될 때까지 각 이름들을 글자단위로 확인하기 시작해야만 한다. 그러나, 만약 이름들 각각이 해시된다면, 각 이름별로 4자리의 고유한 키를 생성하는 것이 가능해진다. 예를 들면 다음과 같다.
어떤 이름을 찾는 작업은 먼저 해시 값을 계산하고, 그 다음에 그 값을 사용하여 일치여부를 비교하는 작업으로 구성된다. 일반적으로 이렇게 하는 것은, 각 문자가 26개의 경우를 갖는 예측할 수 없는 값의 길이에서 찾는 것보다, 각각이 오직 9개의 경우를 갖는 네 자리 수에서 일치하는 것을 찾는 것이 더 빠르다. 해싱 함수란? 해싱 알고리즘을 해시 함수라고 부른다.해싱 함수(hashing function) h(k)는 어떤 키 k에 대한 테이블 주소(table address)를 계산하기 위한 방법으로, 주어진 키 값으로부터 레코드가 저장되어 있는 주소를 산출해 낼 수 있는 수식을 말한다. 해싱은 빠른 속도의 데이터 검색 외에도, 전자서명을 암호화하고 복호화하는 데에도 사용된다. 전자서명은 해시 함수를 이용하여 변환된 다음, 해시 값(이를 요약 메시지라고 부른다)과 전자서명이 별도로 전송된다. 수신자는 송신자가 사용한 해시함수와 같은 것을 사용하여, 서명으로부터 요약 메시지를 뽑아내어 그것을 이미 수신한 요약 메시지와 비교한다. 그 비교 결과는 같아야만 전자서명이 유효한 것이다. 해시 함수는 원래의 값이나 키를 색인하는데 사용되며, 그 값이 관련된 데이터가 검색될 때마다 다시 사용된다. 그러나, 해싱은 항상 한 쪽 방향으로만 연산된다. 따라서, 해시된 값을 분석함으로써 해시 함수를 추출해내는 역방향 공학은 필요가 없다. 사실, 이상적인 해시함수는 그러한 분석에 의해 추론할 수 없어야 한다. 또한, 우수한 해시 함수는 서로 다른 두 개의 입력에 대해, 동일한 해시 값을 생산해서는 안된다. 만약 그렇게 되면, 충돌이 생긴다. 충돌 위험성이 매우 적은 해시 함수라야 훌륭한 해시 함수로 평가된다. 데이터베이스 저장이나 검색에 잘 적용되는 해시 함수는 오히려 암호화나 에러검출 목적으로는 잘 듣지 않을 수도 있다. 암호화에 사용되는 잘 알려진 해시 함수들이 몇 개 있다. 이러한 것들에는 전자서명을 요약 메시지라고 불리는 더 짧은 값으로 바꾸는 데 사용되는 요약 메시지 해시 함수 MD2, MD4, MD5 등과, 더 큰 요약 메시지 (60 비트)를 만드는 표준 알고리즘인 SHA (Secure Hash Algorithm) 등이 포함된다. 해싱 함수및 용어
제산법 나머지 연산자(modulus operator : %)를 사용하여 테이블 주소를 계산하는 방법으로, 레코드 키 값을 수치 자료로 간주하여 어떤 양의 정수(대개 해시 테이블의 크기)로 나눈 나머지를 홈 주소로 결정하는 가장 간단한 해싱 함수이다.
해시 테이블의 홈 주소를 결정하는 양의 정수 I 값 잘못된 선택은 상당한 충돌을 유발할 수 있으므로 I의 선정에 신중을 기울여야 한다. 나눗셈 법에서 I의 선택은 해싱 함수의 기능에 매우 중요한 역할을 하므로 I는 보통 1과 자신의 수에 의해서만 나누어지는 소수(Prime Number)로 정한다.
제곱법 제곱법은 레코드 키 값을 제곱한 후에 결과 값의 중간 부분에 있는 몇 비트를 선택하여해시 테이블의 홈 주소로 사용하며, 심볼 테이블 응용에서 자주 사용된다. 제곱된 결과의 중간 비트는 대개 레코드의 모든 문자에 의존하므로, 레코드를 구성하는몇 개의 문자가 같을 지라도 서로 다른 레코드 키는 다른 홈 주소를 갖게 될 확률이 높다. 홈 주소를 얻기 위해 사용되는 비트 수는 테이블의 크기에 따라 달라지는데, 중간 부분의 자릿수를 n이라 하면 각 레코드 값들이 가지는 범위인 해시 테이블의 크기는 2n이 된다. (EX) 레코드 키 값 k = 35270, 해시 테이블의 크기가 10,000(중간 4비트 선택)일 때 제곱법에 의한 레코드 주소(홈 주소)는 얼마인가? (풀이)
제곱법에 의한 k의 레코드 주소(=홈 주소)= k2 = 1243972900에서 중간 4비트를 취한 9729가 된다. 숫자 분석법 레코드 키를 구성하는 수들이 모든 키들 내에서 각 자리별로 어떤 분포인지를 조사하여비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여, 레코드의 홈 주소로 사용하는 방법이다. 파일의 레코드 키 값이 이미 알려진 정적 파일(static file)인 경우에 유용하며, 삽입과 삭제가 빈번히 발생하는 경우에는 비효율적이다. (EX) 해시 테이블의 크기=1000, 홈 주소 : 0 ~999까지(3자리 필요) 레코드 키 값이 다음의 (a)와 같을 때 숫자 분석법을 이용하여 각 키들에 대한 홈 주소를 결정하시오.
폴딩법 폴딩법은 레코드의 키를 마지막 부분을 제외한 모든 부분의 길이가 동일하게 여러 부분으로 나누고, 이들 부분을 모두 더하거나 배타적 논리합(XOR)을 취하여, 해시 테이블의홈 주소로 이용하는 방법으로 두 가지 방법이 사용된다. (ㄱ) 이동 폴딩(Shift Folding) 각 부분의 값을 계산하기 위해 마지막을 제외한 모든 부분을 이동시켜 최하위 비트(LSB)가 마지막 부분의 자리와 일치하도록 우측 끝을 맞추어 더한 값을 홈 주소로하는 방법이다.
(ㄴ) 경계 폴딩(Boundary Folding) 원래의 레코드 키 값을 여러 부분으로 나눈 후, 나누어진 각 부분의 경계선을 종이 접듯이 접어 역으로 정렬한 다음 같은 자리에 위치한 수를 더한 값을 홈 주소로 하는 방법이다.
기수 변환법 기수 변환법은 어떤 진법으로 표현된 주어진 레코드 키를 다른 진법으로 간주하고 키를변환하여 홈 주소를 얻는 방법으로, 어떤 키 값이 16진법으로 표현되어 있다면 이를 10진법으로 표현된 것으로 간주하고 키 값을 변환하여 해당 레코드의 홈 주소를 구한다. 해시 테이블의 크기가 10의 멱승으로 표현되어 변환된 해당 레코드의 주소값이 테이블의크기를 초과할 때는 주소값의 최하위 자리부터 해시 테이블의 크기가 허용하는 멱승수만큼 취하여 해당 레코드의 홈 주소로 사용한다. (EX) 해시 테이블의 크기 = 10000(104) 십진수로 입력된 키 값(B2538)10을 16진수로 간주하여 그 값을 다시 10진수로 계산하는 기수 변환법을 이용하여 홈 주소를 구하시오. (풀이) (1 * 165) + (3 * 164) + (2 * 163) + (5 *162 ) + (4 * 161) + (8 * 160) 레코드의 주소값(1254728)10에서 해시 테이블이 허용하는 하위 4자리를 선택한다. 무작위 방법 무작위 방법은 난수 발생 프로그램을 이용하여 난수(random number)를 발생시켜 각 레코드 키의 홈 주소를 결정하는 방법으로, 보통 난수는 1보다 작은 양의 실수를 산출하므로, 해시 테이블의 크기인 n을 산출된 난수에 곱하여 0~(n-1)까지의 범위값으로 변환하여 사용하며, 만일 충돌이 발생하게 되면 그 다음 난수를 레코드의 홈 주소로사용한다. 오버플로우의 해결 서로 다른 레코드 키가 동일한 홈 주소를 갖는 충돌(collision) 현상이 발생했다는 것은특정 레코드의 키 값인 K의 해싱 함수값h(K)의 해시 테이블 주소에는 이미 다른 레코드 키가 보관되어 있다는 것을 의미하므로, 버켓의 크기가 1인 경우 충돌을 유발한 레코드 키 K를 저장하기 위해 다른 기억 장소를 검색해야 한다. 이와 같이 다른 기억 장소를 찾아 충돌을 유발한 레코드를 저장하는 일을 과잉 상태 처리라 한다.
선형 검색법은 충돌을 해결하는 가장 간단한 방법으로, 충돌 발생시 새로운 레코드키를 저장할 기억 공간을 찾기 위해 충돌이 일어난 그 위치에서 테이블 순으로 차례대로하나씩 검색하여 첫번째 빈 영역에 레코드 키를 저장하여 충돌을 해결하는 방법이다. 선형 검색법을 이용할 때 해쉬 테이블은 1차원 배열 형태를 가진다. 그러나 충돌을 유발한 레코드의 저장을 위한 검색 과정에서 테이블의 끝에 도달할 때까지 빈 공간이 존재하지 않으면 단순히 테이블의 제일 처음 번지로 돌아가서 다시 검색을 하면 된다. 충돌을 일으킨 레코드 키 K를 저장할 후속 주소 h1(K) = h0(K)+1이 되고, h1(K)에 새로운 레코드의 저장이 가능한지 확인하여 빈곳이면 그곳에 레코드를 저장하고, 그렇지 않으면빈 곳을 찾을 때까지 다음 후속 주소를 따라 검색을 계속한다.
선형 검색법에서 i번째 후속 주소 hi(K)는 위와 같다.
<명칭을 삽입하는 경우>
<명칭을 검색하는 경우>
2차 검색법은 선형 검색법에서 발생하는 제 1밀집(primary clustering) 문제를 제거하는 방법으로, 기대되는 충돌 함수는 이차식인 f(i)= i2이 된다. 원래의 테이블 주소로부터 다음 주소를 결정하는 거리 d가 1, 4, 9, 16, …과 같이 떨어진 영역을 차례대로 검색하여 처음으로 발견되는 빈 영역에 해당 레코드를 저장함으로써 충돌을 해결하는 방법이다.
2차 검색법에서 i번째 후속 주소 hi(K)는 위와 같다. 무작위 검색법 충돌을 유발한 레코드 키를 저장할 수 있는 가용공간을 찾을 때까지 난수 계산 프로그램을실행하여 해시 Table(hash table)의 홈 주소를 다음 후속 주소로 택하여 충돌을 해결하는 방법이다.
체인 이용법 해시 함수에 의해 같은 기억공간에 할당되어 충돌이 발생한 레코드들을 연결 리스트(Linked List)로 연결하는 방법으로 해시 테이블 자체는 포인터의 배열로 만들고, 같은버켓에 할당되는 레코드들을 체인으로 만들어 연결한다.
해시 연쇄법은 연결 리스트를 사용하므로 해시 테이블에서의 삽입이나 삭제 연산이 용이하며, 충돌의 횟수를 감소시키지는 못하지만, 다른 충돌 해결 방법에 의해 해시 테이블을 검색할 때 발생하는 소요시간을 감소시킬 수 있다. 체인 이용법의 알고리즘 <명칭을 삽입하는 경우>
<명칭을 검색하는 경우>
|
'IT' 카테고리의 다른 글
| u-IT839 전략 초점은 ‘유비쿼터스’ 조성 (0) | 2007.11.07 |
|---|---|
| 조립컴퓨터로 삽질... (0) | 2007.10.15 |
| 국내외 웹2.0 서비스 리스트 (0) | 2007.09.06 |
| ISO20000 (0) | 2007.09.05 |
| 기능점수측정(Function Point) 요약 (0) | 2007.09.05 |
국내외 웹2.0 서비스 리스트
단일 결과 값 계산
