Множества: Set, HashSet, LinkedHashSet, TreeSet

HashSet
TreeSet
SortedSet

HashSet, TreeSet и LinkedHashSet относятся к семейству Set. В множествах Set каждый элемент хранится только в одном экземпляре, а разные реализации Set используют разный порядок хранения элементов. В HashSet порядок элементов определяется по сложному алгоритму. Если порядок хранения для вас важен, используйте контейнер TreeSet, в котором объекты хранятся отсортированными по возрастанию в порядке сравнения или LinkedHashSet с хранением элементов в порядке добавления.

Множества часто используются для проверки принадлежности, чтобы вы могли легко проверить, принадлежит ли объект заданному множеству, поэтому на практике обычно выбирается реализация HashSet, оптимизированная для быстрого поиска.

В Android 11 (R) обещают добавить несколько перегруженных версий метода of(), которые являются частью Java 8.

HashSet

Название Hash... происходит от понятия хэш-функция. Хэш-функция — это функция, сужающая множество значений объекта до некоторого подмножества целых чисел. Класс Object имеет метод hashCode(), который используется классом HashSet для эффективного размещения объектов, заносимых в коллекцию. В классах объектов, заносимых в HashSet, этот метод должен быть переопределен (override).

Имеет два основных конструктора (аналогично ArrayList):

// Строит пустое множество
public HashSet()

// Строит множество из элементов коллекции
public HashSet(Collection c)

Методы

public Iterator iterator()
public int size()
public boolean isEmpty()
public boolean contains(Object o)
public boolean add(Object o)
public boolean addAll(Collection c)
public Object[] toArray()
public boolean remove(Object o)
public boolean removeAll(Collection c)
public boolean retainAll(Collection c) - (retain — сохранить). Выполняет операцию "пересечение множеств".
public void clear()
public Object clone()

Методы аналогичны методам ArrayList за исключением того, что метод add(Object o) добавляет объект в множество только в том случае, если его там нет. Возвращаемое методом значение — true, если объект добавлен, и false, если нет.

Перейдём к практике. Как это ни странно, но в жизни встречаются несколько Барсиков, Мурзиков и прочих Рыжиков. Несмотря на одинаковые имена, каждый кот неповторим. Надеюсь, с этим никто не спорит. Но пихать имена котов в множество HashSet не стоит, так как в множестве может храниться только одно имя и двух Мурзиков тут не записать. Другое дело - страны. Не может быть двух Франций, двух Англий, двух Россий (даже партия такая есть Единая Россия, впрочем мы отвлеклись).

Итак, создадим множество стран.


public void onClick(View view) {
    HashSet<String> countryHashSet = new HashSet<>();
    countryHashSet.add("Россия");
    countryHashSet.add("Франция");
    countryHashSet.add("Гондурас");
    countryHashSet.add("Кот-Д'Ивуар"); // любимая страна всех котов

    // Получим размер HashSet
    mInfoTextView.setText("Размер HashSet = " + countryHashSet.size());
}

Нажав на кнопку, вы получите результат Размер HashSet = 4.

Даже если вы попытаетесь схитрить и дополнительно вставить строку countryHashSet.add("Кот-Д'Ивуар"); после России, то всё-равно размер останется прежним.

Убедиться в этом можно, если вызвать метод iterator(), который позволяет получить всё множество элементов:


public void onClick(View view) {
    HashSet<String> countryHashSet = new HashSet<>();
    countryHashSet.add("Россия");
    countryHashSet.add("Кот-Д'Ивуар"); // любимая страна всех котов
    countryHashSet.add("Франция");
    countryHashSet.add("Гондурас");
    countryHashSet.add("Кот-Д'Ивуар"); // кот попросил добавить ещё раз для надёжности

    Iterator<String> iterator = countryHashSet.iterator();
    while (iterator.hasNext()) {
        mInfoTextView.setText(mInfoTextView.getText() + iterator.next()
                + ", ");
    }
}

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

Стоит отметить, что порядок добавления стран во множество будет непредсказуемым. HashSet использует хэширование для ускорения выборки. Если вам нужно, чтобы результат был отсортирован, то пользуйтесь TreeSet.

Преобразовать в массив и вывести в ListView

Следующий пример - задел на будущее. Когда вы узнаете, что такое ListView, то вернитесь к этому уроку и узнайте, как сконвертировать множество в массив и вывести результат в компонент ListView (Список):


public void onClick(View view) {

    ArrayAdapter<String> adapter;

    HashSet<String> countryHashSet = new HashSet<>();
    countryHashSet.add("Россия");
    countryHashSet.add("Кот-Д'Ивуар"); // любимая страна всех котов
    countryHashSet.add("Франция");
    countryHashSet.add("Гондурас");

    // Конвертируем HashSet в массив
    String[] myArray = {};
    myArray = countryHashSet.toArray(new String[countryHashSet.size()]);

    // Выводим массив в ListView
    final ListView listView = (ListView) findViewById(R.id.listView);
    adapter = new ArrayAdapter<>(this,
            android.R.layout.simple_list_item_1, myArray);
    listView.setAdapter(adapter);
}

Продолжим опыты. Поработаем теперь с числами.


public void onClick(View view) {

    Random random = new Random(30);
    Set<Integer> numberSet = new HashSet<>();

    for(int i = 0; i < 1000; i++)
        numberSet.add(random.nextInt(10));
    mInfoTextView.setText(numberSet.toString());
}

Здесь мы ещё раз убеждаемся, что повторное добавление числа не происходит. В цикле случайным образом выбирается число от 0 до 9 тысячу раз. Естественно, многие числа должны были повториться при таком сценарии, но во множество каждое число попадёт один раз.

При этом данные не сортируются, так как расположены как попало.

Специально для Android был разработан новый класс ArraySet, который более эффективен.


ArraySet<K,V> = HashSet<K,V>

LinkedHashSet

Класс LinkedHashSet расширяет класс HashSet, не добавляя никаких новых методов. Класс поддерживает связный список элементов набора в том порядке, в котором они вставлялись. Это позволяет организовать упорядоченную итерацию вставки в набор.

TreeSet

Переделанный пример для вывода случайных чисел в отсортированном порядке. HashSet не может гарантировать, что данные будут отсортированы, так как работает по другому алгоритму. Если сортировка для вас важна, то используйте TreeSet.


public void onClick(View view) {
    Random random = new Random(30);
    SortedSet<Integer> numberSet = new TreeSet<>();

    for(int i = 0; i < 1000; i++)
        numberSet.add(random.nextInt(10));
    mInfoTextView.setText(numberSet.toString());
}

Со строками это выглядит нагляднее:


public void onClick(View view) {

    SortedSet<String> countrySet = new TreeSet<>();
    countrySet.add("Россия");
    countrySet.add("Франция");
    countrySet.add("Гондурас");
    countrySet.add("Кот-Д'Ивуар"); // любимая страна всех котов

    mInfoTextView.setText(countrySet.toString());
}

Названия стран выведутся в алфавитном порядке.

Класс TreeSet создаёт коллекцию, которая для хранения элементов применяет дерево. Объекты сохраняются в отсортированном порядке по возрастанию.

SortedSet

В примере с TreeSet использовался интерфейс SortedSet, который позволяет сортировать элементы множества. По умолчанию сортировка производится привычным способом, но можно изменить это поведение через интерфейс Comparable.

Кроме стандартных методов Set у интерфейса есть свои методы.

Comparator comparator()
subSet(Object fromElement, Object toElement)
tailSet(Object fromElement)
headSet(Object toElement)
Object first()
Object last()


SortedSet<String> animalSet = new TreeSet();
animalSet.add("Antilope");
animalSet.add("Fox");
animalSet.add("Goat");
animalSet.add("Dog");
animalSet.add("Elephant");
animalSet.add("Bear");
animalSet.add("Hippo");
animalSet.add("Cat");

Iterator iterator = animalSet.iterator();

while(iterator.hasNext()){
    // Antilope Bear Cat Dog Elephant Fox Goat Hippo
    mInfoTextView.append(iterator.next().toString() + " ");
}

Log.i(TAG, animalSet.subSet("Dog", "Hippo").toString()); // [Dog, Elephant, Fox, Goat]
Log.i(TAG, animalSet.tailSet("Dog").toString()); // [Dog, Elephant, Fox, Goat, Hippo]
Log.i(TAG, animalSet.headSet("Dog").toString()); // [Antilope, Bear, Cat]
Log.i(TAG, animalSet.first()); // Antilope
Log.i(TAG, animalSet.last()); // Hippo