散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
这是来自wiki的解释,为了透彻理解这个问题,我们举个简单的例子…
比如项羽要分封十八路诸侯,这十八路诸侯倒秦功劳、实力以及对项羽的忠诚度不一而足,如何分封、管制就是一个大问题。每个诸侯包括拥有兵力,封王地域等诸多信息,把这些信息全放进一个结构体,我们只要知道这个结构体地址,即可知道该王所有信息。我们声明一个有序数组king_value[n],把每个封王(结构体指针)放在king_value []中占一项,那么项王只要拥有king_value [n]这个数组,就可以快速调用天下诸侯的所有信息。
问题就出现了,假如你要查找某个诸侯的资料,必须把这个数组遍历一遍,时间复杂度是O(n),明显的n越大,找到某个封王的时间就越长,是相当低效的。
为了加速查找,我们想到一个办法,把某封王通过一个关系转换,得到一个整数(即关键码值),把该王信息保存在,以这个整数为下标的king_value[n]数组中,那么以后要查找任一个封王信息,只要把该王通过指定关系转换计算一下,就得到一个数组下标,很容易就得该王储存项,时间是固定的长度O(1)。这个转换关系就是哈希函数,这个数组就是哈希表。
那么现在的问题是,如何实现这个转换关系,我们看看Linux内核的哈希函数
-
unsigned long hash_long(unsigned long val,unsigned int bits)
-
{
-
unsigned long hash = val * 0x9e370001UL;
-
return hash >> (32 - bits);
-
}
还有一个冲突问题,比如给英布用哈希函数得到整数10,就把king_value[10]就分给他了,那接着给刘季的哈希函数也得到10,怎么办呢,处理方法有开放地址法、再散列法、拉链法等。这里简单的放在11,若11已经有人占了,就给12,依次类推。
那么内核这个哈希函数是否可以达到关键字均衡存放呢,写个简单的程序来测试下内核这个哈希函数是否靠谱,
-
#include <stdio.h>
-
#include <stdlib.h>
-
-
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]);
-
-
for (i = 0; i <= 32767; i++) {
-
if (hash_long(i, 11) == j)
-
-
printf("pid-->%d\n", hash_long(i,11));
-
}
-
return 0;
-
}
主要功能是把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出现的分布
-
#!/bin/bash
-
-
declare -i i
-
-
i=0
-
-
for((i=0;i<2047;i++))
-
-
do
-
-
./a.out $i | wc -l |tr '\n' ' '
-
-
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内核,懂得这水平的哈希函数,或许就不会有乌江惨剧了喔。
阅读(320) | 评论(0) | 转发(0) |