java - 用于保存标记化字符串的 Android 内存高效收集

Question

在我的项目中，我试图从包含字符串标记的 Assets 文件夹中加载一个 600KB 的文件。

我需要这些 token 在 o(1) 或任何固定时间可用/搜索/包含。

我开始使用 HashSet - 但它将字符串数据放大到 10MB - 导致内存不足问题

然后，切换到 ArrayList - 但这也达到了 6MB。

我尝试使用原始 String，但是当我从 StringBuffer 构建它时 - append 方法的固有问题出现了 - 导致 Out of内存问题。

所以，我主要关心的仍然是这些数据:

• 它最初是 600KB - 所以集合应该将它保持在 1 或 2MB 以内
• 查找应该最好在 O(1) 内

是否有任何好的 Java 集合(甚至来自任何其他库)可以帮助我？

Answer 1

以 1 到 2Mb 的内存表示这些标记并且支持O(1)查找将非常困难。没有一个标准的集合类型能够为你做到这一点， 而且我不知道有任何第 3 方 Java 库可以。 (S-Space 项目有一个 TrieSet 实现，但我查看了代码，我很确定它不会满足您的空间或性能要求......)

假设字符串中的字符是ASCII，那么将它们转成String对象，大小会立即翻倍( byte -> char )，然后需要为每个字符串增加32字节的开销。然后，如果您将字符串放入 HashSet集合中的每个条目大约需要 32 个额外字节。

用ArrayList<String>每个条目的开销是 4 个字节，但查找现在是 O(N) ... 或 O(logN)如果您保持列表有序并使用二进制搜索。无论哪种方式，您仍然超出了内存预算。

为了保持在预算之内，您将不得不使用针对内存使用优化的自定义哈希表数据结构并将您的字符数据作为单个字节数组保存在内存中。 p>

这是一个假设的实现。

1. 分配一个int[]成为哈希数组。大小应该是质数，大约是 token 数量的一半到五分之一。
2. 分配一个byte[]大到足以容纳 token 文件。
3. 对于散列数组中的每个槽:
   • 逐字节扫描文件，查找哈希码映射到插槽的所有标记，
   • 将每个标记复制到字节数组，并在其后跟一个终止符字节，
   • 如果找到任何标记，将第一个标记开头的字节数组偏移量写入哈希数组槽...否则将其设置为-1 .
4. 要进行查找:
   • 将测试字符串转换为字节，
   • 散列测试字符串的字节(使用与上述相同的散列算法)，并将其映射到散列槽，
   • 从散列槽中的偏移量开始，将测试字符串的字节与 byte[] 中的字节进行比较.重复直到获得匹配项，或者到达下一个 哈希数组元素中的偏移量。

可以看到，填充byte[]的过程涉及多次扫描输入文件。然而，这可以事先完成，然后可以更新输入文件以包含所需顺序的字节。

空间使用量为每字节字符串数据一个字节 + 每个字符串 1 字节开销 + 主哈希数组中每个槽 4 字节(+ 杂项 O(1) 开销)。查找是 O(1)平均而言，但常量取决于散列数组的大小。 (越大越好。)

上述设计的最大缺点是:

• 创建数据结构是昂贵的
• 数据结构不能以空间或时间高效的方式更新
• 如果迭代集合，则必须创建一堆 String 对象来表示条目……或者公开字节数组和偏移量。