在之前的（一）顺序查找和（二）二分查找中我们都是基于数据在列表中存储的索引位置查找的，本文所要说的是基于hash表的查找
【hash表】又名散列表，是一种根据关键码寻找值的数据映射结构。哈希表的每个位置，通常称为槽，对应存储一个项，由0开始，如图所示是一个size为10的哈希表，最初每个槽中没有值，均为None.
【hash函数】又称为散列函数，是数据值与哈希表之间的映射函数。哈希函数接收数据值，返回值结余0和size-1之间的整数（槽名范围内），在上述哈希表中，返回的哈希值就必须介于0-9之间。下面介绍一下常见的哈希函数：
（1）余数法
将数据值除以表的大小size，所得余数即为该数据值对应的槽的位置
H(item)=item%size
将数据25,38,46,12,31按照余数法插入到上述哈希表中，则有如下
25%10 |
5 |
38%10 |
8 |
46%10 |
6 |
12%10 |
2 |
31%10 |
1 |
余数法存在的问题是，如果输入数据86，余数6，和46所在槽冲突。如果要避免冲突就要尽可能提供多点槽，这样又存在资源利用率不高，因此下面几种方法就是做到最大程度减少冲突
（2）分组求和法
将项划分为相等大小的块（最后一块可能不是相等大小）。然后将这些块加在一起以求出散列值。例如，如果我们的项是电话号码 436-555-4601，我们将取出数字，并将它们分成2位数（43,65,55,46,01）。43 + 65 + 55 + 46 + 01，我们得到 210。我们假设哈希表有 11 个槽，那么我们需要除以 11 。在这种情况下，210％11 为 1，因此电话号码 436-555-4601 散列到槽 1 。一些分组求和法会在求和之前每隔一个反转。对于上述示例，我们得到 43 + 56 + 55 + 64 + 01 = 219，其给出 219％11 = 10
（3）平方取中法
首先求数据值得平方，然后提取一部分数字结果。例如，如果项是 44，我们将首先计算 44^2 = 1,936 。通过提取中间两个数字 93 ，我们得到 5（93％11）
（4）利用ascii码（字符串）
对于字符串，求其散列值可以将字符串理解为一个字符构成的序列，而每个字符对应一个ascii值，因此字符串也可以理解为ascii的序列。利于求H('cat')，在ascii码中，
得出三个字符的ascii值后，相加99+97+116=312，再利用余数法求出散列值312%10=2，见【代码1】
值得注意的是，这种基于ascii码的哈希函数对于字符组成相同的得出的散列值是一样的，即同样存在冲突问题，例如利用【代码1】求出的‘team’和‘meat’相同。
解决方式：可采用字符位置座位权重，例如，cat可采用99*1+97*2+116*3==641,641%10=1，见【代码2】
【代码1】
#利用ascii码（字符串）def hashSearchByAscii(str,tablesize): sum=0 for s in str: sum=sum+ord(s) return sum%tablesizeprint(hashSearchByAscii('cat',10))
【代码2】
#利用ascii码（字符串）+字符的位置权重def hashSearchByAscii2(str,tablesize): sum=0 for i in range(len(str)): sum=sum+ord(str[i])*(i+1) return sum%tablesizeprint(hashSearchByAscii2('team',10))print(hashSearchByAscii2('meat',10))print(hashSearchByAscii2('cat',10))