java - 使用带有整数(索引)作为键的 HashMap 与使用 ArrayList

Question

所以我目前正在用 Java 复制我自己的 Pokemon 版本。我最近才熟悉更高级的数据结构，我仍然不确定什么时候应该比另一个更合适。

基本上，我想存储一个 Pokedex(Pokemon 的数据库)，而 HashMap 似乎是最合适的。键是 Pokemon 的 pokedex # ，值是相关的 Pokemon 对象。但是，由于图鉴的性质，这意味着每个神奇宝贝的图鉴 # 只是它们在图鉴中的各自索引。

我的问题是当键只是索引值时使用 HashMap 是否有意义，或者将 Pokedex 存储为 ArrayList(甚至数组)是否更有意义，其中每个 Pokemon 都存储在其各自的索引处？

显然，如果我还没有为每个 Pokemon 创建定义，那么 ArrayList 将是内存效率低下的，因为我们必须为每个 pokemon 保留空间，但据我所知，hashmaps 中的键应该用于创建哈希值而不是直接索引，对吗？还是无论如何都合适？

Answer 1

这真的取决于。映射为您提供了更高的自由度，而列表/数组可能会迫使您承担使用此类线性/顺序数据结构的后果。

然后，这取决于填充数组的“稀疏”程度。如果“keys”在 0 到 1000 之间，有很少或没有未使用的槽，那么列表就可以了。如果键从 0 到 1000 万，并且大多数槽都是空的:使用映射。或者针对稀疏矩阵优化的数据结构。

除此之外，请记住数组不包含对象本身的内存，仅包含指向它们的引用。所以数组的内存占用是相同的，无论槽是空的还是指向某处。