在 Java 中将对象映射到整数 - 使用数组或 Map

Question

我有需要映射到整数（或原始整数）的对象。

所以例如

Object[] objects = new Object[X];
objects[2]=o1;
objects[34]=o2;
objects[126]=o3;
...

所以我的键范围从 0 到 X，但只需要几个（假设 20 个）映射对。（映射只做一次，不会改变）

使用Map（以及哪种实现最适合）而不是大多数未使用的"大型"数组是否是一个更好的主意（性能和内存使用量）。

所需的范围实际上可能会在开发过程中扩大 - 所以如果它只对非常大的 X 很重要，那对我来说仍然很有趣。（目前 X 是 256 - 所以相当小）

总而言之：我想在 Java 中有效地将数字映射到对象。

Answer 1

使用地图。

性能差异应该可以忽略不计。 假设当你说"性能"时，你指的是查找（正如你所说，映射只完成一次，不会改变），使用直接数组查找的性能会更好。 使用数组时，您的预期查找将O(1) 。 如果您有地图并使用整数作为键，则查找应O(1)预期情况和最坏情况O(n)。 鉴于您提到的对数量很少（20），性能差异不会很大。

但是，Map 的内存使用率会明显更好，因为数组将稀疏填充。

更新

感谢所有提供评论和反馈并帮助我学习的人。 @JohnnyO说数组查找是正确的O(1)，我根据他的反馈更正了我的帖子。 我一直在想ArrayList。

Answer 2

是

使用最快的可能性（数组）还是HashMap取决于您的应用程序。您是否每秒有数百万次计算（数组访问）？是的，然后拿起数组，并花费 1k 的内存。
奥赫怀斯拿着地图。
但是，如果 x 很大，还有第三种解决方案：此解决方案几乎与地图一样快（可能更快），但使用的空间更少：
使用 int 的排序数组作为对象数组的索引：

int[] idx ={2, 34, 126}
Object[] objs = {o1, o2, o3};

Idx 必须按升序排序。现在获取键 34 的对象：

int pos= Arrays.binsearch(34, idx); // params might be wrong, please correct
Object o = objs[pos];

但是，我只会将其用于具有最小存储空间要求的大量对象，其中对象在运行时不会更改。

Answer 3

我会使用Map，因为这确实是它的目的。除此之外，使用 Map 可能会使您的代码在未来更容易更新和管理。至于你应该使用哪种实现，在我看来，一个HashMap就足够了，尽管如果你想保持整数键的顺序，你可能还需要考虑一个TreeMap。

Answer 4

该数组显然会为您提供最快的访问速度，但是如果您有这样的间隙，您将浪费相当多的空间。

如果您正在寻找一种灵活的数据结构，将键（例如整数）与值相关联，其中范围可能存在间隙，并且以后可能会增加它，我想不出比 Map 更合适的东西了。 如果您确切地知道计划插入多少元素，则可能需要调查 HashMap 等实现的构造函数参数，这使您可以调整基础存储的大小，以减少空间和冲突。

Map 的另一个结果是，如果您需要使用它执行其他面向集合的任务，您将获得更丰富的 API。

Answer 5

正如你所说，地图是做到这一点的好方法。我通常使用哈希映射，因为它非常快。虽然没有数组快。如果每个值只有一个键，您甚至可能希望使用 HashSet，因为它将确保每个键只使用一个值。

android API有一个叫做SparseIntArray的东西，它应该有更好的性能，但我还没有在标准的java API中看到它。

如果性能真的很重要，你可能会发现 trove 库有一个合适的稀疏数组或映射。只有当你使用原语时，它才会更快（在你的例子中你是）

Answer 6

你真正想要的是一个SparseArray。 它是法线贴图和数组之间的折衷。

如果您正在为 Android 开发，则可以使用一个（请参阅下面的链接）。 否则，您可能会找到可用的实现。

http://developer.android.com/reference/android/util/SparseArray.html

Answer 7

我会推荐一张地图，原因只有一个：长度可变。跟踪您需要如何映射的对象可能会变得相当乏味。使用 HashMap 或类似的实现将保证映射对象中始终具有足够的容量。除此之外，使用 Map 更有意义，因为这是旨在做的事情，使您的代码对其他人更具可读性。我想原始数组会占用更少的内存，但实际上，地图的开销对于您所说的比例尺来说并不是很重要。