保持标记化字符串的Android内存高效集合

Question

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

我需要这些令牌可用/搜索/包含在o（1）或任何恒定时间。

我开始与HashSet - 但它的字符串数据打击了10MB的 - 导致内存不足的问题

然后，切换到ArrayList - 但也吹至6MB。

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

所以，我主要关注的仍然有这样的数据：

• 其最初600KB - 所以收集应保持在1好或2MB
• 查找应Ø内是最好（1）

有什么好的Java集合（甚至可以从任何其他库），可以帮助我吗？

Answer 1

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

假设字符串中的字符是ASCII ，然后立即将它们转换为String对象使尺寸加倍（byte - >char），然后您需要为每个字符串添加32个字节的开销。然后，如果将字符串放入HashSet，那么对于集合中的每个条目，您大约需要32个附加字节。

随着ArrayList<String>的每个条目的开销为4个字节，但现在查找是O(N) ...或者O(logN)如果你保持有序的列表，然后使用二进制搜索。无论哪种方式，你仍然是你的记忆预算。

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

这是一个假设的实现。

1. 分配一个int[]为散列数组。大小应该是一个素数，大约是令牌数量的五分之一到五分之一。
2. 分配一个大到足以容纳令牌文件的byte[]。
3. 对于哈希阵列中的每个插槽：
   • 扫描文件的字节方式寻找其哈希码映射到时隙的所有令牌，
   • 副本的每个令牌的字节数组，并按照其与终止字节，
   • 如果您发现任何标记，请将第一个标记的开始的字节数组偏移量写入散列数组插槽中，否则将其设置为-1。
4. 要执行的查找：
   • 转换测试字符串字节，
   • 散列测试字符串的字节（使用相同的散列算法如上述），并将其映射到散列插槽，
   • 从散列槽中的偏移量开始，将测试字符串的字节与byte[]中的字节进行比较。重复，直到得到一个匹配，或者你到达下一个散列数组元素的偏移量。

正如你可以看到，尽显byte[]的过程涉及扫描输入文件多次。然而，这可以在手之前完成，然后可以更新输入文件以包含所需顺序的字节。

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

上述设计的大缺点是：

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

Answer 2

这是一个有趣的问题！我通常在util包中使用HashMap类来进行存储。你的问题可能不容易适应Android设备的内存空间，所以我会建议一个替代方案。

对于存储的Android设备通常使用固态如SD卡，其通常是相当快的，那么为什么直到需要不能离开大多数资产文件夹的磁盘上的数据？您可以构造一个类来缓存最常用的结果，修改数据也应该是合理的。如果这不包括套件，也许你可以使用android SDK中可用的数据管理工具，例如sqlite，它将为你做一些辛苦的工作。

如果你能避免使用字符串，往往是更好的选择。字符串的操作可能非常昂贵。如果你使用另一种数据类型（甚至是字符或字节数组），你可能会发现代码在内存方面更复杂一些，但效率更高。