해쉬 구조를 알기 위해선 아래 문서를 읽어 보고...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.. | less.. ]
#include <stdio.h>
#include <time.h>
#include <windows.h>
struct task_struct
{
int pid;
struct task_struct *pidhash_next;
struct task_struct **pidhash_pprev;
};
#define PIDHASH_SZ 16
#define pid_hashfn(x) ((((x) >> 8) ^ (x)) & (PIDHASH_SZ - 1))
struct task_struct *pidhash[PIDHASH_SZ];
void hash_pid(struct task_struct *p)
{
struct task_struct **htable = &pidhash[pid_hashfn(p->pid)]; if((p->pidhash_next = *htable) != NULL)
(*htable)->pidhash_pprev = &p->pidhash_next;
*htable = p;
p->pidhash_pprev = htable;
}
void unhash_pid(struct task_struct *p)
{
if(p->pidhash_next)
p->pidhash_next->pidhash_pprev = p->pidhash_pprev;
*p->pidhash_pprev = p->pidhash_next;
}
struct task_struct *find_task_by_pid(int pid)
{
struct task_struct *p, **htable = &pidhash[pid_hashfn(pid)];
for(p = *htable; p && p->pid != pid; p = p->pidhash_next)
;
return p;
}
void display()
{
int i;
struct task_struct *p;
system("cls");
for(i =0 ; i < PIDHASH_SZ; i++ )
{
printf("[%2d]", i);
for(p = pidhash[i]; p; p = p->pidhash_next)
printf("<->[%4d]", p->pid);
printf("\n");
}
}
int main()
{
int temp,i;
struct task_struct *task;
srand((unsigned int)time(0));
display();
for(i=0; i<30; i++ )
{
getchar();
while( temp = rand())
{
if( !find_task_by_pid( temp ))
break;
}
task = (struct task_struct*)malloc(sizeof(struct task_struct));
task->pid = temp;
hash_pid( task);
display();
}
}
#include <time.h>
#include <windows.h>
struct task_struct
{
int pid;
struct task_struct *pidhash_next;
struct task_struct **pidhash_pprev;
};
#define PIDHASH_SZ 16
#define pid_hashfn(x) ((((x) >> 8) ^ (x)) & (PIDHASH_SZ - 1))
struct task_struct *pidhash[PIDHASH_SZ];
void hash_pid(struct task_struct *p)
{
struct task_struct **htable = &pidhash[pid_hashfn(p->pid)]; if((p->pidhash_next = *htable) != NULL)
(*htable)->pidhash_pprev = &p->pidhash_next;
*htable = p;
p->pidhash_pprev = htable;
}
void unhash_pid(struct task_struct *p)
{
if(p->pidhash_next)
p->pidhash_next->pidhash_pprev = p->pidhash_pprev;
*p->pidhash_pprev = p->pidhash_next;
}
struct task_struct *find_task_by_pid(int pid)
{
struct task_struct *p, **htable = &pidhash[pid_hashfn(pid)];
for(p = *htable; p && p->pid != pid; p = p->pidhash_next)
;
return p;
}
void display()
{
int i;
struct task_struct *p;
system("cls");
for(i =0 ; i < PIDHASH_SZ; i++ )
{
printf("[%2d]", i);
for(p = pidhash[i]; p; p = p->pidhash_next)
printf("<->[%4d]", p->pid);
printf("\n");
}
}
int main()
{
int temp,i;
struct task_struct *task;
srand((unsigned int)time(0));
display();
for(i=0; i<30; i++ )
{
getchar();
while( temp = rand())
{
if( !find_task_by_pid( temp ))
break;
}
task = (struct task_struct*)malloc(sizeof(struct task_struct));
task->pid = temp;
hash_pid( task);
display();
}
}