해쉬 구조를 알기 위해선 아래 문서를 읽어 보고...c로 해쉬를 구성해보자.
http://lxr.linux.no/source/include/linux/hash.h
전체 소스~
http://lxr.linux.no/source/include/linux/hash.h
1. 해쉬 함수는 여러가지 알고리즘이 있으나 커널에서는 간단하면서도 우수한 folding exclusive 방식을 사용.
2. 해쉬는 탐색을 위한 자료구조라고도 할 수 있다. 자료를 효율적으로 분산하여 저장할 수 있게 된다.
#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
#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..