存储字符串的数据结构？

Question

我正在寻找一种用于存储字符串的数据结构。我需要接口中具有一个函数，它以字符串作为唯一参数，并返回可以在数据结构的余生中用于检索字符串的引用/迭代器/指针/句柄。集合成员资格、条目删除等不是必须的。

我更关注内存使用情况而不是速度。

- Nitage

---

请具体说明是哪种编程语言？ - Dead account

我们需要更多的信息来帮助... 大多数编程语言已经提供了处理字符串的数据结构，以实现高效的操作（例如Java的StringBuilder）。 - Zach Scrivena

我觉得他在谈论的是存储一组字符串，而不仅仅是一个字符串。 - Gonzalo Quero

Answer 1

一种高效的字符串存储数据结构是 Trie。通过使用相同的内存存储具有共同前缀的字符串，可以节省内存和时间。

您可以使用 Trie 中返回的字符串的最终标记作为指针，该标记唯一地标识字符串，并且可以通过向上遍历 Trie 来重新创建字符串。

- Avi

---

根据所使用的编程语言和输入的分布，这可能是低效的：对于单个字符将有大量指针。后缀尝试（Suffix tries）大小为O(n)，但是很大。在Java中，每个节点都将有一个互斥锁和条件变量：真的很大。请确保在决定之前测量实际大小。 - Jonas Kölker

@Jonas：绝对是好建议。请注意，我们讨论的不是特定的后缀树，而是trie作为一种通用的字符串存储/查找数据结构。一种变体的trie，它在某种程度上处理内存使用是Patricia Trie - 它尽可能避免单字符节点。 - Avi

Answer 2

我认为这里的关键词是字符串池，它可以仅存储每个不同字符串的一个副本。在Java中，可以通过String.intern()实现：

String ref1 = "hello world".intern();
String ref2 = "HELLO WORLD".toLowerCase().intern();
assert ref1 == ref2;

- Zach Scrivena

---

+1，这很有趣。快速的谷歌搜索显示.NET中有类似的功能。String.Intern()静态类。 - Gerald Davis

Answer 3

存储字符串有三种方式：

1. 定长（数组类型结构）
2. 可变长度但最大大小在运行时固定（指针类型结构）
3. 链表结构

- sangita bora

Answer 4

我认为这里最好的选择是 ArrayList。常见的实现方式会在数组中为新元素分配额外的空间，这会带来一些开销，但如果内存是一个要求，你可以手动为每个新元素分配内存。虽然速度会变慢，但只会使用字符串所需的必要内存。

- Gonzalo Quero