1、功能：哈希表可以直接通过关键字直接找到数据的位置，不需要进行任何的比较，也就是说，哈希表建立了关键字和存储地址之间一种直接的映射关系，其查找的效率相对较高。
2、定义
1、哈希地址：哈希地址只是在查找表中的存储位置，并不是实际的物理存储物质
2、哈希函数：f()是一个函数，通过这个函数可以快速求出关键字对应的数据的哈希地址，称为hash函数
3、冲突：由于用算法求关键字对应哈希地址，会出现两个人算出来是同一块hash地址的情况，哈希只能减少冲突的出现，无法完全避免冲突。
3、哈希表构造
哈希函数的构造方法（常用）：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法
1、直接定址法
哈希函数为一次函数，H(key) = key 或 H(key) = a * key + b。 H(key)表示关键字 key对应的hash地址， a,b都是常数。
2、数字分析法
如果关键字由多位字符或者数字组成，就可以考虑抽取其中两位或者多位作为该关键字对应的哈希地址，在取法上尽量选择变化较多的位，避免冲突发生。适用于已知的关键字集合。
3、平方取中法
将关键字做平方操作，取中间的几位作为哈希地址。（比较常用）
4、折叠法
将关键字分割成位数相同的几部分，最后一部分的位数可以不同，然后取这几部分叠加和（舍去进位）作为哈希地址，此方法适合关键字位数较多的情况。
移位折叠：将分割后的每一小部分，按照最低位对齐，然后相加
间界折叠：从一端向另一端沿分割线来回折叠
5、除留余数法
若已知整个哈希表的最大长度m，可以取一个不大于m的数p，然后对该关键字key做取余运算，H(key) = key%p(p<=m)，适用于哈希表大小已知。
p的取值很重要，p可以为不大于m的质数或者不包含小于20的质因数的合数。
6、随机数法
取关键字的一个随机函数值作为它的哈希地址，H(key) = random(key)，此方法用于关键字长度不等的情况（注意：这里的随机函数其实是伪随机函数，随机函数是即是每次给定的key相同，但是H(key)都是不同，而伪随机数正好相反，每个key都对应的是固定的H（key））。
4、选择方法构造哈希表
1、关键字的长度，长度不等，用随机数法；关键字较多，用折叠法或者数字分析法；关键字位数较短，可以考虑平方取中
2、哈希表的大小，大小已知，可以使用储留余数法；
3、关键字分布情况
4、查找表的查找频率
5、计算哈希函数所需时间（包括硬件指令元素）
5、处理冲突的方法
1、开放寻址法
在出现哈希冲突时在哈希表中找一个新的空闲位置存放元素。
1、线性探测法：当冲突发生时，顺序查看表中的下一个单元，知道找出一个空闲单元
优点：解决冲突简单
缺点：容易产生堆积问题
2、平方探测法：比如发生冲突的地址时d，平方探测法得到新的地址序列为 d+1平方，d-1平方，d+2平方……
缺点：避免出现堆积问题
缺点：不能探测到散列表上的所有单元，但至少能探测到一半单元
2、链地址法：将所有产生冲突的关键字对应的数据全部存储在同一个线性链表中，拉链法适用于经常插入和删除的情况
优点：提高查找速率
缺点：需要额外空间
3、再哈希法
当通过哈希函数求得的哈希地址同其他关键字产生冲突时，使用另一个哈希函数计算，知道冲突不再发生。
6、哈希表查找的性能
在构造哈希表过程中，由于冲突的产生，使得哈希表的查找算法 仍然会涉及到比较的过程，因此对哈希表的查找效率仍然以平均查找长度来衡量
比较次数取决于以下方面
1、哈希函数：哈希函数的好坏取决于影响出现冲突的频繁程度。但是一般情况下，韩熙韩束相比于后两种的影响，可以忽略不计
2、处理冲突的方式：对于同一组关键字，设定相同的哈希函数，使用不同处理冲突的方式得到的哈希表是不同的，表的平均查找长度也不同
3、哈希表的装填因子：在一般情况下：处理冲突的方式相同，平均查找长度取决于哈希表的装满程度，越满，冲突越多
装填因子 = 哈希表中的数据个数/哈希表长度
经过计算，假设表中所有数据查找概率相等的情况下，对于表长为m，合适为n的哈希表：
查找成功的平均长度：-1/装填因子 * ln（1-装填因子）
查找不成功的平均查找长度：1/(1-装填因子)
哈希表的查找效率只能装填因子有关，和哈希表中的数据的个数无关，所以选用哈希表做查找操作时，选择一个合适的装填因子非常重要
代码明天补
7、对比
标签：哈希,关键字,地址,查找,冲突,key From： https://www.cnblogs.com/gunancheng/p/17472631.html