算法思想：
哈希表
什么是哈希表
在前面讨论的各种结构(线性表、树等)中,记录在结构中的相对位置是随机的,和记录的关键字之间不存在确定的关系,因此,在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在”比较”的基础上。
在顺序查找时,比较的结果为”=”与”!=”两种可能;
在折半查找、二叉排序树查找和B树查找时,比较的结果为”
理想的情况是希望不经过任何比较,一次存取便能得到所查记录,那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个惟一的存储位置相对应。因而在查找时,只要根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录,则必定在f(K)的存储位置上,由此,不需要进行比较便可直接取得所查记录。在此,我们称这个对应关系f为哈希( Hash)函数,按这个思想建立的表为哈希表。
哈希函数的构造方法
哈希函数是从关键字集合到地址集合的映像。通常，关键字集合比较大，它的元素包括所有可能的关键字，而地址集合的元素仅为哈希表中的地址值。哈希函数其实是一个压缩映像，那么这种情况就不可避免的产生冲突，那么在建造哈希表时不仅要设定一个好的哈希函数，还要设定一种处理冲突的方法。（设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集上，并以关键字在地址集中的”像”作为记录在表中的存储位置，这种表就是哈希表，映像的过程为哈希造表或散列，所得的存储位置称哈希地址或散列地址）
（1）直接定址法
取关键字或关键字的某个线性函数值为哈希地址。即H(key)=key 或 H(key)=a*key+b (a,b为常数)。
举例1：统计1-100岁的人口，其中年龄作为关键字，哈希函数取关键字自身。查找年龄25岁的人口有多少，则直接查表中第25项。
地址 01 02 03 … 25 26 27 … 100
年龄 1 2 3 … 25 26 27 … ….
人数 3000 2000 …………. 1050
…
举例2：统计解放以后出生人口，其中年份作为关键字，哈希函数取关键字自身加一个常数H(key)=key+(-1948).查找1970年出生的人数，则直接查(1970-1948)=22项即可。
地址 01 02 03 … 22 23 24 …
年份 1949 1950 1951 … 1970
人数 …………. 15000
…
（2）数字分析法
若关键字是以r为基的数（如：以10为基的十进制数），并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
举例：有80个记录，其关键字为8位十进制数，假设哈希表长，则可取两位十进制数组成哈希地址，为了尽量避免冲突，可先分析关键字。
8 1 3 4 6 5 3 2
8 1 3 7 2 2 4 2
8 1 3 8 7 4 2 2
8 1 3 0 1 3 6 7
8 1 3 2 2 8 1 7
8 1 3 3 8 9 6 7
8 1 3 5 4 1 5 7
8 1 3 6 8 5 3 7
8 1 4 1 9 3 5 5 ………..
经分析，发现第一位、第二位都是8,1，第三位只可能取3或4，第八位只可能取2,5或7，所以这四位不可取，那么对于第四、五、六、七位可看成是随机的，因此，可取其中任意两位，或取其中两位与另外两位的叠加求和舍去进位作为哈希地址。
（3）平方取中法
取关键字平方后的中间几位为哈希地址。（较常用的一种）
举例：为BASIC源程序中的标识符键一个哈希表（假设BASIC语言允许的标识符为一个字母或者一个字母和一个数字两种情况，在计算机内可用两位八进制数表示字母和数字），假设表长为512=，则可取关键字平方后的中间9位二进制数为哈希地址。（每3个二进制位可表示1位八进制位，即3个八进制位为9个二进制位）
A ：01 （A的ASCII码值为65,65的八进制为101，取后两位表示关键字）
B：02 （B的ASCII码值为66,66的八进制为102，取后两位表示关键字）
…
Z：32（Z的ASCII码值为90,90的八进制为132，取后两位表示关键字）
…
0：60（0的ASCII码值为48,48的八进制为60，取后两位表示关键字）
…
9：71（9的ASCII码值为57,57的八进制为71，取后两位表示关键字）
记录 关键字 关键字的平方 哈希地址（~）
A 0100 0010000 010
I 1100 1210000 210
P1 2061 4310541 310
Q2 2162 4741304 741
（4）折叠法
将关键字分割成位数相同的几部分（最后一部分的位数可不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。适用于关键字位数比较多，且关键字中每一位上数字分布大致均匀时。
举例：根据国际标准图书编号（ISBN）建立一个哈希表。如一个国际标准图书编号 0-442-20586-4的哈希地址为：
5864 5864
4220 0224
- 04 + 04
10088 6092
移位叠加 间接叠加
H（key）=0088（将分割后的每一部分的最低位对齐） H（key）=6092（从一端向另一端沿分割界来回叠加）
（5）除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址（p为素数）
H（key）=key MOD p，p
Original: https://www.cnblogs.com/mydomain/p/11205623.html
Author: 浪里飞
Title: 哈希表查找（散列表查找） c++实现HashMap
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/536347/
转载文章受原作者版权保护。转载请注明原作者出处！