如何从Java中的这个ArrayList快速了解大量字符串的ArrayList中的索引？
假设在Java ArrayList中有5000万个不同字符串的集合。设foo是一组从上一个集合中任意选择（但固定）的4000万个字符串。我想知道ArrayList中foo中每个字符串的索引
一种显而易见的方法是遍历整个ArrayList，直到在foo中找到第一个字符串的匹配项，然后找到第二个字符串的匹配项，依此类推。然而，这个解决方案需要非常长的时间（同时考虑到5000万是一个任意大的数字，我选择了这个例子，收集的数量可能是数亿甚至数十亿，但这是从一开始就给出的，并且保持不变）
然后我考虑使用一个固定大小为5000万的哈希表，以便使用someStringInFoo.hashCode()确定foo中给定字符串的索引。然而，从我对Java哈希表的理解来看，如果发生冲突，这将失败，因为调用hashCode()将为两个不同的字符串生成相同的索引
最后，我考虑了首先使用Java集合中的sort(List<T> list)对ArrayList进行排序，然后使用binarySearch(List<? extends T> list,T key,Comparator<? super T> c)获得术语的索引。有没有比这更有效的解决方案，或者这是最好的解决方案
# 1 楼答案
您可以毫无问题地使用Java哈希表。根据Java文档，“在发生“哈希冲突”的情况下，单个bucket存储多个条目，必须按顺序搜索。”
我认为您对哈希表的工作方式有误解。哈希冲突不会破坏实现。哈希表只是一个链表数组。每个键通过一个散列函数来确定数组中元素将被放置的索引。如果发生哈希冲突，元素将被放置在哈希表数组中索引处的链表末尾。请参阅下面的链接以获取示意图
# 2 楼答案
您需要为搜索字符串而优化的附加数据结构。它将把字符串映射到它的索引。其思想是迭代填充数据结构的原始列表，然后迭代集合，在该数据结构中执行搜索
你应该选择什么结构
有三种选择值得考虑：
第一个选项易于实现，但不能提供最佳性能。但是，它的填充时间O（N*R）比排序列表要好，排序列表是O（R*N*logn）。搜索时间优于排序字符串列表中的搜索时间（摊销O（R）比O（R log N）。 其中R是字符串的平均长度
第二个选项始终适用于字符串映射，为O（R*N）的情况提供保证的填充时间，并为O（R）的最坏情况提供保证的搜索时间。它唯一的缺点是在Java标准库中没有现成的实现
第三个选项有点棘手，只适合您的情况。为了使其正常工作，您需要确保第一个列表中的字符串在第二个列表中使用（是相同的对象）。使用IdentityHashMap消除了字符串的equals开销（上面的R），因为IdentityHashMap只使用O（1）按地址比较字符串。人口成本将按O（N）摊销，搜索成本按O（1）摊销。因此，此解决方案提供了最佳性能和现成的实现。但是，请注意，只有在原始列表中没有重复项时，此解决方案才有效
如果你有任何问题，请告诉我