string - 存储字符串的内存有效方式

Question

假设我有数百万个字符串。每个字符串都有一个 int 值。我想通过输入字符串检索这个值，但我不想存储所有这些字符串，因为它们占用了大量空间。我不能使用哈希表，因为它需要在内存中存储所有或至少许多字符串。那么对我来说什么是好的数据结构（我不需要添加或删除任何字符串，我已经准备好数据并且只允许读取操作）

score 4 · Accepted Answer

4

使用trie来防止存储常见的子字符串。

于 2013-03-29T15:27:10.623 回答

score 3 · Accepted Answer

如果可以预处理单词列表，请查看完美的哈希值，例如CMPH。（gperf是另一个，但似乎针对较小的数据集进行了优化。）

来自 CMPH 文档：

完美的散列函数将一组静态的 n 个键映射为一组 m 个整数而不会发生冲突，其中 m 大于或等于 n。如果 m 等于 n，则该函数称为最小函数。

...

CMPH 库将最新和更高效的算法封装在一个易于使用、生产质量、快速的 API 中。该库旨在处理无法放入主内存的大条目。它已成功用于为具有超过 1 亿个键的集合构建最小完美散列函数，...

score 1 · Accepted Answer

你可能想看看Judy 树，它的设计既快速又紧凑，并且有一个专为字符串键设计的版本。它的实现在sourceforge上可用。

score 0 · Accepted Answer

根据您当前问题中的有限信息，您不使用哈希表的理由听起来不成立。如果实施得当，它是相当有效的。如果您的需要可以接受，它还可以具有不浪费内存存储重复字符串的优点，如果可能出现重复字符串，则进一步减少内存消耗。

如果您对如何进行查找很有创意，您还可以将每个字符串的压缩形式存储在哈希表中。琴弦通常有多长？

4 回答 4