java.util.HashSet 和 java.util.TreeSet 使用什么算法在其结构中存储唯一值？

Question

我遇到过多种算法，例如 Flajolet-Martin 算法、HyperLogLog 来从元素列表中找出唯一元素，突然好奇 Java 是如何计算的？在每种情况下存储和查找唯一值的时间复杂度是多少？

Answer 1

Flajolet-Martin和HyperLogLog算法旨在通过时间和适度（比 好得多）的内存使用量，在元素流的一次传递中获取不同元素的近似计数（不同计数问题） 。NO(N)O(N)

API的实现Map不需要解决“count-distinct”问题。

（旁白：TreeMap并且HashMap 已经保留了映射¹中条目数量的预先计算的计数；即Map.size()。如果您没有陷入线程安全问题，则结果是准确的（不是近似的）。调用的成本size()是O(1)。成本维护它的方法是执行地图添加和删除操作的O(U)次数U。）

更一般地，Flajolet-Martin 算法或 HyperLogLog 不/不能形成数据结构的基础Map。他们没有解决字典问题。

HashMap和使用的算法TreeMap分别是哈希表和二叉树算法。相应的 javadoc 中有更多详细信息，并且完整的源代码（带注释）可供您查看。"java.util.HashMap" source（例如，谷歌...）

^{1 - 有趣的是，ConcurrentHashMap这种方式不起作用......因为更新size字段将成为并发瓶颈。相反，size()操作是O(N).}