Какая структура данных подходит для хранения значений без повторений?

Ответ на вопрос собеседования

Для хранения значений без повторений в программировании используются Set-подобные структуры данных. В контексте Android-разработки на Kotlin/Java наиболее подходящими являются реализации интерфейса Set, которые гарантируют уникальность элементов.

Основные реализации Set в Kotlin/Java:

1. HashSet (java.util.HashSet / kotlin.collections.HashSet)
   • Основан на хеш-таблице
   • Гарантирует уникальность через механизм хеширования
   • Не сохраняет порядок добавления элементов
   • Операции добавления, удаления и поиска в среднем выполняются за O(1)

val uniqueNumbers = HashSet<Int>()
uniqueNumbers.add(1)
uniqueNumbers.add(2)
uniqueNumbers.add(1) // Этот элемент не будет добавлен
println(uniqueNumbers) // Вывод: [1, 2]

1. LinkedHashSet (java.util.LinkedHashSet)
   • Расширяет HashSet, сохраняя порядок вставки элементов
   • Имеет немного большую overhead по памяти из-за поддержания linked list
   • Полезен, когда важен порядок добавления элементов

val orderedSet = LinkedHashSet<String>()
orderedSet.add("Apple")
orderedSet.add("Banana")
orderedSet.add("Apple") // Не добавится
orderedSet.add("Cherry")
println(orderedSet) // Вывод: [Apple, Banana, Cherry] (сохраняется порядок)

1. TreeSet (java.util.TreeSet)
   • Основан на красно-черном дереве
   • Хранит элементы в отсортированном порядке (естественном или через Comparator)
   • Операции выполняются за O(log n)
   • Полезен, когда нужна сортировка элементов

val sortedSet = TreeSet<Int>()
sortedSet.add(5)
sortedSet.add(2)
sortedSet.add(8)
sortedSet.add(2) // Не добавится
println(sortedSet) // Вывод: [2, 5, 8] (отсортированный порядок)

1. Kotlin-специфичные Set-коллекции:
   • mutableSetOf() - создает MutableSet (по умолчанию реализация - LinkedHashSet)
   • setOf() - создает неизменяемый Set

// MutableSet (обычно LinkedHashSet под капотом)
val mutableSet = mutableSetOf("A", "B", "C")
mutableSet.add("A") // Не добавится

// Неизменяемый Set
val immutableSet = setOf(1, 2, 3, 1) // Будет содержать только [1, 2, 3]

Критерии выбора реализации:

• Если важен быстрый доступ и порядок не важен → HashSet
• Если нужно сохранить порядок добавления → LinkedHashSet или mutableSetOf()
• Если нужна автоматическая сортировка → TreeSet
• Для неизменяемых коллекций → setOf()

Особенности в Android-разработке:

1. Memory considerations: HashSet обычно более эффективен по памяти, чем LinkedHashSet
2. Performance: Для небольших коллекций (до 100 элементов) разница в производительности незначительна
3. Thread safety: Все стандартные реализации Set не являются потокобезопасными. Для многопоточности используйте:
   • Collections.synchronizedSet()
   • ConcurrentHashMap.newKeySet() (в Java 8+)
   • Kotlin корутины с потокобезопасными коллекциями

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

class UniqueItemsRepository {
    private val uniqueItems = mutableSetOf<String>()
    
    fun addItem(item: String): Boolean {
        return uniqueItems.add(item) // Возвращает true, если элемент был добавлен
    }
    
    fun getItems(): Set<String> {
        return uniqueItems.toSet() // Возвращаем неизменяемую копию
    }
    
    fun containsItem(item: String): Boolean {
        return item in uniqueItems // Проверка за O(1) в среднем
    }
}

Ключевой вывод: Для хранения уникальных значений в Android/Kotlin разработке оптимально использовать реализацию MutableSet через mutableSetOf() для изменяемых коллекций или setOf() для неизменяемых, так как это обеспечивает читаемость кода и под капотом дает оптимальную реализацию для большинства случаев использования.