Java：检查字符串是否在单词列表中的最有效方法

Question

我有一个字符串数组String[] words和一个28000个单词的单词列表。我想检查字符串数组中的任何成员是否在单词列表中（单词列表在文本文件wordlist.txt中）。如何以最有效的方式完成此操作？

- Eduardo

---

听起来你正在使用错误的数据结构。HashSet 可能更适合。 - kiheru

这将占用大量内存。 - Philipp Sander

使用单词列表构建kd-tree，其中每个字母是一个维度。将您的String[]单词输入，查找在树中最近的邻居。 - metsburg

Answer 1

将字符串直接放入HashSet<String>而不是数组中，并使用集合上的contains方法迭代文件，以检查内容。您不会获得O（1）访问的提升。如果存在任何重复项，则这还将最小化用于存储Strings的内存。

- Reimeus

---

那么把整个单词列表读入 HashSet 也不是一个好主意吗？ - Eduardo

不，你需要删除重复项以减少内存占用，因此直接使用HashSet是正确的方法（此外，你无需重新填充HashSet - 这在代码使用方面也是微小的优势）！ - Reimeus

Answer 2

你可以尝试使用数组（树）后缀算法，但需要实现，看这里：

使用后缀树查找字符串中的最长回文串

- Omar Mainegra

Answer 3

步骤1：不要使用字符串数组。改用HashSet。

步骤2：将文件(wordlist.txt)的内容加载到另一个HashSet中。

步骤3：

Set<String> set1 = new HashSet<String>(); //Load the string array into set
    Set<String> set2 = new HashSet<String>(); //load the file contents into set
    for (String str : set1) {
        for (String str2 : set2) {
            if (str.equalsIgnoreCase(str2)) {
                break;
            }
        }
    }

- SmartTechie

---

检查set2是否包含str会更快。这是一个O(1)操作，使用集合的主要好处之一。它将时间复杂度从O(n^2)降至O(n)。 - Bryan

Answer 4

HashSet 的 add() 方法如果集合中已经存在该元素，则返回 false。

for (String str : words) {
  if (!wordSet.add(str)) {
    System.out.println("The word " + str + " is already contained.");
  }
}

这比contains()更复杂，也不那么底层。

- András Hummer

Answer 5

如果你的单词列表可以放入内存中，那么 HashSet 就足够了。

如果内存大小是一个问题，使用 BloomFilter。虽然 Bloom 过滤器可能会给出错误的答案，但你可以调整它发生的概率。

- Andrejs

Answer 6

你可以使用具有contains方法的HashSet<String>或ArrayList<String>。它将检查您的字符串是否已存储。
HashSet和ArrayList之间的区别在于，hashset不允许重复值，并且它不会维护顺序，而arraylist允许您重复并且是有序集合。 但是，HashSet比arraylist更有效地执行搜索操作。

- Vimal Bera

---

我不建议使用ArrayList，因为它必须检查所有项，而HashSet只需要检查具有相同hashCode()的项的.equals()。 - ppeterka

我真的认为在这种搜索中使用Java内置的数据类型非常低效。 - metsburg

@metsburg，那你有更好的实现方式吗？;-) - Philipp Sander

感谢评论。是的，HashSet比ArrayList更高效。我只是向他展示了2种不同的方法。 - Vimal Bera

@PhilippSander 如果单词列表很大，Trie可能会被认为更有效率。 - kiheru

Answer 7

创建一个字符串的HashSet。

HashSet<String> wordSet = new HashSet<String>(Arrays.asList(words));

检查在HashSet中是否存在word，使用HashSet.contains(Object o)方法，其中word是您要检查是否存在的单词。

- TheKojuEffect

Answer 8

将原始的words.txt文件替换为序列化的HashSet。这应该是在运行应用程序之前的一个单独步骤。

然后，应用程序只需要加载一次哈希集合。

- Joop Eggen