哈希表知识点总结

一、基本原理:

假设我们使用一个下标范围比较大的数组来存储元素。设计一个函数(哈希函数,也叫做散列函数),使得每个元素的关键字经过函数运算得到一个函数值(即数组下标),于是用这个数组单元来存储这个元素。通过函数值即数组下标就可以查找数据元素了。

直接定址”与“解决冲突”是哈希表的两大特点。

二、优点:

把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间的做法是值得的。

三、构造方法:

尽力避免冲突但函数也需要易于编码,即易于实现。

1、直接定址法

例:有一个从1到100岁的人口数字统计表,其中,年龄作为关键字,哈希函数取关键字自身。但这种方法效率不高,时间复杂度是O(1),空间复杂度是O(n),n是关键字的个数

2、数字分析法

3、平方取中法

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

4、折叠法

将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址,这方法称为折叠法。

这种方法适用于关键字位数较多,而且关键字中每一位上数字分布大致均匀的情况。

折叠法中数位折叠又分为移位叠加和边界叠加两种方法,移位叠加是将分割后是每一部分的最低位对齐,然后相加;边界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。

例:当哈希表长为1000时,关键字key=110108331119891,允许的地址空间为三位十进制数,则这两种叠加情况如下

移位叠加891+119+331+108+110=(1)559

边界叠加  891+911+331+801+110=(3)044

用移位叠加得到的哈希地址是559,而用边界叠加所得到的哈希地址是44。如果关键字不是数值而是字符串,则可先转化为数。转化的办法可以用ASCⅡ字符或字符的次序值。

5、除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。H(key)=key MOD p (p<=m)

6、随机数法

选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/c3ab0ab93f849cf1de59982719540201.html