java - 从 HashSet(或其他集合)中过滤掉字符串

Question

我正在将一个 txt 文件的内容读入一个 HashSet。该文件几乎包含了英语中的每一个单词，并且每个单词都变成了HashSet中的一个字符串。

在我的应用程序中，字符被添加到字符串中。我想检查此字符串是否等于或可以等于 HashSet 中的任何字符串。也就是说，假设 HashSet 仅包含字符串 apple。我有一个字符串 appl，现在我想过滤掉 HashSet，直到它变成一个只包含以 appl 开头的字符串的集合(在这种情况下只有苹果)。

我可以迭代整个 HashSet 并使用 startsWith(String) 方法，因为我构建了一个新的过滤 HashSet。但是我的初始 HashSet 非常大，所以我的问题是:是否有更有效的方法(可能使用不同类型的 Collection？)

我现在将如何做的一些代码:

private HashSet<String> filter(String partOfWord){
    HashSet<String> filteredSet = new HashSet<>();

    for (String word : dictionary) { // dictionary is the full HashSet
        if (word.startsWith(partOfWord)) {
            filteredSet.add(word);
        }
    }
    return filteredSet;
}

Answer 1

A trie是完成此任务的终极武器，但您可以从 TreeSet 中获得良好的效率:

private TreeSet<String> dictionary;

private TreeSet<String> filter(String partOfWord) {
    return (TreeSet<String>)dictionary.subSet(partOfWord, partOfWord + "zzz");
}

以“appl”开头的所有内容也介于“appl”(如果它本身是一个单词，则包含在内)和“applzzz”(没有英语单词中有 3 个连续的“z”) ，这在字典序上大于所有以“appl”开头的单词。调用 subset() 的时间复杂度是O(log n)找到子集的开始和O(m) (m = 返回的数字)范围，这非常好。

请注意，如果您能够随着单词的增长将返回的集合重新用作新词典，那么您的代码总体上会更加高效。

投向TreeSet<String>需要因为 subSet()是 SortedSet 的一种方法接口(interface)并返回 SortedSet , 但它是 covariant因为 TreeSet implementation返回一个 View (另一个效率优势)，这当然是另一个 TreeSet .

为了提高效率，但代码更难看，您可以使用排序的 String[]和 Arrays.binarySearch() ，然后一旦您找到了您的匹配项，您就可以快速遍历数组集合您的匹配项。

请注意 TreeSet和排序数组有 O(log n)查找时间，而 HashSet (虽然不适合这项任务)是O(1)查看时间。