추상데이터 타입(abstract data type; ADT) 로서 사전(dictionary)이라는 개념이 있다. 보통은 사전보다는 심볼 테이블(symbol table) 이라고 불리우며, 심볼 테이블은 이름(key)-속성(value)쌍의 집합으로 정의된다. 일반적으로 심볼테이블은 다음의 연산이 필요하다.
- 특정 이름이 테이블내에 존재하는지 검사
- 주어진 이름의 속성을 검색
- 주어진 이름의 속성을 변경
- 새로운 이름과 그 속성의 삽입
- 이름과 해당 속성의 삭제
- 탐색
- 삽입
- 삭제
2. 정적 해싱
정적해싱은 식별자를 해싱테이블에 저장하고 식별자의 주소 또는 위치를 결정하기 위해 해싱함수를 사용한다.
1) 용어
- 해싱테이블 : 식별자들의 저장장소
- 버켓 : 데이터들의 저장장소
- 슬롯 : 하나의 주소에 여러 데이터가 저장 가능하도록 보켓을 나눔
- 오버플로 : 가득찬 버켓에 새로운 식별자를 추가하려고 할때 발생
- 동거자(synonym) : 한 버켓에 두개 이상의 식별자를 사상시킴 (슬롯)
2) 만약, 오버플로가 없다면?
- 해싱함수 계산 시간 + 버켓 탐색시간 = 식별자 삽입/삭제/탐색 시간
3) 버켓내 식별자 탐색
- 순차 탐색 기법 이용
- O(1) 의 탐색 시간 복잡도 (식별자 개수와 무관하므로)
- 버켓의 크기가 작기 때문
2-1. mapping function(사상함수)
1) 사상함수의 조건 --> 균일 해싱 함수
- 계산이 쉽고 충돌이 적어야 한다.
- 충돌을 피하기 위해 함수가 식별자에 있는 모든 문자와 관련을 가지도록 해야 한다.
- 균일해싱함수 : f(x) = i 의 확률이 모든 버켓 i 에 대해 1/b 즉, b개의 버켓에 대해 각각의 임의의 x 가 대응될 확률은 모두 같다.
2) 중간 제곱 함수(mid-square)
- 식별자를 제곱하여 그 수의 중간에 있는 적당한 수의 비트를 버켓의 주소로 함
- 사용 비트수는 테이블의 크기에 비례함.
- r 비트 사용시 값의 범위는 2r, 테이블 크기도 2r
3) 제산함수
- 가장 많이 쓰임
- 식별자 x 를 어떤 수 M 으로 나눈 나머지 x 를 해싱 주소로 사용
- f(x) = x%M
- M 의 선택 :
- M 이 2의 거듭 제곱꼴로 하면, 10, 100, 1000 이 되어 항상 주소는 0 이 됨
- M 이 2로 나누어지면 홀, 짝으로 편중되게 된다.
- 같은 문자들의 순열로 된 변수 해싱값이 항상 3의 배수만큼 떨어지는 문제 발생 (M을 소수로 하여 해결가능)
- 20보다 작은 소수들을 약수로 가지지 않는 M 을 선택하면 충분함.
- 접지함수 연산 순서
- 식별자 x 를 나눔(마지막 부분을 제외하고 모든 부분의 길이는 같다.)
- M 이 각 부분을 더함
- x 에 대한 주소 생성
- 이동 접지
식별자 x를 x1 = 123, x2 = 203, x3 = 241, x4 = 112, x5 = 20 이라고 했을때,
예)
123
203
241
112
20
------
699 ==> 이 것이 주소
- 경계 접지
식별자의 각 부분을 종이 접듯 경계에서 겹친 후 같은 자리를 더함
이동접지의 예에서 계속)
123
203
241
112
20
을 두째, 네째 자리를 겅계로 접으면(접는다의 의미는 대칭되는 자리의 숫자끼리 자리 교환)
123
302
241
211
20
-----
897 ==> 이것이 주소
5) 오버플로 처리
- 선형 조사법 (선형 개방 조사법)
가장 가까이에 있으면서 빈 슬롯이 있는 버켓을 찾는다. (순차적)
- 원형 회전 (circular rotation)
충돌이 발생하면 빈 슬롯이 있을 때까지 반복하며 찾는다.
- 이차 조사법
- 선형조사법은 식별자가 군집되는 경향이 있고 속도가 느리다. 군집의 폐해를 피해 이차조사법을 사용
- 0 <= i <= b-1 의 범위를 i*i (제곱, 즉 이차) 씩 이동하며 선형조사를 한다.
- 체인법
* 하나의 버켓을 하나의 동가자 리스트로 만들어 불필요한 비교들을 생략함. (서로 다른 해싱값을 비교하지 않도록 함)
* f(x) 를 계산하여 나온 주소값에 있는 리스트들을 비교함.
* 리스트의 크기를 미리 알수 없으므로 리스트들 링크로 연결
* 링크를 갖는 헤더를 각 체인별로 하나씩 가진다. (연결리스트, linked list 와 유사)
이 밖에 여러개의 함수를 사용하는 재해싱, 임의 조사법도 있다.
3. 동적 해싱
DBMS (database management system) 과 같이 대용량 데이터에 접근속도가 빨라야 하며, 시간이 지날 수록 그 데이터량의 증가 또는 변화가 큰 경우에 사용되는 해싱기법이다.
이올린에 북마크하기
이올린에 추천하기'스터디이야기' 카테고리의 다른 글
| 자료구조::해싱(Hashing) (2) | 2007/10/11 |
|---|---|
| 자료구조::기본개념 (0) | 2007/10/11 |
| Data Mining (2) - WEKA (0) | 2006/12/11 |
| Data Mining (1) (0) | 2006/12/11 |
댓글을 달아 주세요
public static int javahash(String name)
{
int h=0;
int twopower = (1 <<20)-1;
for(int s=0;s<name.length();s++)
{
h= (31*h+(char)name.charAt(s))%twopower;
}
return h;
}
맞나몰라.
이거 제산함수 구현하신거 맞죠? 에러가 날듯 안날듯 긴가민가 합네다.. ㅋㅋ