程序原本(四十一):程序设计的核心思想——数据结构:散列存储(Key:对名字不可或缺的验证)

阅读数:40 2019 年 9 月 28 日 18:30

程序原本(四十一):程序设计的核心思想——数据结构:散列存储(Key:对名字不可或缺的验证)

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

复制代码
// 索引数组是以下标为标识的、自映射的一个“名 / 值”数据系统
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:对名字不可或缺的验证)

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

复制代码
Get_Length(Hash_Buckets) == Get_Element_Count(Data_Set)

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

评论

发布