Chinaunix首页 | 论坛 | 博客
  • 博客访问: 231978
  • 博文数量: 37
  • 博客积分: 933
  • 博客等级: 军士长
  • 技术积分: 511
  • 用 户 组: 普通用户
  • 注册时间: 2011-03-16 10:15
文章分类
文章存档

2012年(1)

2011年(36)

分类: LINUX

2011-04-27 23:21:50

对于hash表最重要的评价标准就是这个hash函数的选择是否能够达到关键字的平均存在,这样引起的冲突最小。查找时间最优化。
我们看一下内核的hash函数
unsigned long hash_long(unsigned long val,unsigned int bits)
{
        unsigned long hash = val * 0x9e370001UL;
        return hash >> (32 - bits);
}
为什么这样选择 可以看看ULK3rd的相关章节。
 
那么是否这样的函数可以达到关键字的平均存放呢?
我们可以实验一下:
  1. #include
    #include
    unsigned long hash_long(unsigned long val,unsigned int bits)
  2. {
  3.         unsigned long hash = val * 0x9e370001UL;
  4.         return hash >> (32 - bits);
  5. }
  6. int main(int argc,char*argv[])
  7. {
  8.         int i,j = atoi(argv[1]);
            printf("%d\n",j);
            for(i = 0;i <=32767;i++){
  9.                 if(hash_long(i,11) == j)
  10.                         printf("pid--->index:%d--->%d\n",i,hash_long(i,11));
  11.                 }
  12. }
函数的主要功能就是将0-32767号pid转化为hash的索引
  1. #!/bin/bash
  2. declare -i i
  3. i=0
  4. for((i=0;i<2047;i++ ))
  5. do
  6.         ./test $i | wc -l |tr '\n' ' '
  7.         i=i+1
  8. 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 ....堪称完美。

阅读(2696) | 评论(0) | 转发(3) |
给主人留下些什么吧!~~