哈希表知识点总结

哈希表知识点总结

一、基本原理：

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

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

二、优点：

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

三、构造方法：

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

１、直接定址法

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

２、数字分析法

３、平方取中法

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

４、折叠法

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

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

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

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

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

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

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

５、除留余数法

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

６、随机数法

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

更多详情见请继续阅读下一页的精彩内容：