Реализует ли Java Set алгоритм UnionFind? - PullRequest
Новая
       18

Реализует ли Java Set алгоритм UnionFind?

4 голосов
/ 12 января 2012

Я знаю алгоритм Union Find из Википедии и могу найти их небольшие реализации, но использует ли сама Java аналогичный алгоритм для своего Set?Если это так, я бы предпочел использовать наборы Java без перекодирования колеса ...

Ответы [ 3 ]

3 голосов
/ 12 января 2012

Java-интерфейс Set поддерживает совершенно разные операции (и поэтому подходит для совершенно разных вариантов использования), что структура Union Find.

1 голос
/ 12 января 2012

AFAIK Нет, чтобы создать объединение двух наборов, общий подход состоит в том, чтобы скопировать один набор и добавить все элементы второго.(Или скопируйте все элементы обоих наборов в один и тот же набор), например 

Set<E> set1, set2;

Set<E> union = new HashSet<E>(set1);
union.addAll(set2);
0 голосов
/ 12 января 2012

Я согласен с первым ответом. Кроме того, чтобы найти элемент в наборе, вы должны использовать метод 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, по цене, которая лишь немного выше.

...