java.util.HashSet 和 java.util.TreeSet 使用什么算法在其结构中存储唯一值？
What Algorithm is used by java.util.HashSet and java.util.TreeSet to store unique values in its structure?
我遇到过多种算法，例如 Flajolet-Martin algorithm , HyperLogLog 从元素列表中找出唯一元素，突然很好奇 Java 是如何计算的？在每种情况下存储和查找唯一值的时间复杂度是多少？
HashSet 类型使用散列 table（通常使用封闭寻址）跟踪其元素，TreeSet 类型使用二叉搜索树跟踪其元素。这些数据结构给出了问题 "is this element here?" 的准确答案，并且对于需要 100% 确定您之前是否见过某些东西的情况非常有用，并且它们的内存使用量通常与元素总数成正比到目前为止看过。
另一方面，像 HyperLogLog 这样的基数估计器非常适合回答形式为 "how many distinct elements are there, give or take a few percent?" 的问题，在您需要粗略估计您所看到的不同事物的数量时，它们非常有用，其中将所有内容放入哈希 table 或二叉搜索树中的方法会占用太多内存（例如，如果您是 Google 网络服务器并且您想要计算访问的不同 IP 地址你），因为他们使用的内存量通常是你需要提前获取的。但是，它们不允许您回答 "have I seen this exact thing before?" 形式的问题，因此不能用作任何 java.util.Set 子类型的实现。
总之，这里的数据结构是为了解决不同的问题而设计的。传统的 BST 和散列 table 用于精确查询，其中确定您是否已经看到某些东西是目标并且您希望能够迭代所有看到的元素。基数估计器在您只关心总共有多少不同元素而不关心它们是什么并且不需要确切答案的情况下非常有用。
Flajolet-Martin and HyperLogLog algorithms are about getting an approximate count of the distinct elements (the 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 不会/不能构成 Map 数据结构的基础。他们没有解决 dictionary problem.
HashMap和TreeMap使用的算法（分别）是散列table和二叉树算法。在各自的 javadoc 中有更多详细信息，完整的源代码（带注释）随时可供您查看。 （Google 对于 "java.util.HashMap" source ... 例如。）
1 - 有趣的是，ConcurrentHashMap 不会以这种方式工作...因为更新 size 字段将成为并发瓶颈。相反，size() 操作是 O(N).
我遇到过多种算法，例如 Flajolet-Martin algorithm , HyperLogLog 从元素列表中找出唯一元素，突然很好奇 Java 是如何计算的？在每种情况下存储和查找唯一值的时间复杂度是多少？
HashSet 类型使用散列 table（通常使用封闭寻址）跟踪其元素，TreeSet 类型使用二叉搜索树跟踪其元素。这些数据结构给出了问题 "is this element here?" 的准确答案，并且对于需要 100% 确定您之前是否见过某些东西的情况非常有用，并且它们的内存使用量通常与元素总数成正比到目前为止看过。
另一方面，像 HyperLogLog 这样的基数估计器非常适合回答形式为 "how many distinct elements are there, give or take a few percent?" 的问题，在您需要粗略估计您所看到的不同事物的数量时，它们非常有用，其中将所有内容放入哈希 table 或二叉搜索树中的方法会占用太多内存（例如，如果您是 Google 网络服务器并且您想要计算访问的不同 IP 地址你），因为他们使用的内存量通常是你需要提前获取的。但是，它们不允许您回答 "have I seen this exact thing before?" 形式的问题，因此不能用作任何 java.util.Set 子类型的实现。
总之，这里的数据结构是为了解决不同的问题而设计的。传统的 BST 和散列 table 用于精确查询，其中确定您是否已经看到某些东西是目标并且您希望能够迭代所有看到的元素。基数估计器在您只关心总共有多少不同元素而不关心它们是什么并且不需要确切答案的情况下非常有用。
Flajolet-Martin and HyperLogLog algorithms are about getting an approximate count of the distinct elements (the 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 不会/不能构成 Map 数据结构的基础。他们没有解决 dictionary problem.
HashMap和TreeMap使用的算法（分别）是散列table和二叉树算法。在各自的 javadoc 中有更多详细信息，完整的源代码（带注释）随时可供您查看。 （Google 对于 "java.util.HashMap" source ... 例如。）
1 - 有趣的是，ConcurrentHashMap 不会以这种方式工作...因为更新 size 字段将成为并发瓶颈。相反，size() 操作是 O(N).