HardBirch

Hash知识介绍

时间:09-10-19 栏目:系统技术篇 作者:鲁智森也有文化 评论:0 点击: 2,170 次

9.3.2 哈希函数的构造方法

 

什么是好的哈希函数:均匀的哈希函数

 

均匀的哈希函数——对于关键字集合中的任一个关键字,经哈希函数映象到

地址集合中任何一个地址的概率是相等的,则称此类哈希函数是均匀的哈希

函数。

 

常用的构造哈希函数的方法有:

(1)直接定址法

(2)数字分析法

(3)平方取中法

(4)折叠法

(5)除留余数法

(6)随机数法

1.直接定址法

 

取关键字或关键字的某个线性函数值为哈希地址.即:

 

H(key)=key 或 H(key)=a*key+b

 

例: 有一个从1岁到100岁的人口数字统计表,其中年龄作为关键字.

 

构造哈希函数: H(key)=key

 

哈希表:

 

例:有一个解放后出生人口调查表,其中年份作为关键字.

构造哈希函数:H(key)=key-1948

 

哈希表:

直接定址法的特点:

(1)构造方法简单,无冲突.

(2)实际中能使用这种哈希函数的情况很少.

2.数字分析法

 

假设关键字是以r为基的数,并且哈希表中可能出现的关键字都是事先知道

的,则可取关键字的若干数位组成哈希地址.

 

例: 有80个记录,其关键字为8位十进制数.哈希表长为100. 部分关键字值如下:

 

构造哈希函数:K(key)=取key中的2位

                            

K(key)=取key中的第4、5、6、7四位中的任2位

                           

K(key)=取key中的第4、5位

 

哈希表:

3.平方取中法

 

取关键字平方后中间几位为哈希地址。

 

例:为BASIC 源程序中的标识符建立一个哈希表。表长为 512。

标识符——为一个字母,或一个字母和一个数字的组合。

 

在计算机内可用两位八进制数表示字母和数字。

A B C… Z … 0 1 2 … 9

01 02 03… 32 … 60 61 62 … 71

 

取组成标识符的字母和数字的八进制数的组合为标识符的关键字,则部分

标识符的关键字为:

构造哈希函数: K(key)=取key*key中的3位

 

K(key)=取key*key中的2、3、4位

哈希表:

 

 

4.折叠法

 

将关键字分割成位数相同的几部分,然后取这几部分的叠加和作为哈希地址。

 

例:为10000册西文图书建立一个哈希表。关键字为图书的编号 (10位十进制数)。

 

位数叠加的方法有两种: 移位叠加、间界叠加

 

移位叠加:是将分割后的每一部份的最低位对齐,然后相加。

间界叠加:是从一端向另一端沿分割界来回折迭,然后对齐相加。

 

例:编号为0442205864的图书,用两种叠加方法得到的哈希地址为:

 

移位叠加:

   

 

5.除留余数法

 

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址.即:

H(key)=key mod p (p<=m)

例子1:假设取标识符在计算机中的二进制表示为它的关键字,然后对P=

模作为哈希地址.

 

A B C… Z … 0 1 2 … 9

01 02 03… 32 … 60 61 62 … 71

则部份标识标关键字为:

 

A1:000001110001 B1:000010110001

C1:000011110001 Z1:011010110001

 

构造哈希函数:H(key)=key mod

 

则A1、B1、C1、Z1的哈希地址都为:110001

 

例子2:若P含有质子pf,则所有含有pf因子的关键字的哈希地址均为pf的

倍数。如有以下关键字:

(28 35 63 49 77 105 56……)

构造哈希函数:H(key)=key mod 21

则(28 35 63 49 77 105 56) 的哈希地址为:7 14 0 7 14 0 14

 

由众人的经验得知:一般情况下,可以选p为质数或不包含小于 20的质因

素的合数。

 

6.随机数法

 

选择一个随机函数,取关键字的随机函数值为它的哈希地址.即:

 

H(key)=random(key)

 

实际工作中,选取哈希函数要考滤的因素有:

(1)计算哈希函数所需时间.

(2)关键字的长度.

(3)哈希表的大小.

(4)关键字的分布情况.

(5)记录的查找频率.

声明: 本文由( 鲁智森也有文化 )原创编译,转载请保留链接: Hash知识介绍

Hash知识介绍:目前有

  1. 板凳
    angelordevel:

    有这六种方法的源代码吗?

    2009-12-20 13:55 [回复]
  2. 沙发
    do2jiang:

    那到没有 没有针对源代码进行深入的 研究,不过网上搜下一大把

    2009-12-21 15:07 [回复]

发表评论


QQ群互动

Linux系统与内核学习群:194051772

WP建站技术学习交流群:194062106

魔豆之路QR

魔豆的Linux内核之路

魔豆的Linux内核之路

优秀工程师当看优秀书籍

优秀程序员,要看优秀书!

赞助商广告

友荐云推荐