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

-1

我遇到过多种算法，例如Flajolet-Martin算法，HyperLogLog以从元素列表中找出独特元素，并突然对Java如何计算它感到好奇？每种情况下存储和查找唯一值的时间复杂度是多少？java.util.HashSet和java.util.TreeSet使用什么算法在其结构中存储唯一值？

来源

2017-10-22 Maruthi Adithya

java.util.Set是一个接口，而不是一个实现。在JDK库中有两个常用的实现：java.util.TreeSet和java.util.HashSet。它们都不使用HyperlogLog。 –

我也不确定这将如何适用于java.util.Set接口，因为API需要保留所有元素，并且它需要唯一性。 HyperLogLog算法估计一个**多**集（袋子）的基数，当元素太多时，要同时保存在内存中。 –

它的名字。 HashSet使用一个哈希表。 TreeSet使用树。 – Boann

HashSet类型使用散列表（通常使用封闭寻址）跟踪其元素，而TreeSet类型使用二叉搜索树来跟踪其元素。这些数据结构给出了这个问题的确切答案：“这里是这个元素吗？”对于需要100％确定地知道以前是否看到过某些内容的情况，以及它们的内存使用情况通常与目前为止所看到的元素总数成正比的情况非常有用。

另一方面，像HyperLogLog这样的基数估计器可以很好地回答“存在多少个不同的元素，给出还是占用几个百分比？”这样的问题。如果您需要粗略估计您已经看到了多少不同的东西，那么将这些东西放在散列表或二叉搜索树中的方法会占用太多内存（例如，如果您因为他们使用的内存量通常是你能够接受的东西，因为它是一个Google Web服务器，并且你希望统计访问你的不同IP地址。但是，他们不允许你回答“我在之前看过这个确切的东西吗？因此不能用作任何java.util.Set子类型的实现。

简而言之，这里的数据结构旨在解决不同的问题。传统的BST和哈希表用于确切查询，以确定您是否已经看到某件事是目标，并且希望能够对所见的所有元素进行迭代。基数估计是很好的，你只关心有多少个完全不同的元素，你不关心它们是什么，也不需要确切的答案。

来源

2017-10-22 02:24:06 templatetypedef

Flajolet-Martin和HyperLogLog算法大约与O(N)时间和适度的内存使用情况（比O(N)好得多）N元流中的一个通得到不同元件（所述count-distinct problem）的近似计数。

Map API的实现不需要“计数不同”问题的解决方案。

（旁白：TreeMap和HashMap已经保持条目数的预计算的计数在地图，即Map.size()前提是你不进入线程安全问题的结果是准确的（不是。近似）调用size()的成本是O(1)，维护它的费用是O(U)其中U是进行地图的添加和删除操作的次数）。

更一般地，Flajolet马丁算法或HyperLogLog不/不能形成的基础10数据结构。他们没有解决dictionary problem。

HashMap和TreeMap所使用的算法分别是散列表和二叉树算法。在各自的javadoc中有更多的细节，完整的源代码（带注释）随时可供您查看。（Google为"java.util.HashMap" source ...为例。）

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

来源

2017-10-22 02:26:14

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

回答

相关问题