Question

显然，（图 12 右侧抽象概念中的）“键/值”作为抽象系统，的确可以让我们通过标识找到值。我们甚至可以为 索引数组在这个系统上的抽象 定义一个函数——换言之，索引数组也就是这个系统的一个特例：

1 2 3 4

// 索引数组是以下标为标识的、自映射的一个“名/值”数据系统 function hash_index_array(i) { return i; }

但是我们也发现正因为索引数组是自映射的，所以它的映射关系是一对一的（传入 i ，返回 i ），而此前的 hash_sum_16() 却是多对一的，例如 'OrderNum' 映射为 12，但如果传入标识 'Order' ，其映射的结果也会是 12。

因此我们面临要在同一个位置上放两个或者更多数据的情况。这就是 哈希冲突（哈希碰撞，hash collision） 。对此我们可以增大哈希表的长度，但即使它超过可能的哈希键个数，（在不同的算法下）仍然存在冲突的可能。既然我们承认冲突必然存在，因此在找到 Value 之后再做一次验证就是必需的了。这里的验证也有许多种做法，其中之一是用某种新算法再做一次 Hash() 。尽管两个不同的 Key 在两种不同的 Hash() 之后仍然相同的机率相当低，但是——仍如此前所述的——还是必然会存在。所以最终的一个步骤通常还是对 Key 的直接识别，例如字符串的逐字符比较，或者数据存储区块的逐字节比较，或者基于顺序存储的、区块地址的比较。这种情况下，数据区必须保留原始的 Name/Key 值，如图 13 所示。

图 13　验证：保留 Name/Key 的原因

有两种特殊情况，其一是元素在系统中不一定完全出现，但其可能值是预知的，例如一周的七天；其二是元素总是会完全出现在系统中，例如键盘上的所有键。这两种情况所面临的数据集都是有限的，对此我们仍有机会设计一个函数来使得每一个 Key 所计算的 Code 都保持唯一。这样的哈希表是静态大小的，其长度为数据集范围的上限，即：

Get_Length(Hash_Buckets)　==　Get_Element_Count(Data_Set)

这其实是为每个元素创建了唯一的哈希码映射，只需要比对哈希码值即可确认数据，也因此就无须再保留原始的 Name/Key 值了。这同时也节省了图 13 中最后一步比对 Name/Key 的开销。