pidhash链表的hash函数的性能实验-zhangliangfnst-ChinaUnix博客

对于hash表最重要的评价标准就是这个hash函数的选择是否能够达到关键字的平均存在，这样引起的冲突最小。查找时间最优化。

我们看一下内核的hash函数

unsigned long hash_long(unsigned long val,unsigned int bits)
{
unsigned long hash = val * 0x9e370001UL;
return hash >> (32 - bits);
}
为什么这样选择可以看看ULK3rd的相关章节。

那么是否这样的函数可以达到关键字的平均存放呢？

我们可以实验一下：

#include
#include
unsigned long hash_long(unsigned long val,unsigned int bits)
{
unsigned long hash = val * 0x9e370001UL;
return hash >> (32 - bits);
}
int main(int argc,char*argv[])
{
        int i,j = atoi(argv[1]);
        printf("%d\n",j);
        for(i = 0;i <=32767;i++){
if(hash_long(i,11) == j)
printf("pid--->index:%d--->%d\n",i,hash_long(i,11));
}
}

函数的主要功能就是将0-32767号pid转化为hash的索引

#!/bin/bash
declare -i i
i=0
for((i=0;i<2047;i++ ))
do
./test $i | wc -l |tr '\n' ' '
i=i+1
done

结果：

19 18 17 16 16 18 18 16 16 18 18 16 16 18 18 18 16 16 18 18 16 15 18 18 17 16 17 18 18 16 16 18 18 16 16 18 18 18 15 16 18 18 16 16 18 18 17 16 17 18 18 16 16 18 18 15 16 17 18 18 16 16 18 18 16 16 18 18 16 16 17 18 18 16 16 18 19 16 16 17 18 17 16 16 18 18 16 16 18 18 16 16 17 19 18 16 16 18 18 16 16 17 18 17 16 16 18 18 16 16 19 18 16 16 16 18 18 16 16 18 18 16 16 18 18 17 16 17 18 18 16 15 18 18 16 16 17 18 18 16 16 18 18 16 16 18 18 17 15 16 18 18 16 16 18 18 16 16 17 18 18 16 16 18 18 15 16 18 18 17 16 16 18 18 16 16 18 18 16 16 17 18 17 16 16 18 19 16 16 18 18 16 16 16 18 18 16 16 18 18 16 16 17 19 17 16 16 18 18 16 16 18 18 16 16 16 18 18 16 16 19 18 16 16 17 18 17 16 16 18 18 16 16 18 18 17 16 17 18 18 16 15 18 18 16 16 18 18 17 16 16 18 18 16 16 18 18 17 15 17 18 18 16 16 18 18 16 16 18 18 18 16 16 18 18 15 16 18 18 17 16 17 18 18 16 16 18 18 16 16 18 18 17 16 16 18 19 16 16 18 18 16 16 17 18 17 16 16 18 18 16 16 18 19 17 16 16 18 18 16 16 18 18 16 16 17 18 18 16 16 19 18 16 16 18 18 17 16 16 18 18 16 16 18 18 16 16 18 18 18 16 15 18 18 16 16 18 18 17 16 17 18 18 16 16 18 18 16 15 18 18 18 16 16 18 18 16 16 18 18 17 16 17 18 18 15 16 18 18 16 16 17 18 18 16 16 18 18 16 16 18 18 16 16 17 18 19 16 16 18 18 16 16 17 18 17 16 16 18 18 16 16 18 19 16 16 17 18 18 16 16 18 18 16 16 17 18 17 16 16 19 18 16 16 18 18 16 16 16 18 18 16 16 18 18 16 16 18 18 17 16 16 18 18 16 16 18 18 16 16 17 18 18 16 16 18 18 16 15 18 18 17 16 17 18 18 16 16 18 18 16 16 17 18 18 15 16 18 18 16 16 18 18 17 16 16 18 18 16 16 18 18 15 16 17 18 18 16 16 18 18 16 16 18 18 16 16 16 18 18 16 16 18 19 16 16 17 18 17 16 16 18 18 16 16 18 18 16 16 16 19 18 16 16 18 18 16 16 17 18 17 16 16 18 18 16 16 19 18 17 16 16 18 18 16 16 18 18 16 16 18 18 17 16 16 18 18 16 15 18 18 17 16 17 18 18 16 16 18 18 16 16 18 18 17 15 16 18 18 16 16 18 18 17 16 17 18 18 16 16 18 18 15 16 18 18 18 16 16 18 18 16 16 18 18 16 16 17 18 17 16 16 18 19 16 16 18 18 17 16 16 18 18 16 16 18 18 16 16 17 19 18 16 16 18 18 16 16 18 18 17 16 16 18 18 16 16 19 18 16 16 17 18 18 16 16 18 18 16 16 18 18 17 16 17 18 18 16 15 18 18 16 16 18 18 18 16 16 18 18 16 16 18 18 17 15 17 18 18 16 16 18 18 16 16 18 18 18 16 16 18 18 15 16 18 18 17 16 17 18 18 16 16 18 18 16 16 17 18 17 16 16 18 19 16 16 18 18 16 16 17 18 18 16 16 18 18 16 16 17 19 17 16 16 18 18 16 16 18 18 16 16 16 18 18 16 16 19 18 16 16 17 18 17 16 16 18 18 16 16 18 18 16 16 17 18 18 16 15 18 18 16 16 18 18 17 16 17 18 18 16 16 18 18 16 15 17 18 18 16 16 18 18 16 16 18 18 17 16 16 18 18 15 16 18 18 16 16 17 18 18 16 16 18 18 16 16 18 18 16 16 16 18 19 16 16 18 18 16 16 17 18 17 16 16 18 18 16 16 18 19 16 16 16 18 18 16 16 18 18 16 16 17 18 17 16 16 19 18 16 16 18 18 17 16 16 18 18 16 16 18 18 16 16 18 18 17 16 15 18 18 16 16 18 18 17 16 17 18 18 16 16 18 18 16 15 18 18 17 16 16 18 18 16 16 18 18 17 16 17 18 18 15 16 18 18 16 16 18 18 18 16 16 18 18 16 16 18 18 16 16 17 18 18 16 16 18 18 16 16 18 18 17 16 16 18 18 16 16 18 19 16 16 17 18 17 16 16 18 18 16 16 18 18 17 16 16 19 18 16 16 18 18 16 16 17 18 18 16 16 18 18 16 16

嘎嘎

it's cool ....堪称完美。