Java：在ArrayList中存储到任意索引的最佳方法

Question

我知道不能在尚未使用过的ArrayList索引处存储值，也就是说，这些索引必须小于ArrayList的大小。换句话说，如果myArrayList.size()为5，则无法将值存储在大于等于5的位置上。

myArrayList.set(10, "Hello World") 

我会收到一个越界错误。但我的应用程序需要这个。除了在每个中间位置存储null的循环之外，是否有更优雅的方法？

在我看来，它看起来像：

- 这种行为在Vector中是相同的。 - 如果我需要能够随机访问（即位置X处的元素），那么我的选择是Vector和ArrayList。 - 我可以使用HashMap并使用索引作为键，但这真的很低效。

那么，对于这种看起来很常见的情况，什么是优雅的解决方案？我一定漏掉了什么...

- pitosalas

---

为什么你说使用地图解决方案效率很低？你对空间需求有多严格？ - Michael Myers

为什么使用HashMap比你提出的ArrayList方式效率低？ - Spencer Kormos

另外，你事先知道最高索引是多少吗？ - Michael Myers

你的应用程序为什么需要这样做？也许与其试图想出方法以未预期的方式使用数据结构，不如考虑另一种解决问题的方式？ - Anthony Grist

请查看“Sparse Array”和https://dev59.com/J3RC5IYBdhLWcg3wKtz2。 - mgaert

哇！太快了。我无法感谢每个人，但你们回答了我的问题！ - pitosalas

Answer 1

我可以使用HashMap并将索引作为键，但那真的很低效。

这取决于你使用的索引是否非常稀疏，如果是，使用Map可能会更好。如果索引倾向于紧密在一起，我认为没有比填充null更好的方法了。只需编写一个实用程序函数，您可以一遍又一遍地使用它，而不是在需要它的每个地方重复循环，类似于以下内容：

private void padTo(List<?> list, int size) {
    for (int i=list.size(); i<size; i++)
        list.add(null);
}

- Steven

---

循环之前考虑调用 list.ensureCapacity(size)，以避免不必要的内存重新分配。 - lxbndr

请注意，ensureCapacity(size) 方法并不会实际上填充数组 - https://dev59.com/3msz5IYBdhLWcg3wv6ju - Aram Kocharyan

Answer 2

你可以使用 Map<Integer, MyClass> 替代。具体来说，如果你使用HashMap，它也将是 O(1)——尽管它会比ArrayList慢一些。

- amit

Answer 3

您可以使用 TreeMap<key, value> 来对键值进行排序，其中按照 value 的自然顺序排序。

您可以将 value 作为索引。您可以插入任何值，它不必按顺序。这似乎是最简单的解决方案。

- Bhushan

---

更多关于此的信息请参考：https://github.com/google/guava/wiki/UsingAndAvoidingNullExplained#specific-cases - Yar

TreeMap按其键排序，而不是值。 - mlecz

Answer 4

听起来你需要一个常规数组：

• 你需要随机访问
• 你想指定一些大的大小

- Bohemian

---

您可以指定 ArrayList 的大小。 - blank

不是这样想。这是初始分配的容量，但在开始时大小为零。 - pitosalas

如果列表中存储的项目是通用的，则常规数组不是一个选项。 - Mark Jeronimus

@MarkJeronimus 这是一个选项，如果您可以忽略未经检查的赋值警告，并完全控制进入该数组的内容以及如何读取它（即您必须进行强制转换）。 - Populus

@MarkJeronimus 嗯？Java 数组有类型，虽然没有通过泛型实现，但仍然是有类型的。例如，String[] 与 Integer[] 是不同的，如果您尝试将错误类型的对象分配给数组元素，则会出现编译错误。除非使用 Object[]，否则不需要或不希望进行转换，但这是显而易见的。 - Bohemian

如果您直接指定一个数组，那么可以这样做，但是当您有一个通用的容器类并且需要数组中的项是通用的（即通用参数），则不能这样做。您可以使用 new ArrayList<T> 但不是 new T[]。请注意，ArrayList 的实现方式是通过存储 Object[] 和大量的丑陋转换来实现的。它们可以使用未经检查的转换，因为数组不应泄漏到外部。（但是，您可以使用反射来破解 ArrayList 并导致 ClassCastExceptions） - Mark Jeronimus

Answer 5

如果你一定要使用列表而不是映射，那么最好重写arraylist的add和set方法，在之前先将索引放入null。在我看来没有其他更好的方法。

- sethu

Answer 6

HashMap可能比你想象的要高效得多，可以试试。否则，我想不出比循环和填充null更优雅的方法了。如果你至少想要一些优雅的表达，那么你可以子类化ArrayList并添加一个expandingSet(position, value)方法来隐藏所有的循环等操作，或者其他什么方法。也许这不是一个选项？如果不是，就在其他地方有一个实用程序方法，但我认为这不太好，尽管它也适用于其他类型的列表...

也许一个包装类会是两全其美的最佳选择，或者它只会带来不必要的开销...

- Elias Vasylenko

Answer 7

如果您正在寻找一个稀疏数组（其中大多数索引将为空），某种类型的 Map（可能是 HashMap）将是最佳选择。任何类似于数组的解决方案都将被强制保留所有空索引的空间，这不是非常节省空间的，而且 HashMap 对于大多数正常用途来说足够快。

如果您最终将数组填满到某个 n，您需要在循环中添加 nulls 以达到所需的索引。您可以通过给它一个最终要存储的元素数量的初始容量来使其更加高效（这样可以防止 ArrayList 需要调整大小）。new ArrayList(n) 将很好地工作。不幸的是，除了在创建时循环添加元素外，没有简单的方法使其具有特定的大小。

- Retief

---

我相信这设置了“容量”而不是“大小”。 - pitosalas

@pitosalas 好的，发现了。正在修复中。 - Retief