pidhash链表的hash函数的性能实验

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

我们看一下内核的hash函数

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

 

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

我们可以实验一下：

#include#includeunsigned 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

[root@localhost bangzi]# cat tmp | grep 15 | wc -l
27
[root@localhost bangzi]# cat tmp | grep 16 | wc -l
431
[root@localhost bangzi]# cat tmp | grep 17 | wc -l
108
[root@localhost bangzi]# cat tmp | grep 18 | wc -l
431
[root@localhost bangzi]# cat tmp | grep 19 | wc -l
27

结果：

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 ....堪称完美。