java - 我可以使用什么符号表来存储约 5000 万个字符串并进行快速查找，而不会耗尽堆空间？

Question

我有一个约 5000 万个字符串的文件，我需要在启动时将其添加到某种符号表，然后以合理的速度搜索几次。

我尝试使用 DLB trie，因为查找速度相对较快，因为所有字符串都小于 10 个字符，但是在填充 DLB 时，我会遇到超出 GC 开销限制或内存不足 - 堆空间错误。使用 HashMap 发现了相同的错误。这是针对将由评分者编译和运行的作业，因此我不想只分配更多的堆空间。是否有一种不同的数据结构可以减少内存使用，同时仍然具有合理的查找时间？

Answer 1

如果您期望低前缀共享，那么 trie 可能不是您的最佳选择。

由于您只在启动时加载一次查找表，并且您的目标是低内存占用和“合理的速度”查找，因此您最好的选择可能是排序数组和二分查找查找。

首先，您将数据加载到一个数组中。由于您可能不知道预先的大小，因此您加载到 ArrayList 中。 .然后从列表中提取最终数组。

假设加载 5000 万个 10 个字符的字符串，内存将是:

10 character string:
    String: 12 byte header + 4 byte 'hash' + 4 byte 'value' ref = 24 bytes (aligned)
    char[]: 12 byte header + 4 byte 'length' + 10 * 2 byte 'char' = 40 bytes (aligned)
    Total: 24 + 40 = 64 bytes
Array of 50 million 10 character strings:
    String[]: 12 byte header + 4 byte 'length' + 50,000,000 * 4 byte 'String' ref = 200,000,016 bytes
    Values: 50,000,000 * 64 bytes = 3,200,000,000 bytes
    Total: 200,000,016 + 3,200,000,000 = 3,400,000,016 bytes = 3.2 GB

您将需要另一份 String[]当你转换 ArrayList<String>至 String[] . Arrays.sort()操作可能需要 50% 的数组大小(~100,000,000 字节)用于临时存储，但如果 ArrayList在排序之前为 GC 释放，该空间可以重复使用。

因此，总需求约为 3.5 GB，仅用于符号表。

现在，如果空间真的很宝贵，您可以压缩它。如您所见，String本身在 64 字节中增加了 24 字节的开销。您可以使符号表使用 char[]直接。

此外，如果您的字符串都是 US-ASCII或 ISO-8859-1 , 你可以转换 char[]到 byte[] , 节省了一半的字节数。

合并后，值大小从 64 字节减少到 32 字节，符号表总大小从 3.2 GB 减少到 1.8 GB，或者在加载期间大约减少 2 GB。

---

更新

假设输入的字符串列表已经排序，下面是如何执行此操作的示例。作为MCVE ，它只使用一个小的静态数组作为输入，但您可以轻松地从文件中读取它们。

public class Test {
    public static void main(String[] args) {
        String[] wordsFromFile = { "appear", "attack", "cellar", "copper",
                                   "erratic", "grotesque", "guitar", "guttural",
                                   "kittens", "mean", "suit", "trick" };
        List<byte[]> wordList = new ArrayList<>();
        for (String word : wordsFromFile) // Simulating read from file
            wordList.add(word.getBytes(StandardCharsets.US_ASCII));
        byte[][] symbolTable = wordList.toArray(new byte[wordList.size()][]);

        test(symbolTable, "abc");
        test(symbolTable, "attack");
        test(symbolTable, "car");
        test(symbolTable, "kittens");
        test(symbolTable, "xyz");
    }
    private static void test(byte[][] symbolTable, String word) {
        int idx = Arrays.binarySearch(symbolTable,
                                      word.getBytes(StandardCharsets.US_ASCII),
                                      Test::compare);
        if (idx < 0)
            System.out.println("Not found: " + word);
        else
            System.out.println("Found    : " + word);
    }
    private static int compare(byte[] w1, byte[] w2) {
        for (int i = 0, cmp; i < w1.length && i < w2.length; i++)
            if ((cmp = Byte.compare(w1[i], w2[i])) != 0)
                return cmp;
        return Integer.compare(w1.length, w2.length);
    }
}

输出

Not found: abc
Found    : attack
Not found: car
Found    : kittens
Not found: xyz