存档

文章标签 ‘复杂度’

一些常用的算法与数据结构

2011年4月19日  2,103 views 没有评论

哈希函数

哈希法,又称散列法、杂凑法、关键字地址计算法。这种方法的中心思想是,首先在元素的关键字k和存储位置p之间建立一个对应关系f,使得p=f(k),f称为哈希函数。
创建哈希表时,把关键字为k的元素直接存入地址为f(k)的单元,以后当查找关键字为k的元素时,再利用哈希函数计算出该元素所存储的位置p=(k),从而达到按关键字直接存取元素的目的。

哈希函数的构造方法:
1、数字分析法,如果关键字中有分布较为均匀的部分,则可以使用这几位为哈希地址。例如关键字是4位整数d1d2d3d4,其中d2和d4取值均匀,那么哈希函数可以设为h(key)=h(d1d2d3d4)=d2d4。
2、平方取中发,如果不能确定关键字中那几位分布较为均匀,那么可以先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址。这是因为平方后中间几位和关键字中每一位都相关,故不同关键字会以较高的概率产生不同的哈希地址。
3、分段叠加法,这种方法是将关键字按照哈希地址表的位数进行分割,分成几个部分,然后将每一部分相加,舍弃最高进位后得到哈希地址。具体方法有折叠法和移位法。移位法是将每一部分按照低位对齐的方式相加,折叠法是将关键字之字形排列后相加。
4、除余数法,哈希表长为m,那么取小于等于m的最大质数p,那么哈希函数为h(k)=k%p,其中%是模p取余运算。如果m与p较小,那么出现冲突的几率会比较大,这时可以取较大的m和p,比如大于m的最小质数,如果还是不行,那么重复上步。
5、伪随机数法,采用一个伪随机数函数作为哈希函数,即h(key)=random(key)。实际应用中考虑实际情况选择不同的random函数。考虑使用方法时,要考虑的因素有5个,计算哈希函数所需要的时间、关键字的长度、哈希表大小、关键字分布情况、jiluchazhaopinl

哈希函数处理冲突:创建哈希表和查找哈希表都会遇到冲突,两种情况下解决冲突的方法应该是一致的。
(1) 开放地址法,这种方法又称再散列法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果仍然冲突,再以p为基础,产生另一个哈希地址p2,……,直到找到一个不冲突的哈希地址pi,将相应元素存入其中。
通用函数形式:Hi=(H(key)+di)%m(i=1,2,……,n)
H(key)是哈希函数,m为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。

  • 线性探测再散列 di=1,2,3,……,m-1
  • 二次探测再散列 di=1^2,-1^2,2^2,-2^2,…,k^2,-k^2  (k<m/2) 方法特点:冲突发生时,在表的左右进行跳跃式探测,比较灵活。
  • 伪随机探测再散列 di=伪随机数序列

(2)再哈希法

阅读全文…

分类: 心得笔记 标签: , , ,