转载原文：
什么是散列表（哈希表）
散列表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
散列函数
1、散列函数需要的性质
- 得到的散列值是一个非负整数
- 两个相同的键，通过散列函数计算出的散列值也相同
- 两个不同的键，计算出的散列值不同
对于第三条来说，想要找到不同的 key 对应的散列值都不一样的散列函数是不可能的。
2、散列冲突（collision）
冲突：两个不同的键分配的位置相同（映射到了同一个数字上）。
3、常见散列函数
（1）数字分析法
通过对数据的分析，发现数据中冲突较少的部分，并构造散列地址。例如同学们的学号，通常同一届学生的学号，其中前面的部分差别不太大，所以用后面的部分来构造散列地址。
数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况、它完全依赖于关键码集合
(2)平方取中法
假设关键字是1234，平方之后是1522756，再抽取中间3位227，用作散列地址。平方取中法比较适合于不 知道关键字的分布，而位数又不是很大的情况。
因为：计算平方之后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的散列地址。一般取散列地址为8的某次幂
（3）折叠法
将关键字从左到右分割成位数相等的几部分，最后一部分位数不够时可以短些，然后将这几部分叠加求和， 并按散列表表长，取后几位作为散列地址。
比如关键字是9876543210，散列表表长是3位，将其分为四组，然后叠加求和：987 + 654 + 321 + 0 = 1962，取后3位962作为散列地址。
折叠方式除了直接相加还有来回反转相加的分界法，987+456+321+0
折叠法适合关键码位数较多，且关键码每一位上数字分布比较均匀的情况
（4)留取余数法
f(key) = key mod p (p≤m)，m为散列表长。
这种方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。根据经验，若散列表表长为m，通常p为小于或等于表长（最好接近m）的最小质数，可以更好的 减小冲突。
4、处理冲突的方法
(1)开放地址法(闭散列法)
开放地址就是一旦发生冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并且记录它。至于如何寻找下一个空的散列地址，有三种方法
①线性探查法
f(key)=(f(key)+d)%m ,其中d取（0，1,2,3,4.....，m-1），m为散列表的长度
线性探测来解决冲突问题，会造成冲突堆积。例如：本来是属于下标1的元素，现在却占用了下标为2的空间，这会造成待会我们需要存放本来要放在下标为2的元素时，再次发生冲突，这个冲突会一直传播下去，造成查找和插入效率都大大减低。
②二次探测法
f（key）=（f(key)+d）%m, ,其中d取（0^2，1^2,-1^2,2^2,-2^2,3^2,-3^2,4^2,-4^2...,q^2,-q^2），q<=m/2,m为散列表的长度
其实，这个是对线性探测的一个优化，增加了平方可以不让关键字聚集在某一块区域。
③随机探测法（双散列法）
f（key）=（f(key)+d）%m, d为随机数列，而m为表长
(2)链地址法(开散列法)
其实就是当发生冲突时，我还是把它存放在当前的位置，只是每个位置都是使用链表来存放同义词，这个思路和图的邻接表存储方式很相似。
（3）良好的装填因子
装填因子：a=n/m 其中n 为关键字个数，m为表长。
平均查找成功和不成功长度
一定要先理解ASL概念
设数据表中有 n 个元素，搜索第 i 个元素的概率为 pi搜索到第 i 个元素所需比较次数为 ci，则搜索成功的
平均搜索长度:
一般情况下我们认为pi是相同的，就像有n个小球随记抽取一个，概率为1/n，我们查找某个数的概率也是1/n
线性探查法
ASL成功=（探查每个元素的次数求和）/表中元素的个数
理解：既然能查询成功，说明一定是表中元素，所以计算每个元素的查找长度求和后乘查找每个元素的概率1/5
ASL不功=（对从0~MOD-1的地址逐个求出分别离他们按顺序查找最近的空元素位置的长度再求和）/MOD长
之所以查询到空就是探查失败，因为若有该数据，则该空位置是可以存放的
理解：既然查找不成功，说明一定不表是中元素，这时候可能对散列函数值任意一个查找，若使用留取余数法则一共有MOD种查找可能，每种可能查找的概率为1/MOD，再对每种可能的查询分析查找长度再求和，注意查询失败的条件是查询倒空而不是查询到表尾
