散列表 (Hash table, 也叫哈希表), 是根据键(Key) 而直接访问在内存存储位置的数据结构. 也就是说, 它通过计算一个关于键值的函数, 将所需查询的数据映射到表中一个位置来访问记录, 这加快了查找速度. 这个映射函数称做散列函数, 存放记录的数组称做散列表.
一个通俗的例子是, 为了查找电话簿中某人的号码, 可以创建一个按照人名首字母顺序排列的表(即建立人名 到首字母 的一个函数关系), 在首字母为 W 的表中查找 "王" 姓的电话号码, 显然比直接查找就要快得多. 这里使用人名作为关键字,"取首字母" 是这个例子中散列函数的函数法则, 存放首字母的表对应散列表. 关键字和函数法则理论上可以任意确定.
1. 基本概念
若关键字为 , 则其值存放在 的存储位置上. 由此, 不需比较便可直接取得所查记录. 称这个对应关系 f 为散列函数, 按这个思想建立的表为散列表.
对不同的关键字 可能得到同一散列地址, 即 , 而 , 这种现象称为冲突(或碰撞, 英语: Collision). 具有相同函数值的关键字对该散列函数来说称做同义词. 综上所述, 根据散列函数 和处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间) 上, 并以关键字在地址集中的 "像" 作为记录在表中的存储位置, 这种表便称为散列表, 这一映射过程称为散列造表或散列, 所得的存储位置称散列地址.
若对于关键字集合中的任一个关键字, 经散列函数映象到地址集合中任何一个地址的概率是相等的, 则称此类散列函数为均匀散列函数(Uniform Hash function), 这就使关键字经过散列函数得到一个 "随机的地址", 从而减少冲突.
2. 构造散列函数的方法
散列函数能使对一个数据序列的访问过程更加迅速有效, 通过散列函数, 数据元素将被更快定位.
直接定址法: 取关键字或关键字的某个线性函数值为散列地址. 即 或 , 其中 为常数(这种散列函数叫做自身函数)
数字分析法: 假设关键字是以 r 为基的数, 并且哈希表中可能出现的关键字都是事先知道的, 则可取关键字的若干数位组成哈希地址.
平方取中法: 取关键字平方后的中间几位为哈希地址. 通常在选定哈希函数时不一定能知道关键字的全部情况, 取其中的哪几位也不一定合适, 而一个数平方后的中间几位数和数的每一位都相关, 由此使随机分布的关键字得到的哈希地址也是随机的. 取的位数由表长决定.
折叠法: 将关键字分割成位数相同的几部分 (最后一部分的位数可以不同), 然后取这几部分的叠加和(舍去进位) 作为哈希地址.
除留余数法: 取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址. 即 即 , . 不仅可以对关键字直接取模, 也可在折叠法, 平方取中法等运算之后取模. 对 的选择很重要, 一般取素数或 , 若 选择不好, 容易产生冲突.
3. 处理冲突
为了知道冲突产生的相同散列函数地址所对应的关键字, 必须选用另外的散列函数, 或者对冲突结果进行处理, 而不发生冲突的可能性是非常之小的, 所以通常对冲突进行处理. 常用方法有以下几种:
开放寻址法(open addressing). 想象一下, 有一趟对号入座的火车, 假设它只有一节车厢, 上来一位坐 7 号座位的旅客. 过了一会儿, 又上来一位旅客, 他买到的是一张假票, 也是 7 号座位, 这时怎么办呢? 列车长想了想, 让拿假票的旅客去坐 8 号座位. 过了一会儿, 应该坐 8 号座位的旅客上来了, 列车长对他说 8 号座位已经有人了, 你去坐 9 号座位吧. 哦? 9 号早就有人了? 10 号也有人了? 那你去坐 11 号吧. 可以想见, 越到后来, 当空座越来越少时, 碰撞的几率就越大, 寻找空座愈发地费劲. 但是, 如果是火车的上座率只有 50% 或者更少的情况呢? 也许真正坐 8 号座位的乘客永远不会上车, 那么让拿假票的乘客坐 8 号座位就是一个很好的策略了. 所以, 这是一个空间换时间的游戏. 玩好这个游戏的关键是, 让旅客分散地坐在车厢里. 如何才能做到这一点呢? 答案是, 对于每位不同的旅客使用不同的探查序列. 例如, 对于旅客 A, 探查座位 7,8,23,56...... 直到找到一个空位; 对于旅客 B, 探查座位 25,66,77,1,3...... 直到找到一个空位. 如果有 m 个座位, 每位旅客可以使用 个排列中的一个.
显而易见, 最好减少两个旅客使用相同的探查序列的情况. 也就是说, 希望把每位旅客尽量分散地映射到 m! 种探查序列上. 换句话说, 理想状态下, 如果能够让每个上车的旅客, 使用 个探查序列中的任意一个的可能性是相同的, 我们就说实现了一致散列.(这里没有用 "随机" 这个词儿, 因为实际是不可能随机取一个探查序列的, 因为在查找这名旅客时还要使用相同的探查序列).
线性探查: 最简单的方法是, 如果发现 values[8] 已经被占用了, 就看看 values[9] 是否空着, 如果 values[9] 也被占用了, 就看看 values[0] 是不是还空着. 完整的描述是, 先使用 H() 函数获取 k 的第一个地址, 如果这个地址已被占用, 就探查下一个紧挨着的地址, 如果还是不能用, 就探查下一个紧挨着的地址, 如果到达了数组的末尾, 就卷绕到数组的开头, 如果探查了 m 次还是没有找到空槽, 就说明数组已经满了, 这就是线性探查(linear probing)
真正的一致散列是难以实现的, 实践中, 常常采用它的一些近似方法. 常用的产生探查序列的方法有: 线性探查, 平方探测, 以及双重散列探查. 这些方法都不能实现一致散列, 因为它们能产生的不同探查序列数都不超过 个(一致散列要求有 个探查序列). 在这三种方法中, 双重散列能产生的探查序列数最多, 因而能给出最好的结果.
显示线性探测填装一个散列表的过程:
关键字为 {89,18,49,58,69} 插入到一个散列表中的情况. 此时线性探测的方法是取 . 并假定取关键字除以 10 的余数为散列函数法则.
image
第一次冲突发生在填装 49 的时候. 地址为 9 的单元已经填装了 89 这个关键字, 所以取 , 往下查找一个单位, 发现为空, 所以将 49 填装在地址为 0 的空单元.
第二次冲突则发生在 58 上, 取, 往下查找 3 个单位, 将 58 填装在地址为 1 的空单元. 69 同理.
表的大小选取至关重要, 此处选取 10 作为大小, 发生冲突的几率就比选择质数 11 作为大小的可能性大. 越是质数, mod 取余就越可能均匀分布在表的各处.
聚集 (Cluster, 也翻译做 "堆积") 的意思是, 在函数地址的表中, 散列函数的结果不均匀地占据表的单元, 形成区块, 造成线性探测产生一次聚集 (primary clustering) 和平方探测的二次聚集(secondary clustering), 散列到区块中的任何关键字需要查找多次试选单元才能插入表中, 解决冲突, 造成时间浪费. 对于开放定址法, 聚集会造成性能的灾难性损失, 是必须避免的.
来源: http://www.jianshu.com/p/101c263cd93e