java - Java中如何从这个ArrayList中快速知道海量ArrayList中的索引？

Question

假设我在 Java ArrayList 中有 5000 万个不同字符串的集合。让foo是一组 4000 万个任意选择(但固定)的字符串，来自之前的集合。我想知道 foo 中每个字符串的索引在数组列表中。

一个明显的方法是遍历整个 ArrayList，直到我们在 foo 中找到第一个字符串的匹配项。 ，然后是第二个，依此类推。然而，这个解决方案将花费非常长的时间(同时考虑到 5000 万是我为示例选择的任意大数，集合可能在数亿甚至数十亿的数量级，但这是从一开始就给出的并且保持不变)。

然后我想到使用固定大小为 5000 万的哈希表来确定给定字符串在 foo 中的索引。使用 someStringInFoo.hashCode() .但是，根据我对 Java 哈希表的理解，如果调用 hashCode() 时发生冲突，这似乎会失败。将为两个不同的字符串生成相同的索引。

最后，我考虑先用 sort(List<T> list) 对 ArrayList 进行排序在 Java 的集合中，然后使用 binarySearch(List<? extends T> list,T key,Comparator<? super T> c)获取术语的索引。是否有比这更有效的解决方案，或者这已经是最好的解决方案了吗？

Answer 1

您需要为搜索字符串而优化的额外数据结构。它会将字符串映射到它的索引。这个想法是您迭代原始列表以填充您的数据结构，然后迭代您的集合，在该数据结构中执行搜索。

你应该选择什么样的结构？

有三个选项值得考虑:

• Java 的 HashMap
• TRIE
• Java IdentityHashMap

第一个选项实现起来很简单，但并不能提供最好的性能。但是，它的填充时间 O(N * R) 优于对列表进行排序，即 O(R * N * log N)。搜索时间比在排序的字符串列表中更好(与 O(R log N) 相比，分摊 O(R)。其中 R 是字符串的平均长度。

第二个选项始终适用于字符串映射，为 O(R * N) 的情况提供保证的填充时间，并保证 O(R) 的最坏情况搜索时间。它的唯一缺点是 Java 标准库中没有开箱即用的实现。

第三个选项有点棘手，只适合您的情况。为了使其工作，您需要确保第一个列表中的字符串在第二个列表中按字面意义使用(是相同的对象)。使用 IdentityHashMap 消除了 String 的相等成本(上面的 R)，因为 IdentityHashMap 按地址比较字符串，仅采用 O(1)。人口成本将摊销 O(N) 和搜索成本摊销 O(1)。因此，该解决方案提供了最佳性能和开箱即用的实现。但是请注意，此解决方案仅在原始列表中没有重复项时才有效。

如果您有任何问题，请告诉我。