java使用什么算法。util。HashSet和java。util。树集在其结构中存储唯一值?

Flajolet-Martin 和 HyperLogLog 算法是关于获取 近似 不同元素的计数( count-distinct problem )在一条溪流中 N 具有的元素 O(N) 时间和谦逊(比 O(N) )内存使用情况。

Map API不需要解决“count distinct”问题。

(旁白: TreeMap 和 HashMap 保留映射中条目数的预计算计数 ^1. ; 即 Map.size() . 如果你没有陷入线程安全问题,结果是准确的(不是近似的)。通话费用 size() 是 O(1) . 维护它的成本是 O(U) U

更一般而言,Flajolet-Martin算法或HyperLogLog不/不能构成 地图 dictionary problem .

使用的算法 哈希图 树图 分别是哈希表和二叉树算法。在各自的Javadoc中有更多详细信息,完整的源代码(带注释)随时可供您查看。(谷歌 "java.util.HashMap" source ... 例如。)

^{1-有趣的是, ConcurrentHashMap size 字段将成为并发瓶颈。相反 大小() O(N) .}

这个 HashSet TreeSet 类型使用二进制搜索树跟踪其元素。这些数据结构准确地回答了“这个元素在这里吗?”对于需要百分之百确定之前是否见过某个东西的情况,它们非常有用,并且它们的内存使用量通常与迄今为止看到的元素总数成正比。

另一方面,像HyperLogLog这样的基数估计器很适合回答这样的问题:“有多少不同的元素,给或取几个百分比?”当你需要粗略估计你看到了多少不同的东西,将所有东西放在哈希表或二叉搜索树中这样的方法会占用太多内存(例如,如果你是一个Google web服务器,你想计算访问你的不同IP地址),它们非常适合,因为它们使用的内存量通常是您需要提前获取的。然而,他们不允许你回答“我看到了吗?” 这正是以前的事 ?“因此不能作为任何 java.util.Set

简而言之,这里的数据结构旨在解决不同的问题。传统的BST和哈希表用于精确查询,其中确定是否看到了某些内容是目标,并且希望能够(比如)迭代看到的所有元素。基数估计器很好,你只关心有多少个完全不同的元素,你不关心它们是什么,你不需要精确的答案。