java - 使用startsWith快速比较字符串

Question

我有以下代码:

String[] names = {"aa", ..........., "bb"};
for (int i = 0; i < names.length; i++) {
    if (names[i].toLowerCase().startsWith(query.toLowerCase()))
        c.addRow(new Object[]{i, names[i]});
}

由于数组名称可能很长，我想知道从性能角度来看编写此代码的最佳方法是什么。这样循环的复杂度是O(N)。有没有java数据结构可以更快地完成同样的事情？

Answer 1

您可以对名称进行排序，使用带有不区分大小写的比较器的二分搜索来查找潜在前缀的插入点，并遍历数组以捕获具有相同前缀的所有其他单词:

// At preparation time
Arrays.sort(names, String.CASE_INSENSITIVE_ORDER);
...
// At query time
int pos = Arrays.binarySearch(names, query, String.CASE_INSENSITIVE_ORDER);
if (pos < 0) {
    pos = -(pos+1);
}
while (pos < names.length) {
    if (names[pos].toLowerCase().startsWith(query.toLowerCase())) {
        c.addRow(new Object[]{pos, names[pos]});
        pos++;
    } else {
        break;
    }
}

Arrays.binarySearch 找到一个插入点。如果名称匹配，pos 将为非负数；否则，您需要使用以下表达式将其转换为有效索引: -(pos+1) 如果 query 是正确的前缀，则其插入点将位于前面具有匹配前缀的名字。由于 names 已排序，因此具有相同前缀的所有条目将彼此相邻。这就是为什么您可以线性遍历列表直到第一次不匹配，然后在该点停止。