假设我有数百万个字符串。每个字符串都有一个 int 值。我想通过输入字符串检索这个值,但我不想存储所有这些字符串,因为它们占用了大量空间。我不能使用哈希表,因为它需要在内存中存储所有或至少许多字符串。那么对我来说什么是好的数据结构(我不需要添加或删除任何字符串,我已经准备好数据并且只允许读取操作)
问问题
1858 次
4 回答
4
使用trie来防止存储常见的子字符串。
于 2013-03-29T15:27:10.623 回答
1
你可能想看看Judy 树,它的设计既快速又紧凑,并且有一个专为字符串键设计的版本。它的实现在sourceforge上可用。
于 2013-03-29T23:55:36.623 回答
0
根据您当前问题中的有限信息,您不使用哈希表的理由听起来不成立。如果实施得当,它是相当有效的。如果您的需要可以接受,它还可以具有不浪费内存存储重复字符串的优点,如果可能出现重复字符串,则进一步减少内存消耗。
如果您对如何进行查找很有创意,您还可以将每个字符串的压缩形式存储在哈希表中。琴弦通常有多长?
于 2013-03-29T15:26:23.940 回答