hash 기본 구현.

from Study/자료구조 2007/11/27 19:19 view 27973
해쉬 구조를 알기 위해선 아래 문서를 읽어 보고...c로 해쉬를 구성해보자.
http://lxr.linux.no/source/include/linux/hash.h


1. 해쉬 함수는 여러가지 알고리즘이 있으나 커널에서는 간단하면서도 우수한 folding exclusive 방식을 사용.

#define PIDHASH_SZ  16
#define
pid_hashfn(x)   ((((x) >> 8) ^ (x)) & (PIDHASH_SZ - 1))

pid_hashfn(777)

( ( 777 >> 8 ) ^ 777 ) & ( 16 - 1 )

777                                           => 1100001001
777 >> 8                                   => 0000000011
( 777 >> 8 ) ^ 777                      => 1100001010
16 - 1                                       => 0000001111
( ( 777 >> 8 ) ^ 777 ) & ( 16 - 1 )  => 0000001010

2. 해쉬는 탐색을 위한 자료구조라고도 할 수 있다. 자료를 효율적으로 분산하여 저장할 수 있게 된다.
사용자 삽입 이미지
사용자 삽입 이미지


전체 소스~

more..

Trackback Address :: 이 글에는 트랙백을 보낼 수 없습니다