说来惭愧，本人在几年前就接触了数据结构，对哈希表的认识一直都比较模糊，在日常的学习工作中没少用到这一数据结构，比如像是python语言中的dict，或者是C++中的STL map，这段时间，我自己又重新学习了哈希表的一些设计原理，总结了一下，现在记录在这里，就当是帮助自己加深对hash的了解。
什么是哈希（Hash）表
Hash表也称散列表，也有直接译作哈希表，Hash表是一种特殊的数据结构，它同数组、链表以及二叉排序树等相比较有很明显的区别，它能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。这个源于Hash表设计的特殊性，它采用了函数映射的思想将记录的存储位置与记录的关键字关联起来，从而能够很快速地进行查找。
哈希表的使用
在这里给出来一组数据，这组数据对应有两列（名字/号码），正常情况下，如果我们想要对这种类型的数据进行存储，像是int，string，char等数据类型是无法对这些数据进行存储的，
张三 13980593357
李四 15828662334
王五 13409821234
张帅 13890583472
在C语言中有一种数据类型叫做结构体（struct），我们首先考虑的是定义一个结构体，在结构体中对这两种数据进行定义，然后再将这些联系人的数据信息存储在一个链表中，通过遍历链表的方式，对每一个数据存储单元（struct）进行访问和读写。不过这样的一个劣势就是，时间复杂度为O(n)，因为我们需要对链表进行从头到尾的遍历，即便是通过二分查找的方式进行访问查找，也只能够将时间复杂度降为O(log n).
那么有没有一种数据结构能够将查找的时间复杂度进一步降低呢？这里我们可以考虑使用哈希表（hash table）。
Hash表采用一个映射函数f :key -> address 将关键字映射到该记录在表中的存储位置，从而在想要查找该记录时，可以直接根据关键字和映射关系计算出该记录在表中的存储位置，通常情况下，这种映射关系称作为Hash函数，而通过Hash函数和关键字计算出来的存储位置(注意这里的存储位置只是表中的存储位置，并不是实际的物理地址)称作为Hash地址。比如上述例子中，假如联系人信息采用Hash表存储，则当想要找到“李四”的信息时，直接根据“李四”和Hash函数计算出Hash地址即可。下面讨论一下Hash表设计中的几个关键问题。
哈希函数的设计
Hash函数设计的好坏直接影响到对Hash表的操作效率。
例如对上述的联系人信息进行存储时，采用的Hash函数为：姓名的每个字的拼音开头大写字母的ASCII码之和。
address(张三)=ASCII(Z)+ASCII(S)=90+83=173;
address(李四)=ASCII(L)+ASCII(S)=76+83=159;
address(王五)=ASCII(W)+ASCII(W)=87+87=174;
address(张帅)=ASCII(Z)+ASCII(S)=90+83=173;
假如只有这4个联系人信息需要进行存储，这个Hash函数设计的很糟糕。
首先，它浪费了大量的存储空间。因为假如采用char型数组存储联系人信息的话，每个人的信息需要12个字节来存储（手机号为11位，数值上为100多亿，2^64 =1.844674407371 * 10^19，2^32 = 4294967296，所以需要64位也就是8个字节来存储手机号。每个汉字占两个字节，两个汉字占四个字节。所以总共需要8 + 4 = 12Byte）这样的话，至少需要开辟174*12字节的空间。然而空间利用率只有4/174，不到3%。
另外，根据Hash函数计算结果之后，address(张三)和address(张帅)具有相同的地址，这种现象称作冲突，对于174个存储空间中只需要存储4条记录就发生了冲突，这样的Hash函数设计是很不合理的。所以在构造Hash函数时应尽量考虑关键字的分布特点来设计函数使得Hash地址随机均匀地分布在整个地址空间当中。
通常有以下几种构造Hash函数的方法：
直接定址法
取关键字或者关键字的某个线性函数作为Hash地址，即address(key) = a*key + b; 如果知道学生的学号是从2000开始，最大为4000，则可以将address(key) =key-2000作为Hash地址。
平方取中法
对关键字进行平方计算，然后取结果的中间几位作为Hash地址，假如有以下关键字序列{421，423，436}，平方之后的结果为{177241，178929，190096}，那么可以取中间的两位数{72，89，00}作为Hash地址。
折叠法
将关键字拆分成几个部分，然后将这几个部分组合在一起，以特定的方式进行转化形成Hash地址。例如假如知道某图书的SBN号为：8903-241-23，可以将address(key)=89+03+24+12+3作为Hash地址。
除留取余法
如果知道Hash表的最大长度为m，可以取不大于m的最大质数p，然后对关键字进行取余运算，address(key)=key % p。
在这里p的选取非常关键，p选择的好的话，能够最大程度地减少冲突，p一般取不大于m的最大质数。
Hash表大小的确定
Hash表大小的确定非常关键，如果Hash表的空间远远大于最后实际存储的记录个数，就会造成较大的空间浪费。如果选取小了的话，则容易造成冲突。在实际情况中，一般需要根据最终记录存储个数和关键字的分布特点来确定Hash表的大小。还有一种情况时可能事先不知道最终需要存储的记录个数，则需要动态维护Hash表的容量，此时可能需要重新计算Hash地址。
冲突的解决
如果产生了Hash冲突，就需要办法来解决，通常有如下两种方法：
开放定址法
即当一个关键字和另一个关键字发生冲突时，使用某种探测技术在Hash表中形成一个探测序列，然后沿着这个探测序列依次查找下去，当碰到一个空的单元时，则插入其中。比较常用的探测方法有线性探测法，比如有一组关键字 {12，13，25，23，38，34，6，84，91}，Hash表长为14，Hash函数为address(key)=key%11 ，当插入12，13，25时可以直接插入，而当插入23时，地址1被占用了，因此沿着地址1依次往下探测(探测步长可以根据情况而定)，直到探测到地址4，发现为空，则将23插入其中。
链地址法
采用数组和链表相结合的办法，将Hash地址相同的记录存储在一张线性表中，而每张表的表头的序号即为计算得到的Hash地址。如上述例子中，采用链地址法形成的Hash表存储表示为：
Hash表的平均查找长度
Hash表的平均查找长度包括查找成功时候的平均查找长度和查找失败时候的平均查找长度。
查找不成功时的平均查找长度相当于在表中查找元素不成功时的平均比较次数，可以理解为向表中插入某个元素，该元素在每个位置都有可能，然后计算出在每个位置能够插入时需要比较的次数，再除以表长即为查找不成功时的平均查找长度。
例
这里我们将关键字序列{7,8,30,11,18,9,14}散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，长度为10，即{0,1,2,3,4,5,6,7,8,9}.散列函数为：H(key) = (key * 3) % 7，处理冲突采用了线性探测再散列法。
Step 1 求散列表
H(7) = (7*3)%7 = 0
H(8) = (8*3)%7 = 0
H(30) = (30*3)%7 = 6
H(11) = (11*3)%7 = 5
H(18) = (18*3)%7 = 5
H(9) = (9*3)%7 = 6
H(14) = (14*3)%7 = 0
按关键字序列顺序依次向哈希表中填入，发生冲突后按照“线性探测”探测到第一个空位置填入。
H(7) = 0，key = 7应插在第0个位置，因为第0个位置为空，可以直接插入。
H(8) = 3，key = 8应插在第3个位置，因为第3个位置为空，可以直接插入。
H(30) = 6，key = 30应插在第6个位置，因为第6个位置为空，可以直接插入。
H(11) = 5，key = 11应插在第5个位置，因为第5个位置为空，可以直接插入。
H(18) = 5，key = 18应插在第5个位置，但是第5个位置已经被key=11占据了，所以往后挪一位到第6个位置，但是第6个位置被key=30占据了，再往后挪一位到第7个位置，这个位置是空的，所以key=18就插到这个位置
H(9) = 6，key = 9应插在第6个位置，但是第6个位置已经被key = 30占据，所以需要往后挪一位到第7个位置，但是第7个位置已经被key = 18占据，所以再往后挪移到第8个位置，这个位置是空的，所以key = 9就插到这个位置。
H(14) = 0，key = 14应插在第0个位置，但第0个位置已被key=7占据，所以往后挪移一位到第1个位置，这个位置是空的，所以key=14就插到这个位置。
最终的插入结果如下表所示：
address 0 1 2 3 4 5 6 7 8 9
key 7 14 8 11 30 18 9
Step2 求查找成功的平均长度
查找7，H(7) = 0，在0的位置，一下子就找到了7，查找长度为1。
查找8，H(8) = 3，在3的位置，一下子就找到了8，查找长度为1。
查找30，H(30) = 6，在6的位置，一下子就找到了30，查找长度为1。
查找11，H(11) = 5，在5的位置，一下子就找到了11，查找长度为1。
查找18，H(18) = 5，第一次在5的位置没有找到18，第二次往后挪移一位到6的位置，仍没有找到，第三次再往后挪移一位到7的位置，找到了，查找长度为3。
查找9，H(9) = 6，第一次在6的位置没找到9，第二次往后挪移一位到7的位置，仍没有找到，第三次再往后挪移一位到8的位置，找到了，查找长度为3.
查找14，H(14) = 0，第一次在0的位置没找到14，第二次往后挪移一位到1的位置，找到了，查找长度为2。
所以，查找成功的平均查找长度为(1 + 1 + 1 + 1 + 3 + 3 + 2) / 7 = 12 / 7
Step3 求查找不成功的平均查找长度
查找不成功，说明要查找的数字肯定不在上述的散列表中。
因为这里哈希函数的模为7，所以要查找的数的初始地址只可能位于0~6的位置上。
地址0，到第一个关键字为空的地址2需要比较3次，因此查找不成功的次数为3。比如要查找的数为28，H(28) = (28 * 3) % 7 = 0。即28对应的地址是0，由于存放在0位置的数是7，所以往后挪移一位，发现在1位置存放的数是14，继续往后挪一位，发现位置2上没有数。至此就知道28不在这个哈希表里，即查找28失败。
地址1，到第一个关键字为空的地址2需要比较2次，因此查找不成功的次数为2。
地址2，到第一个关键字为空的地址2需要比较1次，因此查找不成功的次数为1。
地址3，到第一个关键字为空的地址4需要比较2次，因此查找不成功的次数为2。
地址4，到第一个关键字为空的地址4需要比较1次，因此查找不成功的次数为1。
地址5，到第一个关键字为空的地址9需要比较5次，因此查找不成功的次数为5。
比如要查找的数为4，H(4) = (4 * 3) % 7 = 5，所以从地址5开始查找，最终发现地址5、地址6、地址7、地址8上存放的数都不是5，并且地址9的位置上没放数据，至此可知5不在这个哈希表里。
地址6，到第一个关键字为空的地址9需要比较4次，因此查找不成功的次数为4。
所以，查找不成功的平均查找长度为（3 + 2 + 1 + 2 + 1 + 5 + 4）/ 7 = 18 / 7
作者：Paul 5/28/2019
