数据结构之散列表

1、散列函数

原则

• 一致性
• 高效性
• 均匀性

定义

1.散列函数计算得到的散列值是一个非负整数。
2.若key1=key2，则hash(key1)=hash(key2)
3.若key≠key2，则hash(key1)≠hash(key2)

如何设计

1.要尽可能让散列后的值随机且均匀分布，这样会尽可能减少散列冲突，即便冲突之后，分配到每个槽内的数据也比较均匀。
2.除此之外，散列函数的设计也不能太复杂，太复杂就会太耗时间，也会影响到散列表的性能。

常见方法

直接寻址法

取关键字key的某个线性函数为散列地址，如Hash(key) = key 或 Hash(key) = A*key+B; A，B为常数。
如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。但这种方法效率不高，时间复杂度是O(1)，空间复杂度是O(n)，n是关键字的个数。

除留取余法

关键值除以比散列表长度小的素数所得的余数作为散列地址。Hash(key) = key % p;
p的选取非常关键，p选择的好的话，能够最大程度地减少冲突，p一般取不大于m的最大质数。

平方取中法

先计算构成关键码的标识符的内码的平方，然后按照散列表的大小取中间的若干位作为散列地址。
如：有以下关键字序列{421，423，436}，平方之后的结果为{177241，178929，190096}，那么可以取{72，89，00}作为Hash地址。

折叠法

把关键码自左到右分为位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。把这些部分的数据叠加起来，就可以得到具有关键码的记录的散列地址。
如：比如关键字是9876543210，散列表表长是3位，将其分为四组，然后叠加求和：987 + 654 + 321 + 0 = 1962，取后3位962作为散列地址。

随机数据法

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

数学分析法

设有N个d位数，每一位可能有r种不同的符号。这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布均匀些，每种符号出现的机会均等；在某些位上分布不均匀，只有某几种符号经常出现。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址

2、冲突解决

开放寻址

线性探测

• 顺序查看下一个单元

二次探测

• 在表的左右进行跳跃式探测

伪随机探测

• 构造伪随机数据列或者上两种结合

再hash法

• 不同的hash进行探测；缺点是增加的计算时

链地址法

• 构建链表：可以插入和删除

其他

• 如建立公共溢出区

3、动态扩容

装载因子
时间复杂度：摊还分析法
如何避免低效扩容

• 分批扩容的插入操作：当有新数据要插入时，我们将数据插入新的散列表，并且从老的散列表中拿出一个数据放入新散列表。每次插入都重复上面的过程。这样插入操作就变得很快了。
• 分批扩容的查询操作：先查新散列表，再查老散列表。
• 过分批扩容的方式，任何情况下，插入一个数据的时间复杂度都是O(1)。

4、工业级的散列表

要求

• 支持快速的查询、插入、删除操作
• 内存占用合理，避免大量的空间浪费
• 性能稳定在极端情况下，散列表的性能也不会退化到无法接受的情况。

方案

• 设计合理散列函数
• 定义装载因子阈值，并且设计动态扩容策略；
• 选择合适的散列冲突解决方法

5、位图

定义

• 用一个Bit位来标记某个元素对应的Value，而Key即是该元素。

思想

• 32位机器上，一个整形，比如int a;在内存中占32bit位，可以用对应的32bit位对应十进制的0-31个数，BitMap算法利用这种思想处理大量数据的排序与查询.

优点

运算效率高，不许进行比较和移位；
占用内存少，比如N=10000000；只需占用内存为N/8=1250000Byte=1.25M。

缺点

所有的数据不能重复。即不可对重复的数据进行排序和查找。
比如：00000000000000000000000000010100 标注了2和4。

应用

*   排序（非重复）
*   去重
*   快速查询
*   布隆过滤器: 见：[http://www.cnblogs.com/dolphin0520/archive/2012/11/10/2755089.html](http://www.cnblogs.com/dolphin0520/archive/2012/11/10/2755089.html)