为什么 java Set.contains() 比 String.contains() 快？

Question

对于在 2 个字符串之间查找公共字符的问题，起初我使用了直接的 String.contains() 方法：

static String twoStrings(String s1, String s2) {
    boolean subStringFound = false;
    for(int i = 0; i < s2.length(); i++){
        if(s1.contains(Character.toString(s2.charAt(i)))) {
            subStringFound = true;
            break;
        }
    }
    return subStringFound?"YES":"NO";
}

然而，它通过了大部分测试用例 5/7 测试用例，但有 2 个非常长的字符串面临超时。

然后我尝试使用 Set.contains():

static String twoStrings(String s1, String s2) {
    boolean subStringFound = false;
    HashSet<Character> set = new HashSet<>();
    for(int i = 0; i < s1.length(); i++){
        set.add(s1.charAt(i));
    }

    for(int i = 0; i < s2.length(); i++){
        if(set.contains(s2.charAt(i))) {
            subStringFound = true;
            break;
        }
    }
    return subStringFound?"YES":"NO";
}

尽管我运行是一个额外的循环来创建一个 Set，但它通过了所有测试。造成这种运行时显着差异的主要原因是什么。

Answer 1

您必须查看正在使用的 JDK 中的实现，但很可能 String.contains 是 线性搜索 但 HashSet.contains 不是。来自 HashSet documentation:

This class implements the Set interface, backed by a hash table (actually a HashMap instance)...

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.

Answer 2

因为它们是不同的数据结构，contains方法在它们上面的实现也不一样

字符串是一个字符序列，因此要测试它是否包含给定字符，您必须查看序列中的每个字符并进行比较。该算法称为 linear search，它需要 O(n) 时间，其中 n 是字符数，这意味着当字符越多时，它所花费的时间也相应地越多。

一个HashSet是一种hash table数据结构。基本上，要测试它是否包含给定字符，您可以获取该字符的散列值，将散列值用作数组中的索引，然后判断该字符是否存在（或非常接近那里），或者不存在。所以你不必搜索整个集合；平均需要 O(1) 时间，这意味着时间大致相同，但是有很多字符。

为什么 java Set.contains() 比 String.contains() 快？

Why java Set.contains() is faster than String.contains()?

java

string

algorithm

runtime

hashset