在Java中搜索匹配字符串的数组

Question

如何优化以下内容：

final String[] longStringArray = {"1","2","3".....,"9999999"};
String searchingFor = "9999998"
for(String s : longStringArray)
    {
        if(searchingFor.equals(s))
        {
            //After 9999998 iterations finally found it
            // Do the rest of stuff here (not relevant to the string/array)
        }
    }

注意：longStringArray只在运行时搜索一次，不排序，并且每次运行程序都不同。

我确定有一种方法可以改善最坏情况下的性能，但我似乎找不到...

P.S.还希望有一种解决方案，其中字符串searchingFor不存在于数组longStringArray中。

谢谢。

- Sigtran

---

这里不是很清楚你想要实现什么。你可以使用字符串 searchingFor 做与数组中它的完全相同的操作。- 一个好的解决方案必须知道接下来你要做什么。 - vbence

我想提高性能，而不是在线性时间内搜索。我认为这已经很清楚了。下面的答案说我无法改进它。 - Sigtran

是的，但这并不一定是真的。就像我说的一样，它取决于你接下来要做什么。例如：你想检查一个值是否在数组中？（HashSet）或者这些字符串是标识符，你想获取它们所代表的对象（HashMap）。等等... 所以一切都取决于更大的局面。-此外，你搜索/更改的比率也很重要。 - vbence

好的，是的，就像上面的代码一样 - 我想看看字符串是否在数组中（我每次运行只想搜索一次数组，下一次搜索时数组和字符串都会改变）。接下来我要做的与搜索无关，只有当字符串存在时才执行（例如，if语句内部与搜索无关）。我可以修改问题，但我不知道如何改进它。请给予建议。 - Sigtran

Answer 1

如果你必须使用数组，并且不知道它是否已排序，而且只需要进行一次查找，那么这将始终是O(N)操作。由于任何优化步骤都至少需要O(N) - 例如，填充集合或对数组进行排序。

但是还有其他选择：

• 如果数组已排序，则可以执行二分查找。这将把每个查找操作转换为O(log N)操作。
• 如果要执行多个搜索，请考虑使用HashSet<String>。 这将把每个查找操作转换为O(1)操作（假设碰撞较少）。

- Jon Skeet

Answer 2

import org.apache.commons.lang.ArrayUtils;
ArrayUtils.indexOf(array, string);

ArrayUtils文档

- Igor

Answer 3

Arrays.asList(longStringArray).contains(searchingFor)

- Raúl

Answer 4

你可以创建第二个数组，其中包含字符串的哈希码，并在其上进行二分查找。

您将不得不对哈希数组进行排序，并相应地移动原始数组的元素。这样，您将拥有极快的搜索能力，但它将保持有序，因此插入新元素需要资源。

如果您有大量数据并且必须处理插入操作，则最优的方法是实现二叉树或B树。

- vbence

---

你是否打算重新实现哈希表？Java已经有了HashSet的实现（对于此情况，其他变体是HashMap / Hashtable / ConcurrentHashMap）。 - Paŭlo Ebermann

@Paŭlo 如果没有其他原因，作为开发人员编写这样的内容将使您受益匪浅。关于建议的对象，您是错误的。它们三个都创建了键值关联。据我们所知，OP只有值。 - vbence

@Paŭlo，它基本上是一个哈希值的有序列表，因此可以使用二分查找。通过在二分查找结果周围检查相同的哈希值，并使用equals确保我们找到了正确的元素。当然，原始元素必须重新排序以匹配哈希数组的索引。 - vbence

是的，这样做会放弃哈希表的所有优势，即通常的O(1)访问，并且需要O(log n)的访问时间。构建表需要O(n log n)（至少）而不是哈希表的O(n)。这是一个有趣的想法，但并不是真正替代实际哈希表的有用选择。 - Paŭlo Ebermann

@Paŭlo，你提出了有趣的观点。我会查看Java API中基于哈希的容器的实际实现。 - vbence