有一种“奇葩”的存储方式，它将记录的关键字与存储位置建立关系，在理想情况下插入和查询的时间复杂度都是。嗯？那岂不是比平衡二叉树还厉害？那为什么还要花那么多的时间研究平衡二叉树？

我认为主要原因有两点：

1. 平衡二叉树自带排序，而散列表没有排序。
2. 散列表需要视情况“定制”散列函数和处理冲突的方法，不够通用，且维护起来比较麻烦。

一个思想实验：有一些数据需要存储，这些数据在查询时以手机号作为关键字进行查询。完全建立一个顺序表，以手机号作为顺序表的序号存储数据，插入和查询的时间复杂度都是。但是因为手机号是11位的，为了让手机号作为顺序表的序号，哪怕你只存一条记录，也必须创建一个长达11位的顺序表，白白浪费空间。

散列表的核心是对关键字空间进行压缩。散列表的存储方式与上述方法类似，只不过散列表通过散列函数将11位的手机号进行压缩，所以只需要很小的空间。

散列函数 - 整除留余

为了让散列地址更加均匀，M取不大于列表长度的最大质数。

散列函数 - MAD法

整除留余法有两个缺点：

• 存在不动点，不管M取何值，hash(key) =0
• 相邻关键码散列地址也相邻

MAD法对于这两个问题进行改进：

散列函数 - 其他方法

还有一些常用的方法：数字分析、平方取中、折叠汇总、位异或法、伪随机数法。

这些方法原理是让原关键码中的各数位对最终地址拥有更平均的影响力，从而让关键码更随机、没有规律。

处理冲突 - 拉链法：

处理冲突 - 开放地址法：

散列表的平均查找长度依赖于装填因子。越大，散列表越满，发生冲突的可能性越大，反之发生冲突的可能性越小。

平均查找长度

散列函数：H(key)=(keyx3) mod 7

共有7个元素，它们查找成功的次数分别为1、2、1、1、1、3、3，所以：

如果我们在表中查找20，会失败，因为表中没有这个数，那么这种失败有多少种？有无穷多种，因为不在这张表中的数有无穷多个，但是这些数的散列值一共有7种，因为散列函数是mod 7的，我们可以计算出每种查找失败所用的次数分别为3、2、1、2、1、5、4，所以：