Python数据结构与算法——第四十课散列表（哈希表）

　　下面是一张数学成绩表，用元素是元组的列表输入电脑，然后测试查询。

李小明　98

张天成　89

李丹丹　88

黄长陆　91

张明贵　95

李华国　82

　　　　程序代码：

　　运行结果：

　　可见，为了查询某个人的成绩，需要比较表中在他之前的名字，查询效率很低。如果有办法通过名字计算出他的成绩在列表中的下标，就不用比较，直接取出成绩了。把名字都作为变量，变量的值是列表中的下标。

　　程序代码：

　　运行结果：

　　上面把字符串作为变量的名称，从而达到通过字符串计算出数据的存放的下标。但字符串太多，而且也不是所有的字符串都可以作为变量名称，因此这种计算办法适用性很低。为了解决这个问题，哈希提出一种能把所有字符串计算出一个整数值的函数，这个函数就称作哈希函数（Python中是hash(str)），函数的值就是哈希值。下面程序计算出成绩表中姓名的哈希值。

　　程序代码：

　　运行结果：

　　可见，在程序运行过程中，字符串的哈希值是保持不变的。不过程序退出后，再运行就不一样了。下面是第二次运行的结果：

　　可见这数的绝对值都很大，如何才能使它与下标（0~5）对应呢？最简单和直接的办法就是取6的余数了。

　　程序代码：

　　运行结果：

　　从结果上看，下标2没用，下标5要放2个数据。没放数据的，空着（Python列表需要添加None），关键是如何解决一个下标要放多于1个数据的情况。其中一个简单的办法就是用单向链表来解决。第一个放进去的是链表头，以后就添加到链表尾。总体上看，这个表的每一行可以有不同数量的数据，也就是说列不定长，与普通的二维数组不一样，所以我们把这个表叫做散列表，为了纪念哈希（Hash）在这方面的突出贡献，也叫做哈希表（Hash Table）。

　　一般地，这种下标的计算方法称作散列函数，散列函数是一个单值函数。取余数这个方法，是比较常用的，叫做除法散列法；常用的散列函数还有平方根散列法和斐波那契散列法。散列函数的自变量称作键，函数能把键转化为下标（自然数）。散列函数不一定是单调的函数，也就是说，通过散列函数的值是无法推测键的值，这就是一个数组下标可能要储存多个数据的原因。下面用散列表法实现成绩查询。

　　程序代码：

　　运行结果：

　　散列函数不一定要使用哈希值，例如上面6人中，只有3种姓，如果按姓来放位置，那只要长度是3的散列表。散列函数也要做修改。

　　程序代码：

　　可见，散列函数是自然数值域的单值函数就行，不一定要使用字符串的哈希值。从外部调用来看，散列表(Hash Table，也称哈希表)，是根据关键词（Key Value）直接进行访问的数据结构。Python的字典（dict）也是一种是根据关键词（Key Value）直接进行访问的数据结构。其实，它就是通过散列表来实现的。下面就用字典（dict）来演示散列表的使用方法。

　　编程实现投票，每个名字只能投票一次。

　　程序代码：