Эффективные структуры данных: множества и словари

Оптимизация кода на Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Применение пространственной и временной сложности

Теперь мы знаем о пространственной и временной сложности!

Как применить эти знания для написания более эффективного кода?

Выбирайте подходящую структуру данных!

Система управления пользователями

Мы создаём систему управления пользователями
Нужно проверить, существует ли пользователь с заданным именем
С использованием списка: сложность $O(n)$

public boolean usernameExists(ArrayList<String> users, String newUsername) {
    for (String username : users) {
        if (username.equals(newUsername)) {
            return true;
        }
    }
    return false;
}

Множества (Sets)

Коллекция уникальных элементов с быстрым поиском
Средняя временная сложность $O(1)$ для добавления, удаления и проверки наличия элемента

Улучшенное решение для системы управления пользователями:

public class UserRegistry {
    private HashSet<String> users = new HashSet<>();

    public boolean userExists(String username) {
        return users.contains(username); // O(1) average time
    }
}

Словари (Maps)

Как словарь: слово (ключ) → определение (значение)
HashMap: средняя временная сложность $O(1)$ для всех операций

public class UserCache {
    private HashMap<String, UserProfile> userProfiles = new HashMap<>();

    public UserProfile getUser(String username) {
        return userProfiles.get(username);  // O(1) average time
    }
}

Метод hashcode

Залог быстрой работы — метод hashCode()
В примере с ArrayList мы не знали индекс нужного имени пользователя
Метод hashcode() преобразует объект в индекс, по которому можно выполнить поиск
Например: pavlos.2020 -> 35189

pavlos.2020 обрабатывается через hashcode и даёт результат 35189

Индексирование элементов

В основе HashMap и HashSet лежит обычный массив
При добавлении элемента:
- Java вызывает hashCode() на элементе и получает целое число
- Затем применяет операцию по модулю, чтобы определить номер «корзины»

Пример:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

"optimizingCodeInJava" -> 1406313774 // Implemented by Java
1406313774 % 16 = 14 <- that's our bucket!

Коллизии

Когда несколько элементов попадают в одну «корзину»
- Это называется коллизией
Для такой «корзины» используется LinkedList
Именно поэтому говорят $O(1)$ в среднем

Важный вывод

Выбор структуры данных похож на выбор подходящего инструмента: молоток (ArrayList) отлично справляется с гвоздями, но бесполезен для шурупов — а вот Set может оказаться именно тем, что нужно.

Инструменты

Давайте потренируемся!

Оптимизация кода на Java