我要评论
散列思想
存在散列思想的例子：
运动会上，根据运动员的编号快速找到对应选手的信息，编号由6位数字组成，前两位表示年级，中间两位表示班级，最后两位表示递增序号，比如051167表示05年级，11班，67号选手。这时我们可以截取参赛编号的后两位作为数组下标，来存取选手信息数据。当通过参赛编号查询选手信息的时候，我们用同样的方法，取参赛编号的后两位，作为数组下标，来读取数组中的数据。
- 参赛选手的编号叫作键(key)或关键字；
- 参赛编号转为数组下标的映射方法叫作散列函数（哈希函数或hash函数）;
- 散列函数计算的值叫作散列值（hash值或哈希值）。
散列函数
运动员的散列函数如下所示：
int hash(string key) {
// 获取后两位字符
string lasttwochars = key.substr(length-2, length);
// 将后两位字符转换为整数
int hashvalue = convert lasttwochas to int-type;
return hashvalue;
}
散列函数的设计需要符合下面3个基本要求:
-
散列函数计算得到的散列值是一个非负整数；
数组下标是从0开始的。
-
如果key1 = key2，那hash(key1) == hash(key2)；
相同的key经过散列函数得到的散列值应该相同。
-
如果key1 ≠ key2，那hash(key1) ≠ hash(key2)。
散列冲突
常见的散列冲突解决方法有：
- 开放寻址法(open addressing)
- 链表法(chaining)
装载因子：
散列表的装载因子=填入表中的元素个数/散列表的长度
装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
开放寻址法
线性探测
当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
上图中，黄色代表空闲位置，橙色代表已经存储了数据。散列表大小为10，元素x插入散列表之前，已经有6个元素插入了。
x元素插入过程如下：
- x经过hash算法，被散列到了位置7，存在冲突；
- 顺序往下找空闲位置，遍历到尾部没有，继续从头遍历，找到空闲位置2，将其插入。
元素查找过程，比如要查找元素x，过程如下：
- x通过hash函数计算对应的散列值；
- 对比数组下标为散列值的元素和查找元素x：
- 若相等，则找到要查找的元素x；
- 若不相等，依次往后查找，若一直遍历到数组中的空闲位置还没找到，则说明要查找的元素不在散列表中。
元素删除过程，线性探测法不能真正删除元素，因为查找过程中找到一个空闲位置，就认定散列表中不存在该数据，但空闲位置是后面删除的，就会导致原来的查找算法失效。
将要删除的元素标记为deleted，当线性探测查找时，遇见标记元素，不是停下来，而是继续向下探测。
存在问题：
当散列表中插入的数据越多，散列表的冲突概率越大，查找、插入、删除最坏的情况下需要探索整个散列表，时间复杂度为o(n)。
二次探测
线性探测每次探测的步长是 1，探测的下标序列为hash(key)+0，hash(key)+1，hash(key)+2……二次探测的步长则为原来的二次方，它探测的下标序列就是 hash(key)+0，hash(key)+1²，hash(key)+2²……
双重散列
不仅要使用一个散列函数，使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……
先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。
链表法
在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。
如下图所示：
-
插入时：
只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中，时间复杂度为o(1)；
-
查找、删除时：
通过散列函数计算出对应的槽，然后遍历链表查找或者删除，时间复杂度跟链表长度k成正比，对于散列比较均匀的散列函数来说，k=n/m，其中 n 表示散列中数据的个数，m 表示散列表中“槽”的个数。
例子
问题：
-
存储分析
常用的英文单词有20万个左右，假设单词的平均长度是10个字母，平均一个单次占10个字节，那20万单词大约占2mb的存储空间，放大10倍也才20mb。所以完全可以用散列表来存储英文单词词典。
-
实现
- 当用户输入某个英文单词时，我们拿用户输入的单词去散列表中查找；
- 如果查到，则说明拼写正确；如果没有查到，则说明拼写可能有误，给予提示。
发表评论