Question

使用“名/值”关系来确立的数据抽象系统，既有可能确切地找到数据，例如曹冲称象；也有可能找不到数据，例如刻舟求剑。但是这一抽象准确地反映了计算系统的真相：找到数据，计算。

本质上来说，索引数组也是这一抽象下的产物，只不过我们是使用 可顺序索引的地址 来找到数据罢了——地址，也可以视为数值体系下的标识或命名。而我们现在，只不过要假设命名的方式不再是地址，而是一个真实的、可以被自然语言理解的“名字”，例如字符串。

第一个问题。在索引数组中的地址是有限大小的，它与我们的计算系统的存储一一对应，因此使用地址来指示一个数据时，不可能因为越出存储边界而找不到数据。但是我们使用字符串来命名数据的时候，就不能确保数据与存储的这种关系：我们有无穷的方式来生成名字，也就意味着它对应一个无穷尽的数据集合。而这是无法被一个物理的、现实的计算系统——例如计算机——所支持的。

可以用数学方法将一个组合方式无穷的名称集合映射到一个有限的空间中去。这种方法称为 哈希（hash） 。简单地说，它使用一个函数来为每一个名字生成一个有限空间中的索引，例如数字值 2 。这涉及两个问题，其一是映射为数字的索引值；其二是限制在有限空间中。对这两个问题的一种简单的处理，是将字符的编码值求和、取余。例如：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

// JavaScript Syntax /** * 前设: name 是一个顺序存储的字符串 * - 我们可以用 GetStringLength() 函数来获得字符串的字节长度; * - name[i]这种语法形式将 name 作为一个字节数组(byte array) 使用; * - name[i]形式可以取得指定下标 i 的数组元素的数值值，范围为[0...255]. **/ function hash_sum_16(name) { var result = 0, len = GetStringLength(name); for (var i=0; i<len; i++) { result += name[i]; } return result % 16; }

对于某笔订单的基本信息，其字段名的实际运算结果如下：

1 2 3 4

// 计算结果为：12 hash_sum('OrderNum'); // 计算结果为：15 hash_sum('OrderPrice');

图 10 表示上述关系在存储上的映射，亦即是上述字段所对应值分别存储在位置 12 和 15 中：

图 10　一个简单的哈希算法在存储上的映射

这表明我们可以通过 hash_sum_16() 找到 3 ：

• 名为 'OrderNum' 的数据的值为 8；
• 名为 'OrderPrice' 的数据的值为 1202。

由于求模取余之后， hash_sum_16() 的可能值为[0…15]，所以我们能预先分配上述整个索引表区间（16 个基础类型的数据，或者结构体等）。更进一步，我们也可以通过指针来弥补索引表对未定长度数据支持不足的缺憾——这是因为该表本身是一个索引数组，如图 11 所示。

图 11　指针在哈希表上的运用

根据此前的讨论，我们可以保证图 11 中的索引表、数据１与数据２以及整个空间仍然是顺序存储的，进而不会与计算机的物理实现冲突。

在完整的模型描述中，我们称 hash_sum_16() 这类函数为哈希算法或哈希函数（hash function），将名字称为键或哈希键（key，hash key），将索引表称为哈希表或桶（hash bucket），将表中的元素 C₀…C_n称为哈希码（hash code）。图 12 描述了这些抽象关系。

图 12　哈希表的结构与概念间的抽象关系