我遇到过多种算法,例如Flajolet-Martin算法,HyperLogLog以从元素列表中找出独特元素,并突然对Java如何计算它感到好奇?每种情况下存储和查找唯一值的时间复杂度是多少?java.util.HashSet和java.util.TreeSet使用什么算法在其结构中存储唯一值?
回答
HashSet
类型使用散列表(通常使用封闭寻址)跟踪其元素,而TreeSet
类型使用二叉搜索树来跟踪其元素。这些数据结构给出了这个问题的确切答案:“这里是这个元素吗?”对于需要100%确定地知道以前是否看到过某些内容的情况,以及它们的内存使用情况通常与目前为止所看到的元素总数成正比的情况非常有用。
另一方面,像HyperLogLog这样的基数估计器可以很好地回答“存在多少个不同的元素,给出还是占用几个百分比?”这样的问题。如果您需要粗略估计您已经看到了多少不同的东西,那么将这些东西放在散列表或二叉搜索树中的方法会占用太多内存(例如,如果您因为他们使用的内存量通常是你能够接受的东西,因为它是一个Google Web服务器,并且你希望统计访问你的不同IP地址。但是,他们不允许你回答“我在之前看过这个确切的东西吗?因此不能用作任何java.util.Set
子类型的实现。
简而言之,这里的数据结构旨在解决不同的问题。传统的BST和哈希表用于确切查询,以确定您是否已经看到某件事是目标,并且希望能够对所见的所有元素进行迭代。基数估计是很好的,你只关心有多少个完全不同的元素,你不关心它们是什么,也不需要确切的答案。
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)
。
- 1. 为每个唯一值存储过程,做计算和存储结果
- 2. 为什么最好使用UUID来存储唯一的ID值?
- 3. 在一个结构中存储函数和运算符的C++
- 4. 在这个算法中使用什么数据结构?
- 5. 使用唯一值存储时间段
- 6. java.util.HashSet不能转换为java.util.TreeSet,虽然我实现了Comparable
- 7. 使用CFDictionarySetValue()存储结构为值()
- 8. 为什么我们不能在算法和数据结构中使用参考?
- 9. 什么集合来存储树结构?
- 10. 什么数据结构被用来在networkX中存储图形?
- 11. 什么是“分散唯一性算法”?
- 12. 什么结构是存储在内存中的Python对象?
- 13. MATLAB:在结构中存储的值
- 14. 在结构数组中存储值
- 15. 澄清在Arduino中使用结构和在PROGMEM中存储结构
- 16. 用于唯一存储链接的数据结构
- 17. 使用postgresql在django hstorefield中存储唯一值
- 18. 如何使用按位运算将结构值赋值给其他结构值?
- 19. 算法建议唯一值和编辑
- 20. 为什么我的std :: set没有存储唯一值?
- 21. 我应该使用什么数据结构/ db来存储文件树结构?
- 22. 为什么Java使用堆数据结构来存储对象?
- 23. 我应该使用什么结构来存储这些对象?
- 24. 使用inet_pton存储在“”结构in6_addr“”或“结构in6_addr.sin6_addr”计算网络地址
- 25. ElasticSearch与其他存储结合使用的典型用法是什么?
- 26. 在一个文件中存储链表,保留其结构
- 27. 读取一块内存,将其存储到本地结构中
- 28. 什么样的数据结构/算法可以用来在JavaScript中检索一对值(之前和之后)
- 29. 什么是'熊猫式'数据结构存储在DataFrame中?
- 30. Firebase存储文件结构的最佳做法是什么?
java.util.Set是一个接口,而不是一个实现。在JDK库中有两个常用的实现:java.util.TreeSet和java.util.HashSet。它们都不使用HyperlogLog。 –
我也不确定这将如何适用于java.util.Set接口,因为API需要保留所有元素,并且它需要唯一性。 HyperLogLog算法估计一个**多**集(袋子)的基数,当元素太多时,要同时保存在内存中。 –
它的名字。 HashSet使用一个哈希表。 TreeSet使用树。 – Boann