Direct-address tables与常用的数组是同一种数据结构吗？

直接寻址表和数组并不完全等同，二者属于不同层级的概念：数组是底层通用存储结构，直接寻址表是基于数组实现的、有特定使用约束的逻辑数据结构。

二者的核心联系 #

• 直接寻址表的底层必须基于数组实现，它完全依赖数组按下标随机访问的O(1)时间复杂度特性，来实现同等效率的查找、插入、删除操作。
• 当数组被按照直接寻址的规则使用时，二者在实际使用场景中经常被近似指代。

二者的核心差异 #

• 定位不同：数组是通用的线性存储结构，下标仅代表元素的存储位置，本身不携带业务语义。你可以用数组存储任意类型、任意顺序的元素，下标和元素的业务属性没有强制关联；而直接寻址表是特定场景下的逻辑结构，要求它的下标直接对应业务数据的键（key），下标本身就携带业务语义。
• 使用约束不同：数组没有使用前提限制，只要内存足够即可申请任意长度的数组存储任意内容；直接寻址表有严格的使用前提：业务键的取值必须是可直接映射为整数的连续小范围集合，否则会出现大量空间浪费，甚至无法实现。
• 举个具体的区分示例：

假设你需要统计某校所有高三学生的模考分数（满分100，仅取整数）对应的人数：

1. 如果你申请长度为101的数组count，用分数作为数组下标，对应位置存储该分数的人数，此时这个count数组就是直接寻址表，下标直接对应业务键（分数）。
2. 如果你申请长度为101的数组temp，随便用它存储你临时计算的101个中间值，下标和业务数据没有任何关联，此时它只是普通数组。

简单总结：所有的直接寻址表都用到了数组，但不是所有的数组都属于直接寻址表。

内容的提问来源于stack exchange，提问作者Kain