程序设计导论：Python语言实践

4.4.4　哈希表

哈希表（Hash table）是一种数据结构，它把键分成小的组，可以实现快速查找。其基本思想非常简单：选择一个参数m，把所有的键分成m个组，所有组的大小大致相同。针对每个组，我们使用列表保存键并使用顺序查找算法（即前文讨论的基本实现方法）。

为了实现把键分成小的分组，我们使用一种称为哈希函数（hash function）的函数。哈希函数把每一个可能的键映射为一个哈希值（hash value）——一个位于0到m - 1之间的整数。这使我们可以把符号表建模为一个固定长度的数组，其元素为列表，使用哈希值作为数组索引下标访问需要的列表。在Python中，我们可以使用内置的list数据类型实现固定长度的数组和列表。

哈希算法非常有用，所以许多程序设计语言都包含对它的直接支持。如3.3节所述，Python提供了内置函数hash()用于此目的，函数带一个可哈希的对象作为参数，返回一个整型哈希码。要把可哈希对象转换为0到m - 1之间的哈希值，可以使用如下表达式：

请读者回顾一下，一个对象满足如下条件时则可称为可哈希对象：

·该对象可以与其他对象进行相等性比较

·当两个对象相等时，其哈希码相同

·对象的哈希码在对象的生存期间保持不变

不相等对象的哈希码也可能相同。然而，为了保持良好的性能，我们期望哈希函数把所有的键分成m个长度大致相同的组。

表4-4-6是12个具有代表性的字符串键的哈希码和哈希值，其中m=5。哈希码和哈希值在不同的计算机上可能不同，这是因为不同的计算机上具有不同或随机的hash()实现。 ...