Technical FEATURE
C언어와 알고리즘
해싱(Hashing)
필자의 연재물 "C언어와 알고리즘"은 C언어를 체계적으로 학습한 후 자료구조와 알고리즘을 C언어로 이해 및 응용하도록 도와주는 내용으로 구성한다. C언어는 임베디드는 물론 많은 정보통신 분야에서 프로그래밍 언어로 사용하고 있다. 또한, 자료구조와 알고리즘은 컴퓨터 프로그래밍의 기반을 이루는 초석이다. 오늘날 많은 공학적 응용제품들은 자연과학(수학, 화학, 물리)의 토대 위에서 만들어졌다. 컴퓨터 응용 프로그램들 또한 자료구조와 알고리즘 기반에서 코딩 되었으며, C언어는 자료구조와 알고리즘을 구현하는데 유용한 컴퓨터 프로그래밍 언어의 선구자이다. 필자는 오랫동안 자료구조와 알고리즘을 학습한 내용을 C언어로 체계적으로 실습하여 그 결과를 구체적으로 확인한 내용들을 정리해왔다. 이것을 토대로 "C언어와 알고리즘" 연재물을 집필하고 있고 여기에 필자의 많은 노력이 담겨 있다. 독자 여러분들의 많은 관심과 격려 있기를 바란다.
글 정재준 / rgbi3307@nate.com / 커널연구회(www.kernel.bz)
연재 차례
1. C언어 소개
2. 형태, 연산자, 표현
3. 제어 흐름
4. 함수와 프로그램 구조
5. 포인터와 배열
6. 구조체
7. 알고리즘 소개
8. 소팅을 통한 알고리즘 분석
9. 스택(Stack) 실습
10. 큐(Queue) 실습
11. 리스트(List) 실습
12. 트리(Tree) 실습
13. 해싱(Hash) 실습
14. 알고리즘 설계 및 분석기법
15. 진보된 알고리즘 소개
정재준
필자는 학창시절 마이크로프로세서 제어 기술을 배웠으며 리눅스 커널에 많은 관심을 가지고 있다. 10년 이상 쌓아온 IT관련 개발 경험을 바탕으로 "오라클실무활용SQL튜닝(혜지원)" 책을 집필하고, 월간임베디드월드 잡지에 다수의 기고글을 연재하였다.
최근에는 "맞춤형 문장 자동 번역 시스템 및 이를 위한 데이터베이스 구축방법 (The System for the customized automatic sentence translation and database construction method)" 이라는 프로그램을 개발하여 특허청에 특허출원 하였다. 필자는 컴퓨터구조와 자료구조 및 알고리즘 효율성 연구를 바탕으로 기술서적 집필에 노력하고 있으며, 온라인 상에서 커널연구회(http://www.kernel.bz/)를 운영하며 연구개발, 교육, 관련기술 공유 등을 하고 있다.
개요
많은 애플리케이션들은 처리대상 데이터들을 삽입, 검색, 삭제하기 위해서 동적인 집합을 필요로 한다. 예를 들면, 컴퓨터 언어를 처리하는 컴파일러는 기호 테이블(Symbol Table)이라는 것을 관리하는데, 이곳의 요소들은 특정 문자열들을 식별 키로 하여 처리된다.
해시 테이블은 사전 입출력 동작(삽입, 검색, 삭제)을 효율적으로 하는 데이터 구조체이다. 처리 대상 데이터의 수가 n개일때, Linked List는 최악의 경우 O(n) 만큼의 처리시간이 소요되는 반면, 해시 테이블에서는 O(1) 만큼의 시간으로 처리될 수 있다.
해시 테이블은 일반적인 배열 형태로서 순번이 부여된 배열 요소에 직접 접근하는 방식(Directly Addressing)으로 O(1) 시간에 동작한다. 배열은 구성 요소마다 순번(위치 인덱스)을 가지고 있으므로 특정 키의 위치를 인덱스 연산하여 직접 접근할 수 있다. 인덱스 연산은 보통 키 값을 통해서 계산한다.
해시 함수(Hash Function)
해시 테이블 알고리즘의 핵심은 데이터 요소들을 배열형태로 저장한 해시 테이블이다. 데이터 아이템의 키로부터 계산한 인덱스를 사용하여 배열 요소의 위치를 결정한다. 이러한 인덱스는 해시 함수를 통해서 산출된다. 해시 함수 hash는 다음과 같이 정의한다.
index = hash (key, arrayLength)
위의 해시함수 hash는 key와 arrayLength를 매개변수로 전달받아서 index를 산출한다. 여기서 key는 데이터 아이템 값이고, arrayLength는 해시 테이블의 배열 길이이다. index는 해시 테이블의 배열 요소를 찾아가기 위한 인덱스(해시 값)가 된다.
해시 함수는 해시 테이블 알고리즘의 전체 성능에 많은 영향을 주므로 해시 함수를 잘 작성하는 것은 아주 중요하다. 해시 함수의 가장 기본은 해시 배열 인덱스 값(해시 값)이 균등한 분포로 산출되어야 한다는 것이다. 한쪽으로 몰려서 해시 값이 산출되면 충돌 문제를 해결하기 위한 비용이 증가한다. 균등한 분포의 해시 값 산출은 다소 어려운 문제이나 여러 가지 방법들이 도입되고 있다. 해시 값은 해시 테이블의 크기 범위 내에서 균등하게 산출되어야 한다. 이것을 위해서 2의 누승 형태나 소수(prime number)를 활용하기도 한다. 또한, 암호화 기법을 동원하기도 하고 나머지 연산 및 비트 마스킹 등을 한다.
위의 그림은 사람 이름과 전화번호를 연결하는 해시함수를 설명하는 예제이다. 위에서 buckets으로 표현한 것이 해시 테이블이며 이것의 크기는 16이다. 위에서 해시 함수 hash는 다음과 같이 해시 값(index)이 산출된다.
index = hash (key, arrayLength)
02 = hash ("John Smith", 16)
01 = hash ("Lisa Smith", 16)
14 = hash ("Sandra Dee", 16)
아래 C언어 코드는 해시 함수를 실제로 작성하여 해시 값을 산출하는 것이다. 해시 함수는 다음과 같이 작성했다.
//hash 함수: 문자열 s를 위한 해시 값 산출
unsigned int hash (char *s, int length)
{
unsigned hashval;
for (hashval = 0; *s != '' ''; s++) //문자열 s의 길이만큼 반복
hashval = *s + 31 * hashval; //문자 *s에 의존하는 난수적인(random) 값
return hashval % length; //length 이내의 값(0 <= 반환값 < length)
}
hash ("John Smith", 16) 라고 호출하면, "John Smith"의 문자열 길이만큼 for 루프가 돌면서 각각의 문자 아스키 값이 다음과 같이 계산된다.
hashval = 'J' + 31 * 0 = 74 + 0 = 74
hashval = 'o' + 31 * 74 = 111 + 2294 = 2405
hashval = 'h' + 31 * 2405 = 104 + 74555 = 74659
hashval = 'n' + 31 * 74659 = 110 + 2314429 = 2314539
hashval = ' ' + 31 * 2314539 = 32 + 71750709 = 71750741
hashval = 'S' + 31 * 71750741 = 83 + 2224272971 = 2224273054
이하 생략..
따라서 최종적으로 계산되는 해시 값은 hashval을 length로 나눈 나머지 값이 된다.
(실습 소스) hash_function1.c
/*
author: Jung,JaeJoon(rgbi3307@nate.com, http:// www.kernel.bz/)
comments: 해시함수를사용하여해시 값산출
*/
#include
#include
//hash 함수: 문자열s를위한해시 값산출
unsigned int hash (char *s, int length)
{
unsigned hashval;
for (hashval = 0; *s != '' ''; s++) //문자열s의길이만큼반복
hashval = *s + 31 * hashval; //문자*s에의존하는난수적인(random) 값
return hashval % length; //length 이내의값(0 <= 반환값< length)
}
int main (void)
{
int index;
index = hash ("John Smith", 16);
printf ("John Smith = %dn", index); //해시 값출력
index = hash ("Lisa Smith", 16);
printf ("Lisa Smith = %dn", index); //해시 값출력
index = hash ("Sandra Dee", 16);
printf ("Sandra Dee = %dn", index); //해시 값출력
return 0;
}
(실행 결과) hash_function1.c
John Smith = 14
Lisa Smith = 14
Sandra Dee = 7
-
결과값을 확인해 보면, "John Smith"와 "Lisa Smith"는 동일한 해시 값인 14로 충돌한 값이 산출 되었다. 그래서 해시 함수를 다음과 같이 수정하여 결과값을 확인해 보자.
//hash 함수: 문자열 s를 위한 해시 값 산출
unsigned int hash (char *s, int length)
{
unsigned hashval;
for (hashval = 0; *s != '' ''; s++) //문자열 s의 길이만큼 반복
hashval += *s;
return hashval % length; //length 이내의 값(0 <= 반환값 < length)
}
hash ("John Smith", 16) 라고 호출하면, "John Smith"의 문자열 길이만큼 for 루프가 돌면서 각각의 문자 아스키 값이 다음과 같이 계산된다.
hashval = 'J' = 74
hashval = 74 + 'o' = 74 + 111 = 185
hashval = 185 + 'h' = 185 + 104 = 289
hashval = 289 + 'n' = 289 + 110 = 399
hashval = 399 + ' ' = 399 + 32 = 431
hashval = 431 + 'S' = 431 + 83 = 514
hashval = 514 + 'm' = 514 + 109 = 623
hashval = 623 + 'i' = 623 + 105 = 728
hashval = 728 + 't' = 728 + 116 = 844
hashval = 844 + 'h' = 844 + 104 = 948
따라서 최종적인 해시 값 hashval = 948 % 16 = 4가 된다.
(실습 소스) hash_function2.c
/*
author: Jung,JaeJoon(rgbi3307@nate.com, http://www.kernel.bz/)
comments: 해시함수를사용하여해시값산출
*/
#include
#include
//hash 함수: 문자열s를위한해시 값산출
unsigned int hash (char *s, int length)
{
unsigned hashval;
for (hashval = 0; *s != '' ''; s++) //문자열s의길이만큼반복
//hashval = *s + 31 * hashval; //문자*s에의존하는난수적인(random) 값
hashval += *s;
return hashval % length; //length 이내의값(0 <= 반환값< length)
}
int main (void)
{
int index;
index = hash ("John Smith", 16);
printf ("John Smith = %dn", index); //해시값출력
index = hash ("Lisa Smith", 16);
printf ("Lisa Smith = %dn", index); //해시값출력
index = hash ("Sandra Dee", 16);
printf ("Sandra Dee = %dn", index); //해시값출력
return 0;
}
-
(실행 결과) hash_function1.c
John Smith = 4
Lisa Smith = 14
Sandra Dee = 7
-
결과값을 확인해 보면 해시 값의 충돌 없이 모두 다르게 산출되었음을 확인할 수 있다.
해시 값 충돌(Collision) 해결방식
만약, 키(위에서 사람 성명)들의 수가 해시 테이블의 크기보다 많으면 해시 값 충돌이 발생한다. 아래의 그림은 해시 값 충돌을 chaining으로 해결하는 과정을 보여주고 있다.
"John Smith"와 "Sandra Dee"는 동일한 해시 값인 152로 산출되었으므로 해시 값 충돌이 발생했다.
152 = hash ("John Smith", 16)
152 = hash ("Sandra Dee", 16)
이것을 해결하기 위해서, 해시 값 152가 가리키는 배열 요소를 Linked List로 연결(chaining)한다. 그림2를 보면 "John Smith"와 "Sandra Dee"는 Linked List 형태로 연결되어 있다. 이렇게 하여 해시 값 충돌이 발생한 위치에서 Linked List 탐색을 수행하여 해시 값 충돌 문제를 해결한다.
아래의 소스는 해시 값 충돌을 해결하는 해시 알고리즘을 실습해 볼 수 있는 C언어 코드이다.
(실습 소스) hash.c
/*
author: Jung,JaeJoon(rgbi3307@nate.com, http://www .kernel.bz/)
comments: hash 알고리즘
*/
#include
#include
#define HASHSIZE 256
//구조체선언
struct nlist {
struct nlist *next; //연결구조체(리스트)
char *name; //key
char *phone;
};
//구조체테이블정의(해시테이블)
static struct nlist *hashtab [HASHSIZE];
//hash 함수: 문자열s를위한해시 값산출
unsigned hash (char *s)
{
unsigned hashval;
for (hashval = 0; *s != '' ''; s++) //문자열s의길이만큼반복
hashval = *s + 31 * hashval; //문자*s에의존하는난수적인(random) 값
return hashval % HASHSIZE; //HASHSIZE 이내의값(0 <= 반환값< HASHSIZE)
}
//해시함수를통하여해시테이블의요소에접근후
//연결된구조체리스트를따라가며반복탐색
struct nlist* lookup (char *s)
{
struct nlist *np;
for (np = hashtab[hash(s)]; np != NULL; np = np->next)
if (strcmp(s, np->name) == 0)
return np; //found (찾은위치포인터)
return NULL; //not found
}
//문자열s를메모리에할당한포인터반환
char *str_mcopy (char *s)
{
char *p;
p = (char *) malloc(strlen(s)+1); //+1 for '' ''
if (p != NULL)
strcpy (p, s);
return p;
}
//해시테이블에구조체할당(저장)
struct nlist* install (char *name, char *phone)
{
struct nlist *np;
unsigned hashval;
if ((np = lookup (name)) == NULL) { //not found (새롭게할당)
np = (struct nlist *) malloc(sizeof(*np));
if (np == NULL || (np->name = str_mcopy (name)) == NULL)
return NULL;
hashval = hash (name);
np->next = hashtab[hashval]; //현재해시값에있는구조체는다음(뒤)으로연결
hashtab[hashval] = np;
} else //이미존재하면
free ((void *) np->phone); //phone 해제
if ((np->phone = str_mcopy (phone)) == NULL) //phone 다시할당
return NULL;
return np;
}
int main ()
{
char *name[] = {"John Smith", "Lisa Smith", "Sam Doe", "Sandra Dee", "Ted Baker", "JaeJoon Jung", "James Dean"};
char *phone[] = {"521-1234", "521-8976", "521-5030", "521-9655", "418-4165", "520-3307", "425-1020"};
int i, n = sizeof(name) / sizeof(name[0]);
struct nlist *head, *ptr;
//연결리스트에저장
for (i = 0; i < n; i++) {
printf ("%d: %sn", hash (name[i]), name[i]);
//구조체에할당
install (name[i], phone[i]);
}
//해시테이블에연결된리스트출력
printf ("nHash Table List n");
for (i = 0; i < HASHSIZE; i++) {
head = hashtab [i];
for (ptr = head; ptr != NULL; ptr = ptr->next) {
printf("%d: %s, %sn", i, ptr->name, ptr->phone);
}
}
printf ("nHash Table Search n");
ptr = lookup ("JaeJoon Jung") ;
printf("found: %s, %sn", ptr->name, ptr->phone);
printf ("nPress any key to end...");
getchar();
return 0;
}
(실행 결과) hash .c
174: John Smith
46: Lisa Smith
57: Sam Doe
23: Sandra Dee
44: Ted Baker
210: JaeJoon Jung
10: James Dean
Hash Table List
10: James Dean, 425-1020
23: Sandra Dee, 521-9655
44: Ted Baker, 418-4165
46: Lisa Smith, 521-8976
57: Sam Doe, 521-5030
174: John Smith, 521-1234
210: JaeJoon Jung, 520-3307
Hash Table Search
found: JaeJoon Jung, 520-3307
Press any key to end...
-
맺음말
해싱은 해시 테이블을 사용하여 사전 입출력 동작(삽입, 검색, 삭제)을 효율적으로 하는 알고리즘이다. 해싱은 O(1)의 시간으로 해시 테이블에 직접적으로 접근하며 이때 접근위치에 해당하는 인덱스 값이 해시 값이고 이것은 해시 함수를 통하여 산출한다. 따라서 해싱의 전체적인 효율성은 해시 함수에 의해서 많은 영향을 받는다. 해시 함수를 작성하는 방법은 입력되는 키(key)값의 특성에 따라서 여러 가지가 있을 수 있으며, 아래와 같은 형태로 정의된다.
index = hash (key, arrayLength)
여기서 index에 해당하는 값이 해시 값이며, 이 값은 해시 크기(arrayLength)의 범위 내에서 균등하게 분포되는 값으로 산출되어야 해싱의 효율이 좋아진다. key의 수가 해시 크기(arrayLength)보다 많으면 해시 값 충돌이 발생하는데, 이것을 해결하기 위해서 해시 테이블 내에 Linked List을 추가하여 연결(chaining)하는 방식으로 해시 값 충돌 문제를 해결한다.
회원가입 후 이용바랍니다.
개의 댓글
댓글 정렬
BEST댓글
BEST 댓글
답글과 추천수를 합산하여 자동으로 노출됩니다.
댓글삭제
삭제한 댓글은 다시 복구할 수 없습니다.
그래도 삭제하시겠습니까?
그래도 삭제하시겠습니까?
댓글수정
댓글 수정은 작성 후 1분내에만 가능합니다.
내 댓글 모음