在 Map 变得比数组更高效之前需要存储多少项

Question

我觉得这个问题可能应该在某个地方得到解答，但我没能找到。我正在处理一些遗留代码（第一份工作），我遇到了一个问题，其中地图被用来存储恰好 23 个变量（根据我对代码的理解，这个数字永远不会改变）。从根本上说，我理解地图的访问时间是 O(1)，但我总是听说在处理地图时会有一些开销。

所以我的问题是在什么时候使用地图会变得更有效率，而不仅仅是拥有一个存储这 23 个值的数组。我想基本上我会在代码中创建自己的映射，每当我需要存储 xValue 时，我只需访问我知道存储 xValue 的数组。

地图的开销是否太小以至于我想多了？我认为代码的可读性对于地图来说可能更容易一些，因为所使用的键本质上是对 xValue 是什么的描述。

Answer 1

使用映射（或字典）不太可能比直接数组访问更快。也就是说，如果您知道恰好有 N 个项目并且知道这些项目是什么，则可以创建一个数组和常量来说明每个项目在数组中的位置。例如（伪代码）：

const NumItems = 22
const ItemType1 = 0
const ItemType2 = 1
const ItemType3 = 2
...
const ItemType22 = 21

Array myItems[22]

然后，如果要访问项目类型 15 的值，只需 myItems[ItemType15]。

此方法的缺点是您必须为每个可能的项目之一存储 space。因此，如果您有 20,000 个项目而不是 23 个，则必须分配数组以容纳所有 20,000 个可能的项目。并创建常量来定义每个项目类型的存储位置。

地图可让您保存 space，但会消耗一些内存。每项开销可能是数组每项成本的两倍或三倍。但是，如果您有大量可能的项目，但一次只会有几十个，那么地图的内存效率更高。假设您要从 20,000 件中挑选 30 件。一个完整的阵列需要您存储 20,000 个项目。该地图可能会花费您 90 个项目的存储空间（是 30 个项目阵列成本的三倍）。

这里的重点是地图以速度换取存储space。地图可以存储整个项目的子集比数组更有效，但它需要更多时间来访问单个项目。

所以真正的问题不是 "which is faster,"，而是地图提供的 space 节省是否值得额外的处理时间。在你的情况下，你只有少数项目中的每一个，使用地图没有任何优势。

在 Map 变得比数组更高效之前需要存储多少项

How many items need to be stored before a Map become more efficient than an array

arrays

data-structures

maps