String的HashSet占用太多内存，建议......？
我目前在HashSet中存储了一个单词列表（大约120,000），目的是作为一个列表来检查反对的单词是否拼写正确，然后返回yes或no。String的HashSet占用太多内存，建议......？
我想知道是否有办法做到这一点，占用更少的内存。目前120,000字大约是12meg，实际文件的读取字数大约是900kb。
有什么建议吗？
在此先感谢
检查布卢姆过滤器或杜鹃哈希。 Bloom filter or cuckoo hashing?
我不确定这是否是您的问题的答案，但值得研究这些替代方案。布隆过滤器主要用于拼写检查类的用例。
或http://stackoverflow.com/questions/2294915/what-algorithm-is-used-to-give-suggestions-in-a-spell-checker/2294926#2294926 – 2010-07-12 13:54:16
它认为绽放哈希声很好，因为我可以应付在每个条目20b左右有0.01％的假阳性率，相当于我的100k单词列表中的200Kb，这是一个巨大的改进。谢谢！ （现在会读取杜鹃哈希） – Dori 2010-07-13 10:41:11
找到了开源的Java Bloom Filter http://code.google.com/p/java-bloomfilter/ – Dori 2010-07-13 11:33:28
的问题是由设计：在一个HashSet存储的话如此庞大的拼写检查 - 原因是不是一个好主意：
您可以使用拼写检查（例如：http://softcorporation.com/products/spellcheck/） ，或者你可以用一个前缀树（描述：http://en.wikipedia.org/wiki/Trie）构建一个“auto-wordcompletion”。
无法在此设计中减少内存使用量。
节省内存以节省内存的一种方法是使用radix tree。这比trie好，因为前缀不会被冗余存储。
由于你的字典是固定的，另一种方法是为它建立一个完美的散列函数。你的哈希集不需要桶（和相关的开销），因为不会有冲突。每个使用open addressing的哈希表/哈希集的实现都可以用于此（如谷歌收集的ImmutableSet）。
这可能有点晚，但使用Google，您可以轻松找到前段时间发布的DAWG调查和C代码。
http://www.pathcom.com/~vadco/dawg.html
TWL06 - 178691字 - 融入494676个字节
压缩共享节点的结构的缺点是，它不为你的列表中的单词的哈希函数工作。也就是说，它会告诉你一个单词是否存在，但是它不会为一个存在的单词返回相关数据的索引。
如果您想要在处理器高速缓存大小的结构中完美和完整的散列功能，您将必须阅读，理解和修改名为ADTDAWG的数据结构。它会比传统的DAWG稍大，但速度更快，更实用。
http://www.pathcom.com/~vadco/adtdawg.html
一切顺利，
JohnPaul Adamovsky
12MB存储12万个字是每字约100个字节。可能至少有32个字节是字符串开销。如果单词平均为10个字母，并且它们存储为2个字节的字符，则占用另外20个字节。然后是HashSet中每个字符串的引用，这可能是另外4个字节。其余的44个字节可能是HashSet条目和索引开销，或者我上面没有考虑的东西。
最简单的事情就是String对象本身的开销，它可能比存储实际的字符数据需要更多的内存。所以你的主要方法是开发一个自定义表示，避免为每个字符串存储一个单独的对象。在这样做的过程中，您还可以摆脱HashSet开销，因为您真正需要的只是简单的单词查找，可以通过对数组进行简单的二进制搜索来完成，这将成为您的自定义实现的一部分。
您可以将您的自定义实现创建为类型为int的数组，每个单词包含一个元素。这些int元素中的每一个都会被分成包含长度和偏移量的子字段，并指向char类型的单独支持数组。将它们放入一个管理它们的类中，并且支持公共方法，允许您在给定字符串索引和可选字符索引的情况下检索和/或转换数据和单个字符，并对单词列表执行简单搜索这是您的拼写检查功能所需的。
如果底层字符串数据的字符数不超过16777216（例如，平均长度为10个字符的120,000个字符串= 120万个字符），则可以取每个int的低24位，并将起始将每个字符串偏移到char数据的后备数组中，并取每个int的高位8位并在其中存储相应字符串的大小。
你的char数据会将你的旧字符串挤在一起而没有任何分隔符，完全依赖int数组来知道每个字符串的开始和结束位置。
采取上述方法，您的120,000字（平均每个10个字母）将需要大约2,400,000字节的后备阵列数据和480,000字节的整数索引数据（120,000 x 4字节），总共2,880,000字节，与上面报告的目前的12MB数量相比，可节省大约75％的费用。
数组中的单词将按字母顺序排序，并且您的查找过程可能是对int数组的简单二分搜索（从每个测试的char数组中检索相应单词），这应该非常有效。
如果您的文字碰巧完全是ASCII数据，您可以通过将备份数据存储为字节而不是字符来保存额外的1,200,000字节。
如果您需要更改这些字符串，这可能会变得更加困难。很显然，在你的情况下（拼写检查器），你不需要（除非你想支持用户添加到列表中，而这将不经常发生，所以重写char数据和索引来添加或删除单词可能会可以接受）。
你怎么知道数据结构是12MB？ – 2010-07-12 11:34:19
仅仅通过编写一个小测试类 – Dori 2010-07-12 11:36:25