java - 高效地从 Java 中的大量数组中删除重复的字符串？

Question

我正在考虑从(未排序的)字符串数组中删除重复项的最佳方法 - 该数组包含数百万或数千万个 stringz..该数组已经预填充，因此优化目标只是删除重复项而不是阻止重复项最初填充!!

我的思路是先进行排序，然后进行二分搜索，以获得 log(n) 搜索而不是 n(线性)搜索。这会给我 nlogn + n 搜索，这比未排序的 (n^2) 搜索更好 = 但这看起来仍然很慢。 (也在考虑散列但不确定吞吐量)

求助!由于在不使用 Collections API 的情况下涉及数百万个字符串，因此正在寻找一种既能解决速度又能解决内存问题的高效解决方案!

Answer 1

直到你的最后一句话，答案对我来说似乎很明显:使用 HashSet<String>或 LinkedHashSet<String>如果您需要保持秩序:

HashSet<String> distinctStrings = new HashSet<String>(Arrays.asList(array));

如果您不能使用集合 API，请考虑构建您自己的哈希集...但是在您给出不想使用集合 API 的原因之前，它是很难给出更具体的答案，因为这个原因也可以排除其他答案。