Когда лучше использовать Set?

Когда использовать Set в Kotlin и Android

Set — это коллекция уникальных элементов без определённого порядка. Это важный инструмент для оптимизации кода и избежания дубликатов.

Set vs List: Отличия

List

val list = listOf(1, 2, 2, 3, 3, 3)
println(list.size)  // 6 элементов (дубли не удаляются)
println(list[1])    // Доступ по индексу: 2

Set

val set = setOf(1, 2, 2, 3, 3, 3)
println(set.size)   // 3 элемента (дубли удаляются)
println(set.contains(2))  // Проверка наличия

Типы Set в Kotlin

1. HashSet — Быстро

val ids = mutableSetOf<Int>()
ids.add(101)
ids.add(102)
ids.add(101)  // Дубль не добавляется

println(ids)  // [101, 102]
println(ids.contains(101))  // true, O(1) время

Характеристики:

• Неупорядоченный
• O(1) для add, remove, contains
• Хеш-таблица внутри
• Идеален для быстрых проверок

Когда использовать:

• Проверка наличия элемента
• Удаление дубликатов
• Высоконагруженные операции

2. LinkedHashSet — Порядок

val tags = linkedSetOf<String>()
tags.add("android")
tags.add("kotlin")
tags.add("android")  // Дубль не добавляется

for (tag in tags) {
    println(tag)  // android, kotlin (в порядке добавления)
}

Характеристики:

• Упорядоченный (порядок добавления)
• O(1) для операций
• Больше памяти чем HashSet
• Как LinkedList но с уникальностью

Когда использовать:

• Нужен порядок элементов
• История действий пользователя
• Последовательность просмотров

3. TreeSet — Сортированный

val scores = sortedSetOf(3, 1, 4, 1, 5, 9, 2, 6)
println(scores)  // [1, 2, 3, 4, 5, 6, 9]

for (score in scores) {
    println(score)  // В порядке возрастания
}

Характеристики:

• Отсортирован (по умолчанию по возрастанию)
• O(log n) для операций
• Red-Black tree внутри
• Поддерживает диапазоны

Когда использовать:

• Нужна сортировка
• Лидерборд
• Рейтинговые системы

Практические примеры в Android

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

// ❌ Плохо
val userIds = mutableListOf<Int>()
for (user in users) {
    if (!userIds.contains(user.id)) {  // O(n) проверка!
        userIds.add(user.id)
    }
}

// ✅ Хорошо
val userIds = users.map { it.id }.toSet()  // O(n log n)

2. Проверка прав доступа

class PermissionManager {
    private val grantedPermissions = mutableSetOf<String>()
    
    fun requestPermissions(permissions: Array<String>) {
        // Проверка очень быстро O(1)
        val notGranted = permissions.filter { 
            !grantedPermissions.contains(it) 
        }
    }
    
    fun onPermissionGranted(permission: String) {
        grantedPermissions.add(permission)
    }
}

3. Отслеживание посещённых страниц

class AnalyticsTracker {
    // LinkedHashSet сохраняет порядок просмотров
    private val visitedPages = linkedSetOf<String>()
    
    fun trackPageView(pageName: String) {
        visitedPages.add(pageName)
    }
    
    fun getPageHistory(): List<String> {
        return visitedPages.toList()
    }
}

4. Лидерборд

data class ScoreEntry(val userId: Int, val score: Int) : Comparable<ScoreEntry> {
    override fun compareTo(other: ScoreEntry) = other.score.compareTo(this.score)
}

class LeaderBoard {
    // TreeSet автоматически сортирует
    private val scores = sortedSetOf<ScoreEntry>()
    
    fun addScore(userId: Int, score: Int) {
        scores.add(ScoreEntry(userId, score))
    }
    
    fun getTop10(): List<ScoreEntry> {
        return scores.take(10)
    }
}

5. Фильтрация избранных

class FavoritesManager {
    private val favoriteIds = mutableSetOf<Long>()
    
    fun addFavorite(id: Long) {
        favoriteIds.add(id)
    }
    
    fun removeFavorite(id: Long) {
        favoriteIds.remove(id)
    }
    
    fun isFavorite(id: Long): Boolean {
        return favoriteIds.contains(id)  // O(1)!
    }
    
    fun filterFavorites(items: List<Item>): List<Item> {
        return items.filter { it.id in favoriteIds }  // O(n)
    }
}

6. Теги пользователя

data class User(
    val id: Int,
    val name: String,
    val tags: Set<String> = emptySet()  // Используем Set!
)

// Быстрая проверка тега
if ("premium" in user.tags) {
    showPremiumFeatures()
}

// Добавление тега
val newUser = user.copy(
    tags = user.tags + "verified"
)

Производительность

Сложность операций

Пример производительности

// 1 млн элементов
val n = 1_000_000

// HashSet: поиск O(1) = ~0.001ms
val hashSet = (1..n).toSet()
measureTimeMillis {
    repeat(10000) { hashSet.contains(500_000) }
}  // ~1ms

// List: поиск O(n) = ~500ms для 10k запросов
val list = (1..n).toList()
measureTimeMillis {
    repeat(10000) { list.contains(500_000) }
}  // ~500ms !!!

Best Practices

1. Используй Set для проверок: contains() намного быстрее
2. Удаляй дубли: toSet() — эффективнее чем filter
3. Выбирай правильный Set:
   • HashSet для скорости
   • LinkedHashSet если нужен порядок
   • TreeSet если нужна сортировка
4. Не переусложняй: List может быть проще для маленьких коллекций
5. Помни о памяти: Set занимает больше памяти чем List

// ❌ Плохо
if (list.contains(item)) { }  // O(n)

// ✅ Хорошо
if (item in set) { }  // O(1)

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