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

Question

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

Answer 1

Flajolet-Martin和HyperLogLog算法的目的是在 N 元素流的一次传递中获取不同元素的近似计数(count-distinct problem)，且O(N) code> 时间和适度(比 O(N) 好得多)的内存使用。

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

(旁白:TreeMap 和 HashMap 已经保留映射中条目数量的预先计算计数¹; 即 Map.size()。只要不遇到线程安全问题，结果就是准确的(不是近似的)。调用 size() 的成本> 是 O(1)。维护它的成本是 O(U)，其中 U 是执行 map 添加和删除操作的次数.)

更一般地说，Flajolet-Martin 算法或 HyperLogLog 不会/无法构成 Map 数据结构的基础。他们没有解决 dictionary problem .

HashMap和TreeMap使用的算法分别是哈希表和二叉树算法。相应的 javadoc 中有更多详细信息，并且完整的源代码(带注释)可供您查看。 (Google 搜索“java.util.HashMap”源代码 ...例如。)

<小时/>

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