Java HashMap<Integer，Integer>和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. 为数据结构定义一个接口，该接口具有您需要在其上执行的操作的方法。
2. 编写您的代码，除了结构的实际创建之外，只使用该接口。
3. 定义两个类，每个类实现接口，一个使用数组，另一个使用HashMap。
4. 使用每个类进行度量。对于HashMap，还可以尝试使用HashMap构造函数参数。

Answer 2

数组是值的列表。int数组是整数的列表。您可以按索引访问元素。

一张地图。散列映射是: key -> value。在散列映射中，您可以通过键检索值。

public class Book{}

HashMap<String, Book> books = new HashMap<String, Book>(); // mapping from a string(=key) to a Book object(=value)
books.put("Harry Potter", new Book());
// etc.

因此，如果您希望通过键访问元素，则需要一个散列映射。键必须是不可变的(如int或string)，所以选择最适合您的。