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

Question

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

在我的代码中，我想查找ArrayList中随机对象的索引。我想避免使用indexOf方法，因为我有一个非常大的ArrayList，并且循环将花费大量时间。有没有解决方法？一些想法如何保持一些数据结构可能是ArrayList中对象的索引？

编辑：显然我的问题并不清楚，或者我有一个arraylistist.add（object）方法的错误理解（这也是非常可能的！）。我想要做的是让滑动窗口具有滑动窗口，将对象插入到数组列表的一端，并从另一端删除对象，并且当一个对象插入到一端时，其他对象被一个索引移位。我可以使用arraylist.add（0，object）插入来自数组列表左侧的对象，并且每次将前一个对象右移一个索引，但是进行谷歌搜索后，我发现这是一个处理密集型操作 - O（N）如果我没记错的话。因此，我认为“好吧，让我们插入来自数组列表右端的对象，没问题！”，假设每个插入仍然会将前一个对象移动一个索引（这次是左边）。

另外，当我使用术语“索引”时，我只是指对象在ArrayList中的位置 - 也许还有一些更多的小型术语“索引”，这意味着不同的东西。

Answer 1

你有几个选项。这里有两个基本的选择：

1. 可以保持Map<Object,Integer>保存索引，在平行排列。当你向数组追加一个元素时，你可以将它添加到地图中。当你从头开始删除一个元素时，你将不得不遍历整个地图并从每个索引中减去一个元素。

2. 如果它适合您的情况并且Map不符合您的性能要求，您可以将index字段添加到您的对象并将其添加到阵列时直接存储索引。当你从开始移除一个元素时，你将不得不迭代列表中的所有对象，并从它们的索引中减去一个。然后，您可以在给定对象的同一时间内获得索引。

这些仍然有删除后更新索引的性能命中。现在，在您选择其中一个选项后，如果您进行了简单的改进，则可以避免必须在移除后更新地图/列表以更新：

而不是存储每个对象的索引，存储迄今添加的对象总数。然后为了得到实际的索引，只需从你正在查找的那个值中减去第一个对象的计数值即可。例如。当您添加：

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

（的counter初始值启动程序时，其实并不重要。）然后找对象“X”：

index = x.counter - first object.counter; 

无论您存储counter为新的领域或地图取决于你。希望有所帮助。

顺便说一下;当从列表的前面移除对象时，链接列表将具有更好的性能，但通过索引访问对象时会更糟。根据您的添加/删除与随机访问的平衡（如果您只关心索引但实际上不需要通过索引检索对象，随机访问性能并不重要），这可能更合适。如果你真的需要进一步优化，你可以考虑使用固定容量的环形缓冲区（反向插入，前端移除和随机访问都将是O（1））。

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