|
Hash函数简介
hash函数是把任意长度的输入变换成固定长度的输出，该输出就是散列值。散列值的空间
通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定
唯一的输入值。相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能
十分之高，不考虑哈希冲突的情况下（后面会探讨下哈希冲突的情况），仅需一次定位即可
完成，时间复杂度为O(1)。
常见的Hash函数
a. 直接定址法：直接以关键字k或者k加上某个常数（k+c）作为哈希地址（H(k)=ak+b）。
b. 数字分析法：提取关键字中取值比较均匀的数字作为哈希地址（如一组出生日期，相较
于年-月，月-日的差别要大得多，可以降低冲突概率）
c. 分段叠加法：按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以
比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。
d. 平方取中法：如果关键字各个部分分布都不均匀的话，可以先求出它的平方值，然后按照
需求取中间的几位作为哈希地址。
e. 伪随机数法：选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度
不同的场合。
f. 除留余数法：用关键字k除以某个不大于哈希表长度m的数p，将所得余数作为哈希表地址
（H(k)=k%p, p<=m; p一般取m或素数）。
冲突：
冲突：对于不同的关键字ki、kj，若ki != kj，但H(ki) = H(kj)的现象叫冲突。
就是不同的输入却得到了相同的输出。
常见的冲突解决办法：
a. 链地址法：将哈希表的每个单元作为链表的头结点，所有哈希地址为 i 的元素构成一个
同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。
b. 开放定址法：即发生冲突时，去寻找下一个空的哈希地址。只要哈希表足够大，总能找到
空的哈希地址。当节点深度高于八个的时候采用二叉树查询，当小于等于六个的时候采用
数组顺序存储。
c. 再哈希法：即发生冲突时，由其他的函数再计算一次哈希值。
d. 建立公共溢出区：将哈希表分为基本表和溢出表，发生冲突时，将冲突的元素放入溢出表。
|