Как устроен Set?

Устройство Set в Java/Android (на примере HashSet)

В Android-разработке, которая базируется на Java/Kotlin, Set — это коллекция, которая не содержит дубликатов элементов. Его внутреннее устройство зависит от конкретной реализации, но наиболее распространенная — HashSet.

Основные характеристики Set

1. Уникальность элементов — главное свойство. При попытке добавления уже существующего элемента операция игнорируется.
2. Порядок элементов не гарантируется (кроме реализаций вроде LinkedHashSet и TreeSet).
3. Допускает один null элемент (в большинстве реализаций).

Внутреннее устройство HashSet

HashSet построен на основе HashMap, где элементы Set становятся ключами (keys) в Map, а значениями (values) выступает заглушка — константный объект:

// Упрощенная схема реализации HashSet
public class HashSet<E> {
    private transient HashMap<E, Object> map;
    
    // Заглушка для значений в HashMap
    private static final Object PRESENT = new Object();
    
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
}

Ключевые механизмы работы

1. Определение уникальности через hashCode() и equals()

При добавлении элемента:

• Сначала вычисляется его hashCode()
• По хэшу определяется бакет (ячейка) в хэш-таблице
• Если в бакете уже есть элементы, вызывается equals() для поочередного сравнения

// Пример на Kotlin
data class User(val id: Int, val name: String)

val set = hashSetOf<User>()
set.add(User(1, "Alice")) // Добавится
set.add(User(1, "Alice")) // Не добавится, equals() вернет true
set.add(User(1, "Bob"))   // Не добавится, если data class - equals сравнивает все поля

2. Разрешение коллизий

При совпадении хэшей разных элементов используется метод цепочки (chaining) — элементы с одинаковым хэшем хранятся в связанном списке или дереве (в Java 8+ при большом количестве коллизий список преобразуется в сбалансированное дерево).

Другие реализации Set в Android

LinkedHashSet

• Сохраняет порядок вставки элементов
• Имеет немного большую память из-за хранения дополнительных ссылок

Set<String> orderedSet = new LinkedHashSet<>();

TreeSet

• Хранит элементы отсортированными (натуральный порядок или через Comparator)
• Основан на красно-черном дереве
• Операции добавления/поиска: O(log n)

val sortedSet = TreeSet<Int>()
sortedSet.addAll(listOf(5, 2, 8, 1))
println(sortedSet) // [1, 2, 5, 8]

Производительность операций

Важно: В худшем случае (все элементы в одном бакете) HashSet деградирует до O(n).

Практическое использование в Android

1. Удаление дубликатов из коллекции

fun removeDuplicates(list: List<String>): List<String> {
    return ArrayList(LinkedHashSet(list)) // Сохраняем порядок
}

1. Кэширование проверенных данных

private val processedIds = mutableSetOf<String>()

fun processItem(id: String) {
    if (!processedIds.contains(id)) {
        // Обработка
        processedIds.add(id)
    }
}

1. Проверка уникальности полей перед сохранением в БД

Особенности для Kotlin

В Kotlin Set представлен через интерфейсы:

• Set — read-only
• MutableSet — изменяемый вариант

val immutableSet = setOf(1, 2, 3)
val mutableSet = mutableSetOf(1, 2, 3)
mutableSet.add(4)

Важные нюансы

1. Изменяемые объекты в Set — если изменяется объект, уже находящийся в Set (так, что меняется его hashCode), он может стать "потерянным".
2. Инициализационная емкость и load factor — можно указать при создании HashSet для оптимизации производительности.
3. Потокобезопасность — базовые реализации не потокобезопасны, используйте ConcurrentHashMap.newKeySet() или синхронизацию.

Понимание внутреннего устройства Set критически важно для написания эффективного Android-кода, особенно при работе с большими объемами данных или требовательных к производительности операциях.