当前位置：文江博客话题详情

Java 的 Set 是否实现了 UnionFind 算法？

发布于 2024-12-26 12:55:10 字数 114 浏览 0 评论 0原文

我从 Wikipedia 知道 Union Find 算法，并且可以找到它们的小实现，但是 Java 本身是否对其 Set 使用类似的算法？如果是这样，我更愿意使用 Java Sets 而不重新编码轮子......

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

枕头说它不想醒 2025-01-02 12:55:10

Java 的 Set 接口支持与 Union Find 结构完全不同的操作（因此适用于完全不同的用例）。

回复收藏 0 原文

清泪尽 2025-01-02 12:55:10

AFAIK 不，要创建两个集合的并集，常见的方法是复制一个集合并添加第二个集合的所有元素。（或者将两个集合的所有元素复制到同一集合）例如

Set<E> set1, set2;

Set<E> union = new HashSet<E>(set1);
union.addAll(set2);

AFAIK No, to create a union of two sets, the common approach is to copy one set and add all the elements of the second. (Or copy all the element of both sets to the same set) e.g.

Set<E> set1, set2;

Set<E> union = new HashSet<E>(set1);
union.addAll(set2);

回复收藏 0 原文

腹黑女流氓 2025-01-02 12:55:10

我同意第一个答案。此外，要查找 Set 中的元素，您应该使用 contains 方法。它的签名是：

public boolean contains(Object o)

Returns true if this set contains the specified element. More formally, returns true if and only if this set contains an element e such that (o==null ? e==null : o.equals(e)).

Specified by:
    contains in interface Collection<E>

Parameters:
    o - element whose presence in this set is to be tested. 
Returns:
    true if this set contains the specified element. 
Throws:
    ClassCastException - if the type of the specified element is incompatible with this set (optional). 
    NullPointerException - if the specified element is null and this set does not support null elements (optional).

另外，这三个 Set 实现的制作方式完全不同。 HashSet 将其元素存储在哈希表中，是性能最好的实现；但是它不保证迭代的顺序。 TreeSet 将其元素存储在红黑树中，并根据元素的值对元素进行排序；它比 HashSet 慢得多。 LinkedHashSet 是作为一个哈希表实现的，其中有一个链表贯穿其中，它根据元素插入集合的顺序（插入顺序）对其元素进行排序。 LinkedHashSet 使其客户免受 HashSet 提供的未指定的、通常混乱的排序的影响，但成本仅略高一些。

I agree with the first answer. In addition, to find an element in a Set, you should use the contains method. Its signature is:

public boolean contains(Object o)

Returns true if this set contains the specified element. More formally, returns true if and only if this set contains an element e such that (o==null ? e==null : o.equals(e)).

Specified by:
    contains in interface Collection<E>

Parameters:
    o - element whose presence in this set is to be tested. 
Returns:
    true if this set contains the specified element. 
Throws:
    ClassCastException - if the type of the specified element is incompatible with this set (optional). 
    NullPointerException - if the specified element is null and this set does not support null elements (optional).

In addition, the three Set implementations are quite differently made. HashSet, which stores its elements in a hash table, is the best-performing implementation; however it makes no guarantees concerning the order of iteration. TreeSet, which stores its elements in a red-black tree, orders its elements based on their values; it is substantially slower than HashSet. LinkedHashSet, which is implemented as a hash table with a linked list running through it, orders its elements based on the order in which they were inserted into the set (insertion-order). LinkedHashSet spares its clients from the unspecified, generally chaotic ordering provided by HashSet at a cost that is only slightly higher.

回复收藏 0 原文

~没有更多了~