java - 在更少的内存中计算唯一的字符串

Question

我正在尝试计算从远程源获取值的过程中的唯一值。

这些值可以是数百万个数字。

我知道使用 HashSet 来获取唯一计数，但是它需要太多内存。

示例代码

long beforeUsedMem = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
        Set<String> hashSet = new HashSet<>();
        for (int index = 0; index < 1000000; index++) {
            hashSet.add(UUID.randomUUID().toString());

        }
        long afterUsedMem = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
        long actualMemUsed = beforeUsedMem - afterUsedMem;
        System.out.println("Items " + hashSet.size());
        System.out.println("Mem used: " + actualMemUsed / (1024 * 1024) + " MB");

对于 100 万个唯一字符串，哈希集需要大约 240MB 的 RAM。

我无法使用数据库来保存这些值，因此查询数据库以获得唯一值是不可能的。

还有其他方法可以获取唯一值的数量吗？

Answer 1

如果您确实对节省内存感兴趣并且可以接受最小的错误，请查看 count-distinct problem算法。

最好的例子是 HyperLogLog它可以使用几千字节的内存来计算数百万个低裕度的结果(来自维基百科:1,5kB 内存可在 10^9 个结果上实现 2% 的误差裕度)