字符串集占用太多内存,建议…?

看看布鲁姆过滤器或杜鹃散列。 Bloom filter or cuckoo hashing?

我不确定这是否是你问题的答案,但值得研究这些替代方案。bloom过滤器主要用于拼写检查类的用例。

http://en.wikipedia.org/wiki/Trie

HashSet 可能不是这个的正确结构。使用 Trie 相反。

这可能有点晚了,但使用Google你可以很容易地找到我不久前发布的DAWG调查和C代码。

http://www.pathcom.com/~vadco/dawg.html

TWL06-178691个字-可容纳494676个字节

压缩共享节点结构的缺点是它不能作为列表中单词的哈希函数。也就是说,它会告诉您一个单词是否存在,但不会返回一个与确实存在的单词相关的数据的索引。

http://www.pathcom.com/~vadco/adtdawg.html

祝你一切顺利,

12MB存储120000个字大约是每个字100个字节。可能其中至少有32个字节是字符串开销。如果单词的平均值为10个字母,并以2字节字符的形式存储,那就需要另外20个字节。然后是对哈希集中每个字符串的引用,可能是另外4个字节。剩下的44个字节可能是HashSet条目和索引开销,或者是我上面没有考虑过的东西。

最简单的方法是字符串对象本身的开销,这会占用比存储实际字符数据所需的内存多得多的内存。因此,您的主要方法是开发一个自定义表示,以避免为每个字符串存储单独的对象。在此过程中,您还可以消除HashSet开销,因为您真正需要的只是一个简单的单词查找,这可以通过对数组的直接二进制搜索来完成,该数组将是您自定义实现的一部分。

可以将自定义实现创建为int类型的数组,每个单词有一个元素。这些int元素中的每一个都将被分解成子字段,子字段包含一个长度和一个偏移量,该偏移量指向char类型的独立后备数组。将这两个类放入一个管理它们的类中,该类支持公共方法,允许您检索和/或转换给定字符串索引和可选字符索引的数据和单个字符,并对拼写检查功能所需的单词列表执行简单搜索。

如果基础字符串数据不超过16777216个字符(例如,120000个字符串乘以10个字符的平均长度=120万个字符),则可以取每个int的低位24位,并将每个字符串的起始偏移量存储到字符数据的后备数组中,取每个int的高阶8位,并将相应字符串的大小存储在那里。

char数据将把以前的字符串塞满在一起,而不使用任何分隔符,完全依赖int数组来知道每个字符串的开始和结束位置。

如果您的字恰好完全是ASCII数据,您可以通过将备份数据存储为字节而不是字符来额外节省1200000字节。

如果需要更改这些字符串,这可能会变得更加困难。显然,在您的情况下(拼写检查器),您不需要这样做(除非您希望支持用户添加到列表中,这无论如何都是不常见的,因此重新编写char数据和索引来添加或删除单词可能是可以接受的)。

radix tree trie 因为前缀不是冗余存储的。

open addressing 可用于此(如google collection的 ImmutableSet

问题出在设计上:出于拼写检查的原因,在哈希集中存储如此大量的单词不是一个好主意:

您可以使用拼写检查器(例如: http://softcorporation.com/products/spellcheck/ ),也可以使用前缀树构建“自动单词完成”(说明: http://en.wikipedia.org/wiki/Trie

在这种设计中没有办法减少内存使用。

你也可以试试 Radix Tree ( Wiki , Implementation trie 但是内存效率更高。