我遇到过多种算法，例如 Flajolet-Martin 算法、HyperLogLog 来从元素列表中找出唯一元素，突然好奇 Java 是如何计算它的？在每种情况下存储和查找唯一值的时间复杂度是多少？
问问题
613 次
2 回答
4
Flajolet -Martin和HyperLogLog算法是关于在一个元素流的一次通过中获得不同元素的近似计数（计数不同问题N），并且具有O(N)时间和适度（比O(N)）内存使用量。
API的实现Map不需要解决“count-distinct”问题。
（除此之外：TreeMap并且HashMap 已经对映射1中的条目数进行了预先计算；即Map.size()，如果您没有遇到线程安全问题，则结果是准确的（不是近似的）。调用的成本size()是O(1)。成本维护它的O(U)地方U是执行的地图添加和删除操作的数量。）
更一般地说，Flajolet-Martin 算法或 HyperLogLog 不/不能形成Map数据结构的基础。他们没有解决字典问题。
HashMap和使用的算法TreeMap（分别是）哈希表和二叉树算法。相应的 javadocs 中有更多详细信息，您可以随时查看完整的源代码（带注释）。（例如，谷歌"java.util.HashMap" source……）
1 - 有趣的是，ConcurrentHashMap这种方式不起作用......因为更新size字段将成为并发瓶颈。相反，size()操作是O(N).
于 2017-10-22T02:26:14.377 回答
1
该HashSet类型使用哈希表（通常使用封闭寻址）TreeSet跟踪其元素，该类型使用二叉搜索树跟踪其元素。这些数据结构对“这个元素在这里吗？”这个问题给出了准确的答案。并且对于您需要 100% 确定您以前是否看过某些东西并且它们的内存使用量通常与目前看到的元素总数成正比的情况很有用。
另一方面，像 HyperLogLog 这样的基数估计器可以很好地回答“有多少不同的元素，给还是拿几个百分点？”形式的问题。它们非常适合您需要粗略估计您看到的不同事物的数量，而将所有内容放入哈希表或二叉搜索树之类的方法会占用太多内存（例如，如果您'是一个谷歌网络服务器，你想计算访问你的不同 IP 地址），因为他们使用的内存量通常是你可以提前获取的。但是，他们不允许您回答“我以前见过这个确切的东西吗？”形式的问题。因此不能作为任何子java.util.Set类型的实现。
简而言之，这里的数据结构旨在解决不同的问题。传统的 BST 和哈希表用于精确查询，其中确切地知道您是否已经看到某些东西是目标，并且您希望能够迭代所有看到的元素。基数估计器很好，你只关心有多少不同的元素，你不关心它们是什么，你不需要确切的答案。
于 2017-10-22T02:24:06.653 回答