程序原本(四十二):程序设计的核心思想——数据结构:散列存储(万法归一:索引数组是关联数组的特例)

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

程序原本(四十二):程序设计的核心思想——数据结构:散列存储(万法归一:索引数组是关联数组的特例)

曹冲称象本质上是通过一个系统将大象的重量映射为石头的重量,而哈希算法正是这样一个系统。对于象与石头的重量来说,这个映射关系是确定的、一对一的,因此刻度也就只需要简单地核对,而无须“原始的象”来参与复核。

但在另一个故事中,楚人为什么就失败了呢?

因为哈希算法的背景变了。需要留意的是,楚人的哈希算法:

  • 求掉落位置之于船体的相对位置

没变。算法的结果 HashCode:

  • 刻度

在整个过程中也没变,但是楚人计算刻度时的背景是船体,使用刻度(下水找剑)时的背景却是整条河。所以“名 / 值”数据系统与其存储背景有着相关大的关系,“必须在相同背景下创建与维护哈希表”是一种系统负担,这种负担通常是由语言或某种硬件装置4来维护的。

4 这是安全令牌、加密盾等实时密码发生装置的基本原理。

对于在某种特定背景下建立的一种“名 / 值”关系型的数据系统,我们称为关联数组(associative array)。这种抽象的数据结构在基于地址存取的机器中应用时,面临的核心问题是:

作为名字的字符串存在无限的组合,这与有限的地址空间是矛盾的。

而哈希机制 / 算法通过将“名 / 值”映射为“Key/Code/Value”的关系,从而解决了上述问题。这一映射关系是“哈希算法 + 存储背景”来约束的,这既是系统负担,但也使系统从根本上避免了刻舟求剑的笑话。

解决了与地址空间的矛盾之后,关联数组得以在顺序机器中实现。它在物理上仍然能够满足顺序存储的需要,但从逻辑上却分离了名字(标识)存储与值存储的关系。而我们知道,标识与值是数据最重要的两个性质。

总的来说,如今我们在计算世界里使用的数据表示方法只有两种,即关联数组和索引数组。无论是在抽象概念还是具体实现上,索引数组都可以视为关联数组的特例,既有存储限制,也有存储限制带来的名称 / 标识限制。

评论

发布