//〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓
// [ 해 쉬 (Hash) ]
//
// 1. 해쉬
// 2. 해쉬의 전략
// 3. 해쉬 함수의 작성
//〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓
/*
//─────────────────────────────────
1. 해쉬
//─────────────────────────────────
자료수에 상관없이 상수의 검색 길이를 가진다.
내부검색(메모리)과 외부검색(디스크)을 빠른 속도로 검색해주는 알고리즘
//─────────────────────────────────
2. 해쉬의 전략
//─────────────────────────────────
1) 해쉬 용어
ex) 우체국에서 편지를 다루는 방법
- 편지 : 주소, 우편번호
우체국 --> 우편번호에 따라 통(bucket)에 정리
- key : 주소 // 데이터
hash value : 우편번호 // 실제로 저장되는 장소
hash table : 편지를 넣는 통들의 집합
bucket : 각 통들
slot : 통들에 들어가는 편지의 갯수
hash function : key(주소)를 hash value(우편번호)로 바꾸어 주는
함수
- 해쉬 검색법의 성능 좌우
key 값을 해쉬 함수에 넣어 얻어진 hash value의 위치에
레코드를 저장하는 방법
=> 이상적인 경우 단 한번의 계산으로 삽입과 삭제, 그리고
검색이 가능하다.
ex) 간단한 해쉬 함수 구현
- key : 세 글자의 문자
- hash value : 세 글자 중의 첫 글자
// 소스 작성 ------------------------------------------------
#define TABLE_SIZE 256
char hash_table[TABLE_SIZE][3]
// 해쉬 함수
int hash1(char str[])
{
int h;
h = str[0];
return h;
}
key : 저장하고자 하는 값 char str[](3개의 문자)
hash Value : 3개의 문자 첫번째 문자
hash table : hash_table --> 편지를 넣는 통들의 집합, 크기?? 256
bucket : hash_table[0].... 각 통들...
slot : 통들에 들어가는 편지의 갯수, 자료의 갯수
hash function : hash1
==> 3글자의 키는 hash_table[hash1(key)]에 저장된다.
만약)
ABC, BCA, CBA : 모두 다른 해쉬값을 갖는다... 서로 다른 곳에 저장된다.
ABC, ACD, AXY : 같은 곳에 저장된다.(충돌)
--> 이 충돌해결 방법 : 선형탐사법, 이중 해쉬법, 연결법등으로 세분화된다.
---------------------------------------------------------------
//─────────────────────────────────
3. 해쉬 함수의 작성
//─────────────────────────────────
(1) 가장 좋은 함수는?
- 평균적인 입력에 대해 해쉬값 분포를 고르게 작성...
- 특정 해쉬값이 많이 나올 경우 : 부가적인 작업이 필요해진다.
=> 따라서 해쉬 함수는 고른 분포여야 하는데 입력 자료에 따라
적절한 해쉬 함수도 다르게 된다.(그때 그때...)
ex)
ABC, ACD, AXY등의 문자가 대부분의 경우일 경우?
첫번째 문자가 아니라 2번째 문자를 hash값으로 하는 등 방법적인 부분 고려...
해쉬 함수가 사용할 수 있는 형태
나머지, 제곱, 쪼개기, 합치기
1) 가장 많이 사용하는 해쉬 함수의 형태는 나머지 연산
- % 연산자로 쉽게 할 수 있으며 속도가 빠르다.
- 키값을 수치화시킨 후에 M으로 나머지 연산을 하면 해쉬값은
0 ~ (M-1)의 분표를 갖는다.
=> M : 소수를 사용 or
20이하의 인수를 가지지 않는 수
=> M이 인수 2를 가진다면(2의 배수라면)
//답변)두곳의 버킷에 모든 수가 들어간다.
2) 그 다음 형태는 거듭 제곱
- 키값을 제곱 또는 세제곱하면 구성하는 비트의 형태가 확연히
달라지게 된다.
3) 키를 쪼개고 합치는 방법
ex) 만약 입력 자료들의 첫 글자가 한쪽에 편중되어 있다면
해쉬값 역시 편중될 우려가 있다.
-> 거듭 제곱, 쪼개어 합치기, 너머지 이용등의 방법들을 사용
int hash2(char str[])
{
int h;
h = str[0]^((str[1]*str[1] + str[2]))%TABLE_SIZE);
return h;
}
- 고른 분포
- 해쉬 테이블의 크기를 넘어서는 안된다.
- 해쉬 테이블 크기 또한 해쉬 함수의 범위에 합당하게 설정
==> 즉 상황에 따라 해쉬 함수는 다르게 된다.
*/
//〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓
// [ 해 쉬 (Hash) ]
//
// 4. 충돌의 해결 방법
// 4.1 선형 탐사법(Linear Probing)
// 4.1.1 선형 탐사법(Linear Probing) 구현
// 4.1.2 선형 탐사법의 개선
//〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓
/*
//─────────────────────────────────
4. 충돌의 해결 방법
//─────────────────────────────────
해쉬 테이블의 한곳에 여러개의 key들이 들어 갈 경우
//─────────────────────────────────
4.1 선형 탐사법(Linear Probing)
//─────────────────────────────────
정적인 해쉬 검색법 규칙
정적인 해쉬 테이블 사용 :
배열과 같이 소스 코드상 크기가 정해져 있슴.
입력자료의 수는 해쉬 테이블의 버킷을 초과 할 수 없슴
사용 시점
--> 자료의 변동이 별로 없는 경우 적합, 구현 간단
--> 자료 검색은 해쉬 함수에 의해 구해진 해쉬값으로 해쉬 테이블을 참조
--> 충돌시 가장 널리 사용하는 방법임
선형 탐사법
1) 현재 삽입하려는 키의 해쉬값에 의한 버킷이 이미 다른 레코드가
들어있다면 단순히 다음의 버킷에 새로운 레코드를 기입하는 방법
2) 만일 다음 버킷에도 다른 레코드가 들어있다면 그 다음 버킷을
찾고 하는 과정 반복
< 삽입 알고리즘 >
1. 삽입할 레코드의 해쉬값을 해쉬 함수를 이용하여 구하여 try에 저장
2. while(해쉬 테이블[try]가 비어있지 않을 동안...)
2.1 try = (try+1) % TABLE_SIZE
3. 해쉬 테이블[try]에 레코드 기입
[ex] 해쉬 함수 작성
레코드는 단순한 정수형
해쉬 테이블의 크기 10
해쉬 함수는 키값을 TABLE_SIZE로 나눈 나머지를 리턴
#define TABLE_SIZE 10
int hash_func(int key)
{
int h;
h = key % TABLE_SIZE;
return h;
}
10의 크기를 해쉬 테이블에 A C E O F P I K U 차례로 삽입
1. A(아스키 : 65)%10 = 5 => 5번 버킷에 A를 기입
2. C(아스키 : 67)%10 = 7 => 7번 버킷에 B를 기입
3. E(아스키 : 69)%10 = 9 => 9번 버킷에 E를 기입
4. O(아스키 : 79)%10 = 9 => 9번 버킷에 O를 기입 ??
5. F(아스키 : 80)%10 = 0 => 0번 버킷에 F를 기입 ??
6. P(아스키 : 90)%10 = 0 => 0번 버킷에 P를 기입 ??
7. I--> 3, K-->6, U--> 4
<검색 알고리즘>
1. 검색할 키의 해쉬값을 구하여 try에 저장
2. while(해쉬 테이블[try]가비었지 않을 동안)
해쉬 테이블[try]가 찾고자 하는 레코드이면 리턴
아니면 try = (try+1)%TABLE_SIZE
3. 여기까지 오면 찾지 못한 것이므로 실패
[ 위의 저장 예에서의 검색 ]
1. A나 C나 E를 찾는 것은 한번의 해쉬값으로 충분
2. O, F, P를 찾는 것은 선형 탐사 필요
[ 용어 ]
cluster(덩어리)
해쉬 테이블에서 연속된 공간을 차지하는 것
덩어리가 크느냐 작느냐에 따라 삽입과 검색을 위해 선형 탐사를
하는 횟수가 결정됨
Loading density(적재밀도)
전체자료수에다 전체 버킷수를 나눈 수
적재 밀도는 1보다 작다.
적재 밀도가 커질수록 큰 덩어리가 생길 확률이 높다.
ex) D까지 삽입한 상태에서 U를 삽입할 경우
최고 9번의 선형 탐사 후에야 삽입할 곳을 찾게 된다.
<삭제 알고리즘>
--> 만약 10번 상태에서 p를 삭제하여 빈 곳으로 만들면
U를 찾을 수 있을까?
U를 찾기 위해 선형 탐사를 하던 도중 P가 있던 곳이
빈 곳이 되므로 탐사를 멈추게 된다.
--> 삭제 표시와 빈 곳이라는 표시를 따로 해줄 필요 존재함
검색시 삭제된 버킷이 존재해도 계속 검색
삽입시 삭제된 버킷에 삽입 가능...
[ 선형 탐사법의 단점 ]
1. 동적 자료의 검색시 매우 취약(최초 테이블의 크기를 크게 잡아야 함)
- 적재 밀도(Loading density)가 매우 작아져 효율적이다.
2. 해쉬 테이블이 꽉 찬상태에서 존재 안하는 키를 검색시 ??
- 무한 루프
해결) 시작위치(최초 해쉬값) 기록 후 try값이 원래의 값이 되었을 경우 종료
3. 해쉬 테이블이 꽉찬 상태면 최대 N의 검색길이를 갖는다.
- 해결방법???
120% 정도 크게 잡아주는 것이 효율적...
//─────────────────────────────────
4.1.1 선형 탐사법(Linear Probing) 구현
//─────────────────────────────────
*/
// 구현 : 초기화, 삽입, 삭제, 검색 함수
//─────────────────────────────────
// 1) 빈 곳과 삭제된 곳을 표시할 상수 정의
//─────────────────────────────────
#define EMPTY -1 // 빈곳을 표시
#define DELETED -2 // 삭제된 곳을 표시
//─────────────────────────────────
// 2) 선형 탐사를 하기 위해서 해쉬 테이블 초기화
//─────────────────────────────────
// 테이블을 모드 EMPTY로 채운다.
// 인자값 : 테이블... 채워진 갯수
int HlpInit(int a[], int *np)
{
int i;
for (i=0; i < TABLE_SIZE; i++)
a[i] = EMPTY;
*np = 0;
return 1;
}
//─────────────────────────────────
// 3) 해쉬 함수 구현
//─────────────────────────────────
#define TABLE_SIZE 10
int Hash_Func(int key)
{
int h;
h = key % TABLE_SIZE;
return h;
}
//─────────────────────────────────
// 4) 해쉬 테이블에 자료 삽입
//─────────────────────────────────
// 초기의 해쉬값... try1와 try2 저장
// try2 : 해쉬 테이블이 꽉 찼을 경우 무한 루프에 빠지는 것을 방지...
// - try1 가 해쉬 테이블을 한바퀴 돌고 제자리로 돌아온 것을 확인하기 위해
// 마련한 변수
// [ 자료 삽입 장소는???]
// - EMPTY로 표시된 곳... DELETED로 표시된 곳
// 인자값 : 저장할 키, 테이블, 실제 저장 갯수
int Hlp_Insert(int key, int a[], int *np)
{
int try1, try2;
// 초기 무한 루프 방지...
try1 = try2 = HashFunc(key);
// 빈 곳이나 삭제된 곳을 찾음
while ( a[try1] != EMPTY || a[try1] != DELETED) {
try1 = (try1 + 1) % TABLE_SIZE; // 선형 탐사
if ( try1 == try2) // 꽉 차 있는 상태
return -1;
}
// 찾은 곳에 key를 수록
a[try1] = key;
// 자료수 증가
(*np)++;
// 삽입한 곳 리턴
return try1;
}
//─────────────────────────────────
// 5) 해쉬 테이블에서 자료 삭제
//─────────────────────────────────
// 자료 삭제 후에 삭제된 곳이라고 표시
int Hlp_Delete(int key, int a[], int *np)
{
int try1;
// 자료수가 0이면 리턴
if ( *np == 0 )
return -1;
// 삭제할 키를 찾음
if (( try1 = Hlp_Search(key, a, np)) < 0 )
return -1;
// 찾았을 경우
a[try1] = DELETED;
// 자료수 감소
(*np)--;
}
//─────────────────────────────────
// 6) 해쉬 테이블 검색 함수(핵심 함수)
//─────────────────────────────────
// 빈 곳을 만나면 실패를 리턴
// 키를 찾으면 그 위치를 리턴
// 빈 곳은 없지만 찾는 키도 없는 경우는 실패를 리턴
int Hlp_Search(int key, int a[], int *np)
{
int try1, try2;
try1 = try2 = Hash_Func(key);
while ( a[try1] != EMPTY ) {
// 키를 찾았으면 성공
if ( a[try1] == key )
return try1;
// 선형 검색
try1 = (try1 + 1) % TABLE_SIZE;
// 찾고자 하는 키가 없음
if ( try1 == try2 )
return -1;
}
return -1;
}
// ==> 선행 탐사법은 기본적으로 배열을 이용 => 프로그램이 쉽다.
// 해쉬 테이블을 충분히 크게 잡으면 => 검색 효율이 좋다.(자료수에 관계없이 상수 검색 길이)
// 해쉬 테이블을 작게 잡으면 => 평균 검색 길이가 길어진다.
// 적재 밀도가 높아짐 : 큰 덩어리가 생김..
//
/*
//─────────────────────────────────
4.1.2 선형 탐사법의 개선
//─────────────────────────────────
한 버킷에 들어올 값을 인접한 곳에 두기 때문에 큰 덩어리가 생길 확율이
많다.
앞의 예는 해쉬 테이블의 크기가 10이라고 가정하고,
충돌이 일어난 경우 아래와 같이 작성하여 다음 버킷을 찾음
try = (try+1) % TABLE_SIZE;
// 어떻게 하면 좋을까??
// [ 답변 ]
꼭 1을 더하라는 법은 없다.
try = (try + i) % TABLE_SIZE;
i를 적절히 선택
만약 3이라면??
==> 덩어리가 적어진다.
*/
| http://blog.naver.com/ymhooky/120007525175 |
|
|
//〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓
// [ 해 쉬 (Hash) ]
//
// 4. 충돌의 해결 방법
// 4.2 이중 해쉬법(Double Hash)
// 4.2.1 이중 해쉬법(Double Hash) 구현
//〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓
/*
//─────────────────────────────────
4. 충돌의 해결 방법
//─────────────────────────────────
해쉬 테이블의 한곳에 여러개의 key들이 들어 갈 경우
//─────────────────────────────────
4.2 이중 해쉬법(Double Hash)
//─────────────────────────────────
- 선형 탐사법보다 큰 덩어리를 만들 확률이 적다.
- 해쉬를 중복해서 사용
- 2개의 해쉬 함수 사용
- Primary Hash Function
: 최초 검색, 삽입시 사용하는 함수
- Secondary Hash Function
: 1차 검색으로 해쉬값을 찾았을 경우 이미 다른 자료가 그
버킷을 사용함 --> 충돌
또다른 함수로 새로운 버킷을 찾는다.
- 이중 해쉬의 효율은 2차 함수에 달려 있다.
=> 이중 해쉬법은 선형 탐사법의 변형이다.
사용하는 자료의 구조는 동일
삽입, 삭제, 검색 방법도 동일
다만 충돌의 문제를 어떻게 해결하느냐에 달려있다.
[ 예 ]
// 선형 에서의 충돌 방지
try = (try+1)%TABLE_SIZE;
// 이중 해쉬의 2차 함수
int hash2_func(int key)
{
// 키의 값이 128보다 작으면 3을 아니면 7을 리턴
if(key < 128)
return 3;
else
return 7; // 3과 7은 서로소
}
// 충돌 방지를 위한 문장
try = (try + hash2_func))%TABLE_SIZE; |
〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓
// [ 해 쉬 (Hash) ]
//
// 4. 충돌의 해결 방법
// 4.3 연결법(Separate chaining)
// 4.3.1 연결법(Separate chaining) 구현
//〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓
/*
//─────────────────────────────────
4. 충돌의 해결 방법
//─────────────────────────────────
해쉬 테이블의 한곳에 여러개의 key들이 들어 갈 경우
//─────────────────────────────────
4.3 연결법(Separate chaining)
//─────────────────────────────────
연결법(동적인 해쉬법)
- 동적 할당을 통하여 해쉬 테이블의 크기보다는 큰 자료를 저장할 수 있다.
- 기본적인 해쉬 테이블과 단순 연결리스트를 이용하여 동적인 자료를 빠르게 검색
- 매우 큰 자료 집합에 대해서 유용
( ex ) 양의 정수 자료 검색
해쉬 테이블의 크기 TABLE_SIZE 10
배열로 10 크기의 해쉬 테이블 생성
- 단순히 레코드를 저장하는 것이 아니라 버킷에 저장될 레코드를
가리킬 포인터를 가지고 있어야 한다.
// 노드 구성
typedef struct _node
{
int key;
struct _node *next;
}node;
-> 이 노드 구조를 TABLE_SIZE크기의 배열로 잡고
내용을 초기화(next = NULL)
-> 이후 모든 삽입과 삭제, 검색은 연결 리스트에서 순차 검색을
하던 것과 매우 유사하다.
-> 연결법은 간단히 해쉬법과 연결 리스트의 순차 검색을 혼용한 방법
ex) A C E O F P I K D U 자료 연속 삽입
< 연결법에서의 삽입 알고리즘 >
1. 키에 해당하는 해쉬값을 해쉬 함수를 이용하여 찾아서 try에 저장
2. 삽입할 레코드를 동적 저장
3. 해쉬 테이블[try]의 연결 리스트의 앞에 레코드를 끼워 넣는다.
------------
버 킷
------------
0 --> F --> p
1
2
3 --> I
4
5 --> A --> k --> U
6
7 --> C
8 --> D
9 --> E --> O
< 연결법에서의 검색 알고리즘 >
1. 찾을 키의 해쉬값을 해쉬 함수를 이용하여 구하고 try에 저장
2. 해쉬 테이블[try]에 연결된 리스트에서 순차 검색
< 연결법에서의 삭제 알고리즘 >
1. 찾을 키의 해쉬값을 해쉬 함수를 이용하여 구하고 try에 저장
2. 해쉬 테이블[try]에 연결된 리스트에서 삭제할 레코드를 검색
3. 포인터 조작으로 삭제할 레코드를 연결 리스트에서 제외
4. 삭제할 레코드를 메모리에서 해제
=> 연결법을 이용할 경우 적재 밀도 1보다 커질 수 있다.
=> 레코드 검색시 시간이 더 걸릴 수도 있다.
=> 동적인 해쉬 방법이기 때문에 융통성이 있고 많은 자료 저장 가능
//─────────────────────────────────
4.3.1 연결법(Separate chaining) 구현
//─────────────────────────────────
// 구현 : 초기화, 삽입, 삭제, 검색 함수
*/
//─────────────────────────────────
// 1) 해쉬 함수 구현
//─────────────────────────────────
#define TABLE_SIZE 10
int Hash_Func(int key)
{
int h;
h = key % TABLE_SIZE;
return h;
}
//─────────────────────────────────
// 2) 선형 탐사를 하기 위해서 해쉬 테이블 초기화
//─────────────────────────────────
// 모든 해쉬 테이블의 next를 NULL로 설정
// 인자 : 테이블, 갯수, 전체 크기
int Hsc_Int( node a[], int *np, int N)
{
// N은 전체 해쉬 테이블 크기
int i;
// NULL 로 초기화
for (i=0; i < N; i++)
a[i].next = NULL;
*np = 0;
return 1;
}
//─────────────────────────────────
// 3) 자료 삽입 함수
//─────────────────────────────────
int *Hsc_Insert(int key, node a[], int *np)
{
int try1;
node *t;
// 새로운 노드 할당
t = (node *)malloc(sizeof(node));
// 해쉬값을 찾음
try1 = HashFunc(key);
// 연결리스트의 선두에 t를 삽입
t->next = a[try1].next;
t->key = key;
a[try1].next = t;
// 자료수 증가
(*np)++;
return 1;
}
//─────────────────────────────────
// 4) 자료 삭제 함수
//─────────────────────────────────
node *HscDelete(int key, node a[], int *np)
{
// 삭제할 노드의 앞 노드를 가리킴
node *p;
// 삭제할 노드
node *t;
if ( *np > 0 ) {
// p와 t의 초기화
p = &a[Hash_Func(key)];
t = p->next;
// 삭제할 노드를 찾음
while ( t != NULL && t->key != key ) {
p = t;
t = t->next;
}
// 찾지 못하면 실패
if ( t == NULL )
return NULL;
// 연결리스트에서 t를 제외
p->next = t->next;
// t를 메모리에서 해제
free(t);
// 자료수 감소
(*np)--;
return p;
}
return NULL;
}
//─────────────────────────────────
// 5) 자료 검색 함수
//─────────────────────────────────
node *HscSearch(int key, node a[], int *np)
{
node *t;
// 연결리스트 처음
t = a[HashFunc(key)].next;
// 순차 검색
while ( t != NULL && t->key != key)
t = t->next;
// t 리턴...
// 검색을 실패했을 경우 NULL...
return t;
}
//─────────────────────────────────
// 6) 전체를 삭제하는 함수
//─────────────────────────────────
// 해쉬 테이블의 각 버킷에 연결되어 있는 연결 리스트 순회
// 하면서 메모리 삭제
int HscDeleteAll(node a[], int *np, int N)
{
node *t, *p; // p 는 임시 저장용
int i;
for ( i = 0; i < N; i++) {
// 버킷에 연결된 리스트의 선두
t = a[i].next;
while ( t != NULL ) {
// 삭제를 위해 물려둠
p = t;
// t 는 다음 노드를 가리킴
t = t->next;
// p를 삭제
free(p);
}
}
// 자료수 =0
*np = 0;
return 1;
}
}
//〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓
// [ 해 쉬 (Hash) ]
//
// 5. 해쉬 검색의 분석
//〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓
/*
//─────────────────────────────────
5. 해쉬
//─────────────────────────────────
1) 종류
정적 해쉬법 : 선형 탐사법, 이중 해쉬법
- 해쉬 테이블의 고정적 크기
동적 자료 처리에 부적절
- 큰 덩어리가 생길 확률이 연결법에 비해서 높다. (비효율적)
- 구현 처리는 간단하다.
동적 해쉬법 : 연결법
- 연결 리스트와 동적 할당 이용
고정적인 해쉬 테이블의 크기보다 큰 자료를 저장 검색 가능
- 해쉬 함수를 잘만 설정하면 큰 덩어리가 생길 확률은 거의 없어
효율적이다.
2) 성능
- 두 이론 모두 O(1)의 성능을 가진다.
즉 자료수에 관계없이 일정한 검색과 삽입과 삭제 속도를 나타낸다.
순차 검색, 이진나무검색의 실행시간이 N의 증가 함수인 것에 비하면
매우 높은 효율이다.
하지만 해쉬 테이블이 충분히 커야만 O(1)의 성능을 가진다.
3) 메모리 내부 검색 방법
- 두 이론 모두 방법이 국한되지 않는다.
대량의 자료를 검색할 경우 가장 널리 사용되는 검색방법이다.
4) 해쉬 테이블의 단점
- 만일 검색과 동시에 정렬된 리스트를 얻어야 한다면 해쉬 검색법은
재고의 대상이 된다.
*/
