Java：存储大量单词的数据结构

Question

我需要在Java程序中存储大量单词（200k +），并希望快速访问它们。我只需要知道给定的单词是否属于我的“字典”。 我不需要像 <word, smthg> 这样的成对数据。 如果可能，我正在寻找标准库中的解决方案。 PS：也许使用数据结构不是最好的方法？每次读取包含单词的文件会更有效吗？ 编辑：这是一个小项目。 我必须处理效率和内存。 最后编辑：最终我选择了 HashSet。

- DouglasAdams

---

听起来像是 HashSet 可能很适合。 - Keppil

你有关于使用 Lucene 的任何想法吗？ - SenthilPrabhu

@Keppil HashSet的问题在于它不是有序的，因此搜索速度会变慢。 - Nikhil Agrawal

@Nikhil：在HashSet中查找一个单词的时间复杂度是 O(1)，而在TreeSet中则为 O(log n)。 - Keppil

HashSet 真的更快。谢谢。 - DouglasAdams

@Yavar：我认为问题出在数百万条数据上..！ - SenthilPrabhu

Answer 1

使用Java集合（Sets）因为集合是类似TreeSet的线性排序数据结构。因此，可以实现二分搜索等技术来进行搜索，它们很快且没有重复项。

以下是Java集合的结构。 同时，它将不允许重复，从而减少冗余并节省内存。

如果您想了解各种搜索算法的复杂度，请参阅此链接。这里是： http://bigocheatsheet.com/

- Nikhil Agrawal

---

集合会浪费很多内存。有专门的数据结构来处理这种任务。 - Ivaylo Strandjev

@IvayloStrandjev 一共20万个单词，平均每个单词10个字符，存储在一个HashSet中，可能需要5到10MB的内存。这并不算多... - assylias

就性能而言，在我的台式电脑上，使用200k个单词填充哈希集合并运行100万次单词查找总共需要约150毫秒。 - assylias

@IvayloStrandjev 我并不是说 HashSet 比专门的数据结构更高效 - 我只是说它对于 OP 的需求来说已经足够好了。因此，找到并导入外部库或更糟糕的是手动实现这些结构可能并不值得麻烦。 - assylias

@assylias，我可以得到你的邮件ID或Twitter ID吗？ - Nikhil Agrawal

Answer 2

根据单词分布，可以选择使用 Trie 或 Patricia 树。个人建议采用 Patricia 树，因为它更优化内存使用（尽管实现难度较大）。

- Ivaylo Strandjev

---

对于像是在 OP 所描述的场景中数量相对较小的对象，使用 HashSet 就足够了。同时值得注意的是，在标准 JDK 中没有 Trie/Patricia Tree 的实现。 - assylias

Answer 3

也许您想要测试一下我的 TrieMap 或者 TrieSet 实现（在这里找到）？我专门为这种情况编写了它们。到目前为止，我已经实现了针对 String 和 byte[] 键的 Trie。

    TrieSet<String> t = Tries.newStringTrieSet();

    t.add("hello");
    t.add("help");
    t.add("hell");
    t.add("helmet");
    t.add("hemp");

    List<String> resultsA = new ArrayList<>();
    t.findElements("hel", true, resultsA);    // search for prefix

    List<String> resultsB = new ArrayList<>();
    t.findElements("ell", false, resultsB);   // search for substring

    System.out.println("A: " + resultsA);
    System.out.println("B: " + resultsB);

这将会打印出来：

A: [hell, hello, helmet, help]
B: [hell, hello]

- Jan Kebernik

---

1.5 KLOC，连一个测试都没有？ - Philipp Reichart

Answer 4

这个看起来对我来说相当不错，但我不知道是否由于某种原因我是错误的：

//put all your words to an ArrayList and sort the list.
List <String> arr = new Arraylist<>();
while(there is next)
    arr.add(theWord)
Collections.sort(arr);

//this is your search method
boolean mysearch(keyword){
    return Collections.binarySearch(arr, keyword)
}

性能为：O(n*log_n)，用于插入数据和搜索是O(log_n)

假设每个字符串平均为20B。20B * 200000 = 4MB的空间。

- smttsp