Java HashMap 与 int[]

Question

我有一个大小为 10000 的整数数组，它逐渐被其他整数填充(上下文: http://uva.onlinejudge.org/external/1/100.pdf )，但它不够大。我打算用 HashMap 替换它，并且想知道这是否比任意增大数组(例如将大小增加到 100000)更好？

此外，HashMap 和整数数组之间的主要区别是什么？

注意在这种情况下，HashMap/数组中仅使用奇数键。

Answer 1

显然，两者都提供了从整数子集到整数的映射。有几个区别，但简短的答案是数组可能更适合密集键，而 HashMap 更适合稀疏键。

对于数组，您使用的每个键的内存成本将为 32 位，但对于 HashMap 来说是数倍。对于该范围内但不使用的每个键的内存成本对于数组来说也是 32 位，但对于 HashMap 来说可能接近于零。

数组访问将比 HashMap 访问更快。

如果您希望使用多达 50% 的条目，那么使用数组会更好。如果只需要奇数键，并且数组很大，可以考虑使用数组索引(i-1)/2来表示键为i的元素。

找到更适合您情况的最佳方法(包括找到在它们之间切换的密度阈值)是通过测试。这是我要遵循的程序:

1. 为数据结构定义一个接口(interface)，其中包含您需要能够对其执行的操作的方法。
2. 仅根据该接口(interface)编写代码，但实际创建结构除外。
3. 定义两个类，每个类都实现该接口(interface)，一个使用数组，另一个使用 HashMap。
4. 使用每个类进行测量。对于 HashMap，您还可以尝试使用 HashMap 构造函数参数。