保持標記化字符串的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，它將爲你做一些辛苦的工作。

如果你能避免使用字符串，往往是更好的選擇。字符串的操作可能非常昂貴。如果你使用另一種數據類型（甚至是字符或字節數組），你可能會發現代碼在內存方面更復雜一些，但效率更高。