哈希函数详解

桃扇骨 2022-06-18 03:42 191阅读 0赞

散列表（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.    
    
4.  unsigned long hash\_long(unsigned long val,unsigned int bits)
5.  \{   
    
6.    
    
7.       unsigned long hash = val\*0x9e370001UL;  
    
8.    
    
9.       return hash >> (32\-bits);
10. \}  
    
11.   
    
12. int main(int argc, char \*argv\[\])
13. \{ 
14.      int i, j = atoi(argv\[1\]);  
    
15.   
    
16.      for (i = 0; i <= 32767; i\+\+) \{ 
17.            if (hash\_long(i, 11) == j)  
    
18.   
    
19.                 printf("pid-->%d\\n", hash\_long(i,11));
20.      \}
21.      return 0;
22. \}

主要功能是把0～32767的pid值转换为hash的索引

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

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

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

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

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

点击(此处)折叠或打开

1.  \#!/bin/bash  
    
2.    
    
3.  declare \-i i  
    
4.    
    
5.  i=0  
    
6.    
    
7.  for((i=0;i<2047;i\+\+))  
    
8.    
    
9.  do  
    
10.   
    
11.          ./a.out $i | wc \-l |tr '\\n' ' '  
    
12.   
    
13. 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内核，懂得这水平的哈希函数，或许就不会有乌江惨剧了喔。

阅读(3523) | 评论(4) | 转发(7) |

上一篇：Linux编程的经典书籍-推荐书籍

下一篇：深入理解Linux内核(3)---进程

相关热门文章

*  linux 常见服务端口
 *  xmanager 2.0 for linux配置
 *  【ROOTFS搭建】busybox的httpd...
 *  openwrt中luci学习笔记
 *  什么是shell

*  [linux dhcp peizhi roc][]
 *  [关于Unix文件的软链接][Unix]
 *  [求教这个命令什么意思，我是新...][...]
 *  [sed -e "/grep/d" 是什么意思...][sed -e _grep_d_ _...]
 *  [谁能够帮我解决LINUX 2.6 10...][LINUX 2.6 10...]

给主人留下些什么吧！~~

![28_avatar_small.jpg][]

lmnos2012-10-07 16:52:18

很生动![Image 1][]![Image 1][]

回复 | 举报

![06_avatar_small.jpg][]

Bean\_lee2012-08-19 00:10:14

**leon\_yu**: 我倒没怎么研究算法，这个哈希函数是看ULK的时候遇到的，就专门查资料分析了一下，ULK里这个整数0x9e370001UL，怎么取的我也没弄明白，![Image 1][].....

如果你感兴趣的话,可以看Knuth大神的计算机程序设计艺术,里面提到过这个数字.  
我也没看.  
  
hash函数有很多种,效率是不同的. 网上有比较的文章.

回复 | 举报

![40_avatar_small.jpg][]

leon\_yu2012-08-19 00:04:03

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

我倒没怎么研究算法，这个哈希函数是看ULK的时候遇到的，就专门查资料分析了一下，ULK里这个整数0x9e370001UL，怎么取的我也没弄明白， ![Image 1][]

回复 | 举报

![06_avatar_small.jpg][]

Bean\_lee2012-08-18 08:29:06

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

回复 | 举报

评论热议

[linux dhcp peizhi roc]: http://ask.chinaunix.net/question/785970
[Unix]: http://ask.chinaunix.net/question/785964
[...]: http://ask.chinaunix.net/question/785935
[sed -e _grep_d_ _...]: http://ask.chinaunix.net/question/785919
[LINUX 2.6 10...]: http://ask.chinaunix.net/question/785702
[28_avatar_small.jpg]: http://passport.ixpub.net/data/avatar/028/03/21/28_avatar_small.jpg
[Image 1]: 
[06_avatar_small.jpg]: http://passport.ixpub.net/data/avatar/024/77/41/06_avatar_small.jpg
[40_avatar_small.jpg]: http://passport.ixpub.net/data/avatar/024/70/83/40_avatar_small.jpg