I know the Union Find algorithm from Wikipedia, and can find small implementations of them, but does Java itself use a similar algorithm for its Set's? If so I'd prefer to use Java Sets without recoding the wheel...
3 Answers
Java's Set interface supports completely different operations (and is therefore appropriate for completely different use cases) that a Union Find structure.
-
Does Java have a Disjoin-Set data structure? now im using HashMap<S,C> from simplices to complexes, where each complex remembers its set of simplices Jan 13, 2012 at 12:35
-
@propaganda: There's nothing in the standard API, but I'm sure you can find implementations on the internet. Jan 13, 2012 at 12:37
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);
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.