Java：数据结构存储大量字

我必须在Java程序中存储大量字（+ 200k），并且我想快速访问它们。我只需要知道给定的单词是否属于我的“词典”。我不需要像<word, smthg>这样的一对。如果可能，我正在标准库中寻找解决方案。Java：数据结构存储大量字

PS：也许使用数据结构不是更好的方法来做到这一点？每次读取包含单词的文件会更有效率？

编辑：这是一个小项目。我必须处理效率和内存

最后编辑：我最终选择HashSet。

来源

2013-04-18 DouglasAdams

听起来像[HashSet]（http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html）可能非常合适。 – Keppil

你对使用[Lucene]有任何想法（http://lucene.apache.org/） – SenthilPrabhu

@Keppil HashSet中的问题是它没有排序。所以搜索会更慢。 –

使用java集因为集合是像TreeSet这样的线性排序数据结构。所以对于搜索来说，像二进制搜索这样的技术可以实现，而且它们快速且不重复。

这是一个java集合的结构。

enter image description here

它也将不会允许重复，因此减少冗余，节省你的记忆。

如果您想了解各种搜索算法的复杂性，请参阅此链接。这里是

http://bigocheatsheet.com/

来源

2013-04-18 10:21:51

集合会浪费大量内存。这类任务有专门的数据结构。 –

@IvayloStrandjev存储在HashSet中的平均10个字符的200k字可能需要5到10MB的内存。这并不是很多... – assylias

刚刚尝试过，它接近20MB，但还是不多。 – assylias

根据单词的分布情况，使用Trie或Patricia tree。我个人会选择Patricia树，因为它更适合内存使用（虽然实现起来比较困难）。

来源

2013-04-18 10:20:47

对于像OP的用例那样的相当少量的对象，HashSet可以做得很好。另外值得注意的是标准JDK中没有Trie/Patricia Tree实现。 – assylias

也许你想测试我的TrieMap或TrieSet实现（found here）？我专门为这类案件编写了它们。到目前为止，我已经为String和byte[]键实施了Tries。

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]

来源

2013-04-18 11:36:02

> 1.5 KLOC，而不是一个单一的测试？ –

这看起来很确定，我不知道如果我错了，因为某些原因：

//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，在a verage。 20B *200000 = 4MB空间。

来源

2013-04-18 11:41:26 smttsp

Java：数据结构存储大量字

回答

相关问题