Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1673369
  • 博文数量: 174
  • 博客积分: 5493
  • 博客等级: 上校
  • 技术积分: 5802
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-05 15:13
个人简介

炼狱,是为追逐光芒

文章分类

全部博文(174)

文章存档

2017年(1)

2016年(3)

2015年(9)

2014年(5)

2013年(23)

2012年(56)

2011年(45)

2010年(32)

分类: LINUX

2012-08-09 17:38:30

散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表

这是来自wiki的解释,为了透彻理解这个问题,我们举个简单的例子…

比如项羽要分封十八路诸侯,这十八路诸侯倒秦功劳、实力以及对项羽的忠诚度不一而足,如何分封、管制就是一个大问题。每个诸侯包括拥有兵力,封王地域等诸多信息,把这些信息全放进一个结构体,我们只要知道这个结构体地址,即可知道该王所有信息。我们声明一个有序数组king_value[n],把每个封王(结构体指针)放在king_value []中占一项,那么项王只要拥有king_value [n]这个数组,就可以快速调用天下诸侯的所有信息。

问题就出现了,假如你要查找某个诸侯的资料,必须把这个数组遍历一遍,时间复杂度是O(n),明显的n越大,找到某个封王的时间就越长,是相当低效的。

为了加速查找,我们想到一个办法,把某封王通过一个关系转换,得到一个整数(即关键码值),把该王信息保存在,以这个整数为下标的king_value[n]数组中,那么以后要查找任一个封王信息,只要把该王通过指定关系转换计算一下,就得到一个数组下标,很容易就得该王储存项,时间是固定的长度O(1)。这个转换关系就是哈希函数,这个数组就是哈希表

那么现在的问题是,如何实现这个转换关系,我们看看Linux内核的哈希函数

点击(此处)折叠或打开

  1. unsigned long hash_long(unsigned long val,unsigned int bits)
  2. {
  3.         unsigned long hash = val * 0x9e370001UL;
  4.         return hash >> (32 - bits);
  5. }
还有一个冲突问题,比如给英布用哈希函数得到整数10,就把king_value[10]就分给他了,那接着给刘季的哈希函数也得到10,怎么办呢,处理方法有开放地址法、再散列法、拉链法等。这里简单的放在11,若11已经有人占了,就给12,依次类推。

那么内核这个哈希函数是否可以达到关键字均衡存放呢,写个简单的程序来测试下内核这个哈希函数是否靠谱,

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. unsigned long hash_long(unsigned long val,unsigned int bits)
  4. {

  5.      unsigned long hash = val*0x9e370001UL;

  6.      return hash >> (32-bits);
  7. }

  8. int main(int argc, char *argv[])
  9. {
  10.      int i, j = atoi(argv[1]);

  11.      for (i = 0; i <= 32767; i++) {
  12.            if (hash_long(i, 11) == j)

  13.                 printf("pid-->%d\n", hash_long(i,11));
  14.      }
  15.      return 0;
  16. }
主要功能是把0~32767的pid值转换为hash的索引

leon@PC:~/work$ ./a.out 10 |wc -l
17

leon @PC:~/work$ ./a.out 20 |wc -l
17

leon @PC:~/work$ ./a.out 23 |wc -l
15

leon @PC:~/work$ ./a.out 231 |wc -l
17

看看下标分配到0~2047出现的分布

点击(此处)折叠或打开

  1. #!/bin/bash

  2. declare -i i

  3. i=0

  4. for((i=0;i<2047;i++))

  5. do

  6.          ./a.out $i | wc -l |tr '\n' ' '

  7. done
leon@PC:~/work$ ./pid.sh

18 17 17 17 16 15 15 15 15 17 17 17 17 15 15 15 15 16 17 17 17 17 15 15 15 14 17 17 17 17 17 15 15 15 15 17 17 17 17 16 15 15 14 15 17 17 17 17 16 15 15 15 16 17 17 17 17 16 15 14 15 16 17 17 17 17 15 15 15 15 17 17 17 17 17 15 14 15 15 17 17 17 17 16 15 15 15 15 17 17 17 17 16 14 15 15 16 17 17 17 17 16 15 15 15 16 17 17 17 17 14 15 15 15 16 17 17 17 17 15 15 15 15 17 17 17 17 15 15 15 15 15 17 17 17 18 15 15 15 15 16 17 17 17 17 15 15 15 15 16 17 17 18 16 15 15 15 15 16 17 17 17 16 15 15 15 15 17 17 18 17 16 15 15 15 15 17 17 17 17 15 15 15 15 16 17 18 17 17 15 15 15 15 16 17 17 17 16 15 15 15 15 16 18 17 17 16 15 15 15 15 17 17 17 17 16 15 15 15 15 18 17 17 17 15 15 15 15 15 17 17 17 17 15 15 15 15 17 17 17 17 16 15 15 15 14 17 17 17 17 16 15 15 15 16 17 17 17 17 16 15 15 14 16 17 17 17 17 15 15 15 15 16 17 17 17 17 15 15 14 15 17 17 17 17 17 15 15 15 15 17 17 17 17 16 15 14 15 15 17 17 17 17 16 15 15 15 16 17 17 17 17 15 14 15 15 16 17 17 17 17 15 15 15 15 17 17 17 17 17 14 15 15 15 17 17 17 17 16 15 15 15 15 17 17 17 17 15 15 15 15 16 17 17 17 18 15 15 15 15 16 17 17 17 16 15 15 15 15 17 17 17 18 16 15 15 15 15 17 17 17 17 15 15 15 15 15 17 17 18 17 15 15 15 15 16 17 17 17 17 15 15 15 15 16 17 18 17 16 15 15 15 15 16 17 17 17 16 15 15 15 15 17 18 17 17 15 15 15 15 15 17 17 17 17 15 15 15 15 16 18 17 17 17 15 15 15 15 16 17 17 17 16 15 15 15 15 17 17 17 17 16 15 15 15 15 17 17 17 17 16 15 15 15 16 17 17 17 17 15 15 15 14 17 17 17 17 17 15 15 15 15 17 17 17 17 16 15 15 14 15 17 17 17 17 16 15 15 15 16 17 17 17 17 16 15 14 15 16 17 17 17 17 15 15 15 15 16 17 17 17 17 15 14 15 15 17 17 17 17 17 15 15 15 15 17 17 17 17 16 14 15 15 16 17 17 17 17 16 15 15 15 16 17 17 17 17 14 15 15 15 16 17 17 17 17 15 15 15 15 17 17 17 17 16 15 15 15 15 17 17 17 18 15 15 15 15

基本是均匀分布的,并且哈希函数及其简洁,实现了快速访问,典型的以空间换时间例子,堪称完美(原理还没弄明白),要是项王看过Linux内核,懂得这水平的哈希函数,或许就不会有乌江惨剧了喔。

阅读(5814) | 评论(4) | 转发(7) |
给主人留下些什么吧!~~

lmnos2012-10-07 16:52:18

很生动

Bean_lee2012-08-19 00:10:14

leon_yu: 我倒没怎么研究算法,这个哈希函数是看ULK的时候遇到的,就专门查资料分析了一下,ULK里这个整数0x9e370001UL,怎么取的我也没弄明白,.....
如果你感兴趣的话,可以看Knuth大神的计算机程序设计艺术,里面提到过这个数字.
我也没看.

hash函数有很多种,效率是不同的. 网上有比较的文章.

leon_yu2012-08-19 00:04:03

Bean_lee: 最后对项王的调戏,太搞了。
网上有 各种hash函数的性能比较,
另外最后写个通用的hash table,就更完美了。.....
我倒没怎么研究算法,这个哈希函数是看ULK的时候遇到的,就专门查资料分析了一下,ULK里这个整数0x9e370001UL,怎么取的我也没弄明白,

Bean_lee2012-08-18 08:29:06

最后对项王的调戏,太搞了。
网上有 各种hash函数的性能比较,
另外最后写个通用的hash table,就更完美了。