经典哈希函数特性

• 输入域是无穷大的，输出域是有限的
• 固定的输入，返回的输出hashCode也是固定的
• 必然有不同的输入相同的输出
• 哈希函数具有离散性

常见的HASH算法

• 直接定址法
  • 直接以关键字K或者K加上某个常数(K+C)作为HASH地址
• 数字分析法
  • 提供关键字中取值比较均匀的数字作为Hash地址
• 除留余数法
  • 用关键字K除以某个不大于Hash表长度m的数P,将所得余数作为Hash地址
• 分段叠加法
  • 按照Hash表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短，然后将这几部分相加，舍弃最高进位后的结果就是该关键字的Hash地址
• 平方取中法
  • 如果关键字各个部分分布都不均匀，则可以先求出它的平方值，然后按照需求取中间的几位作为Hash地址
• 伪随机数法
  • 采用一个伪随机数当作Hash函数
• 斐波那契法
  • 2 ^ 32 * 0.6180339887为了让数据更加的散列，减少哈希碰撞

并查集

• 作用
  • 快速的查找两个元素是否属于一个集合
  • 两个元素各自所在的集合，将两个集合合并

解决hash冲突的方法

再散列方法（开放地址法）

线性探测

• 冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
• 优点：易于实施；总是找到一个位置（如果有）；当表不是很满时，平均情况下的性能非常好。
• 缺点：表的相邻插槽中会形成“集群”或“集群”键；当这些簇填满整个阵列的大部分时，性能会严重下降，因为探针序列执行的工作实际上是对大部分阵列的穷举搜索。

随机散列

• di=伪随机数序列。
  具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。
  例如，已知哈希表长度m=11，哈希函数为：H（key）= key % 11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。
  如果用线性探测再散列处理冲突，下一个哈希地址为H1=（3 + 1）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 + 2）% 11 = 5，还是冲突，继续找下一个哈希地址为H3=（3 + 3）% 11 = 6，此时不再冲突，将69填入5号单元。
  如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3 + 12）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 - 12）% 11 = 2，此时不再冲突，将69填入2号单元。
  如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，……..，则下一个哈希地址为H1=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址为H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元。

双重哈希（再Hash）

• 这种方法是同时构造多个不同的哈希函数：Hi=RH1（key） i=1，2，…，k。当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

链地址法

• 这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

拉链法与开放地址法相比的缺点

• 拉链法的优点
  与开放定址法相比，拉链法有如下几个优点：

  • 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
  • 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
  • 开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
  • 在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

• 拉链法的缺点

  • 指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

经典HASH问题

• 有一个包含20亿个全是32位整数的大文件，在其中找到出现次数最多的数，但是内存限制只有2G
  • 使用哈希函数分流
  • 分别使用hashMap进行统计，找到最多的数
• 32位无符号整数的范围是0-42亿，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围内必然有没有出现过的数，可以使用最多10M的内存，只用找到一个没出现过的数即可，该如何找？
  • 范围分成64个区间
  • 申请一个$2^{32}$ / 64 的bitMap，大约占500M/64 = 8M空间
  • 必然有填不满的区间，然后根据这个区间上缺的数遍历这个文件

总结

• 根据内存限制决定区间的大小，根据区间大小，得到有多少个变量，来记录每个区间的数出现的次数
• 统计区间上的数的出现次数，找到不足的区间
• 利用bitMap对不满的区间，进行这个区间上的数的词频统计