Spec-Zone .ru
спецификации, руководства, описания, API
След: Наборы
Урок: Интерфейсы
Интерфейс Набора
Домашняя страница > Наборы > Интерфейсы

Интерфейс Набора

A Set a Collection это не может содержать двойные элементы. Это моделирует математическую абстракцию набора. Set интерфейс содержит только методы, наследованные от Collection и добавляет ограничение, что запрещаются двойные элементы. Set также добавляет более сильный контракт на поведении equals и hashCode операции, позволяя Set экземпляры, которые будут сравнены обоснованно, даже если их типы реализации отличаются. Два Set экземпляры равны, если они содержат те же самые элементы.

Следующее Set интерфейс.

public interface Set<E> extends Collection<E> {
    // Basic operations
    int size();
    boolean isEmpty();
    boolean contains(Object element);
    // optional
    boolean add(E element);
    // optional
    boolean remove(Object element);
    Iterator<E> iterator();

    // Bulk operations
    boolean containsAll(Collection<?> c);
    // optional
    boolean addAll(Collection<? extends E> c);
    // optional
    boolean removeAll(Collection<?> c);
    // optional
    boolean retainAll(Collection<?> c);
    // optional
    void clear();

    // Array Operations
    Object[] toArray();
    <T> T[] toArray(T[] a);
}

Платформа Java содержит три общего назначения Set реализации: HashSet, TreeSet, и LinkedHashSet. HashSet, то, который хранит его элементы в хэш-таблице, является лучше всего выполняющей реализацией; однако это не делает гарантий относительно порядка итерации. TreeSet, то, который хранит его элементы в красно-черном дереве, упорядочивает его элементы, основанные на их значениях; это существенно медленнее чем HashSet. LinkedHashSet, который реализуется, поскольку хэш-таблица со связанным списком, пробегающим это, упорядочивает свои элементы, основанные на порядке, в который они были вставлены в набор (порядок вставки). LinkedHashSet спасает его клиенты от неуказанного, обычно хаотического упорядочивания, обеспеченного HashSet по стоимости, которая только немного выше.

Вот простое, но полезное Set идиома. Предположите, что у Вас есть a Collection, c, и Вы хотите создать другого Collection содержа те же самые элементы, но со всеми устраненными копиями. Следующая острота добивается цели.

Collection<Type> noDups = new HashSet<Type>(c);

Это работает, создавая a Set (который, по определению, не может содержать копию), первоначально содержащий все элементы в c. Это использует стандартного конструктора преобразования, описанного в раздел Интерфейса Набора.

Вот незначительная разновидность этой идиомы, которая сохраняет порядок исходного набора, удаляя двойной элемент.

Collection<Type> noDups = new LinkedHashSet<Type>(c);

Следующее является универсальным методом, который инкапсулирует предыдущую идиому, возвращаясь a Set из того же самого универсального типа, поскольку передают тот.

public static <E> Set<E> removeDups(Collection<E> c) {
    return new LinkedHashSet<E>(c);
}

Интерфейс набора Основные Операции

size работа возвращает число элементов в Set (его количество элементов). isEmpty метод делает точно, что Вы думаете, что он был бы. add метод добавляет указанный элемент к Set если это уже не присутствует и возвращает булево указание, был ли элемент добавлен. Точно так же remove метод удаляет указанный элемент из Set если это присутствует и возвращает булево указание, присутствовал ли элемент. iterator метод возвращается Iterator по Set.

Следующий program берет слова в его списке параметров и распечатывает любые двойные слова, число отличных слов, и список слов с устраненными копиями.

import java.util.*;

public class FindDups {
    public static void main(String[] args) {
        Set<String> s = new HashSet<String>();
        for (String a : args)
            if (!s.add(a))
                System.out.println("Duplicate detected: " + a);

        System.out.println(s.size() + " distinct words: " + s);
    }
}

Теперь выполните программу.

java FindDups i came i saw i left

Следующий вывод производится.

Duplicate detected: i
Duplicate detected: i
4 distinct words: [i, left, saw, came]

Отметьте, что код всегда обращается к Collection его типом интерфейса (Set) а не его типом реализации (HashSet). Это - строго рекомендуемая практика программирования, потому что она дает Вам гибкость, чтобы изменить реализации просто, изменяя конструктора. Если или переменных, используемых, чтобы сохранить набор или параметры, используемые, чтобы раздать это, как объявляют, Collection's тип реализации, а не его тип интерфейса, все такие переменные и параметры должны быть изменены, чтобы изменить его тип реализации.

Кроме того нет никакой гарантии, что получающаяся программа будет работать. Если программа будет использовать какие-либо нестандартные операции, существующие в исходном типе реализации, но не в новом, то программа перестанет работать. Что касается наборов только их интерфейсом препятствует тому, чтобы Вы использовали любые нестандартные операции.

Тип реализации Set в предыдущем примере HashSet, который не делает гарантий относительно порядка элементов в Set. Если Вы хотите, чтобы программа напечатала список слов в алфавитном порядке, просто изменилась Set's тип реализации от HashSet к TreeSet. Создание этого тривиального короткого изменения заставляет командную строку в предыдущем примере генерировать следующий вывод.

java FindDups i came i saw i left
Duplicate detected: i
Duplicate detected: i
4 distinct words: [came, i, left, saw]

Операции Объема Интерфейса набора

Объемные операции особенно хорошо подходят Sets; когда применено, они выполняют алгебраические стандартным набором операции. Предположить s1 и s2 наборы. Вот то, что делают объемные операции:

Чтобы вычислить объединение, пересечение, или разность множеств двух наборов непагубно (не изменяя ни один набор), вызывающая сторона должна скопировать набор того прежде, чем вызвать соответствующую объемную работу. Следующее является получающимися идиомами.

Set<Type> union = new HashSet<Type>(s1);
union.addAll(s2);

Set<Type> intersection = new HashSet<Type>(s1);
intersection.retainAll(s2);

Set<Type> difference = new HashSet<Type>(s1);
difference.removeAll(s2);

Тип реализации результата Set в предыдущих идиомах HashSet, который является, как уже упомянуто, лучшим всесторонним Set реализация в платформе Java. Однако, любой общего назначения Set реализацией можно было заменить.

Давайте повторно посетим FindDups программа. Предположите, что Вы хотите знать, какие слова в списке параметров происходят только однажды и которые происходят не раз, но Вы не хотите копий, распечатываемых неоднократно. Этот эффект может быть достигнут, генерируя два набора — один содержащий каждое слово в списке параметров и другом содержащем только копии. Слова, которые происходят только однажды, являются разностью множеств этих двух наборов, которые мы знаем, как вычислить. Вот то, как the resulting program взгляды.


import java.util.*;

public class FindDups2 {
    public static void main(String[] args) {
        Set<String> uniques = new HashSet<String>();
        Set<String> dups    = new HashSet<String>();

        for (String a : args)
            if (!uniques.add(a))
                dups.add(a);

        // Destructive set-difference
        uniques.removeAll(dups);

        System.out.println("Unique words:    " + uniques);
        System.out.println("Duplicate words: " + dups);
    }
}

Когда выполнено с тем же самым списком параметров, используемым ранее (i came i saw i left), программа приводит к следующему выводу.

Unique words:    [left, saw, came]
Duplicate words: [i]

Менее алгебраическая единым набором работа является симметричной разностью множеств — набор элементов, содержавшихся в любом из двух указанных наборов, но не в обоих. Следующий код вычисляет симметричную разность множеств двух наборов непагубно.

Set<Type> symmetricDiff = new HashSet<Type>(s1);
symmetricDiff.addAll(s2);
Set<Type> tmp = new HashSet<Type>(s1);
tmp.retainAll(s2));
symmetricDiff.removeAll(tmp);

Операции над массивом Интерфейса набора

Операции над массивом не делают ничего специального для Sets вне того, что они делают для любого другого Collection. Эти операции описываются в разделе Интерфейса Набора.


Проблемы с примерами? Попытайтесь Компилировать и Выполнить Примеры: FAQ.
Жалобы? Поздравление? Предложения? Дайте нам свою обратную связь.

Предыдущая страница: Интерфейс Набора
Следующая страница: Интерфейс Списка