在ArrayList中查找对象索引的有效方法

Question

我有一个ArrayList，从ArrayList的末尾（即使用add（object）方法）以串行方式（即逐个）填充Integer类型的对象。每次我这样做，ArrayList中的其他对象都会左移一个索引。

在我的代码中，我想在ArrayList中找到一个随机对象的索引。我想避免使用indexOf方法，因为我有一个非常大的ArrayList，循环将花费大量时间。有什么解决办法吗？如何在某些数据结构中保留ArrayList中对象的索引？

编辑：显然我的问题不清楚，或者我对arraylist有误解。添加（对象）方法（这也是很可能的！）。我想做的是有一个类似滑动窗口的东西，对象插入arraylist的一端，然后从另一端删除，当一个对象插入到一端时，其他对象将移动一个索引。我可以使用arraylist。添加（0，object），从arraylist的左侧插入对象，每次将之前的对象右移一个索引，但在google搜索时，我发现这是一个处理非常密集的操作-如果我记得正确的话，是O（N）。因此，我想“好吧，让我们插入arraylist右端的对象，没问题！”，假设每次插入都会将之前的对象移动一个索引（这次向左）。

此外，当我使用术语“索引”时，我只是指对象在ArrayList中的位置-也许还有一些更正式的术语“索引”，它的意思不同。

Answer 1

你有几个选择。以下是两个基本选项：

>

如果它适合您的情况，并且映射不符合您的性能要求，则可以向对象添加索引字段，并在将其添加到数组时直接存储索引。从一开始删除元素时，必须遍历列表中的所有对象，并从其索引中减去一个对象。然后，您可以在给定对象的固定时间内获得索引。

这些仍然有在删除后更新索引的性能影响。现在，在您选择其中一个选项后，如果您进行简单的改进，您可以避免在删除后遍历map/list进行更新：

不要存储每个对象的索引，而是存储到目前为止添加的对象总数的计数。然后要获得实际索引，只需从您要查找的对象的值中减去第一个对象的计数值。例如，当您添加：

add a to end;
a.counter = counter++;
remove first object;

（启动程序时计数器的初始值并不重要。）然后要找到一个对象“x”：

index = x.counter - first object.counter;

您是将计数器存储为新字段还是存储在地图中取决于您。希望有帮助。

顺便说一句当从列表前面删除对象时，链表的性能会更好，但当通过索引访问对象时，性能会更差。这可能更合适，这取决于添加/删除与随机访问之间的平衡（如果您只关心索引，但实际上不需要按索引检索对象，那么随机访问性能并不重要）。如果确实需要进一步优化，可以考虑使用固定容量的环形缓冲区（后插入、前移除和随机访问都是O（1））。

当然，选项3是在更高的层次上重新考虑你的算法；也许有一种方法可以完成你正在寻找的行为，而不需要找到列表中的对象。