我正在寻找一种用于存储字符串的数据结构。我需要接口中具有一个函数,它以字符串作为唯一参数,并返回可以在数据结构的余生中用于检索字符串的引用/迭代器/指针/句柄。集合成员资格、条目删除等不是必须的。
我更关注内存使用情况而不是速度。
我更关注内存使用情况而不是速度。
一种高效的字符串存储数据结构是 Trie。通过使用相同的内存存储具有共同前缀的字符串,可以节省内存和时间。
您可以使用 Trie 中返回的字符串的最终标记作为指针,该标记唯一地标识字符串,并且可以通过向上遍历 Trie 来重新创建字符串。
我认为这里的关键词是字符串池,它可以仅存储每个不同字符串的一个副本。在Java中,可以通过String.intern()
实现:
String ref1 = "hello world".intern();
String ref2 = "HELLO WORLD".toLowerCase().intern();
assert ref1 == ref2;
存储字符串有三种方式:
我认为这里最好的选择是 ArrayList。常见的实现方式会在数组中为新元素分配额外的空间,这会带来一些开销,但如果内存是一个要求,你可以手动为每个新元素分配内存。虽然速度会变慢,但只会使用字符串所需的必要内存。