Ефективні структури даних: Set і Map

Оптимізація коду в Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Застосування складності пам'яті/часу

Тепер ми знаємо про складність за пам'яттю та часом!

Як застосувати це, щоб писати ефективніший код?

Обирайте правильну структуру даних!

Оптимізація коду в Java

Система керування користувачами

  • Ми будуємо систему керування користувачами

  • Треба перевіряти для заданого імені користувача, чи існує користувач

  • Використовуючи список: складність $O(n)$

public boolean usernameExists(ArrayList<String> users, String newUsername) {
    for (String username : users) {
        if (username.equals(newUsername)) {
            return true;
        }
    }
    return false;
}
Оптимізація коду в Java

Set-и

  • Колекція унікальних елементів із швидким пошуком
  • Середня складність $O(1)$ для додавання, видалення та перевірки наявності елемента

Поліпшене рішення для керування користувачами:

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

    public boolean userExists(String username) {
        return users.contains(username); // O(1) average time
    }
}
Оптимізація коду в Java

Map-и

  • Як словник: слово (ключ) -> тлумачення (значення)
  • 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
    }
}
Оптимізація коду в Java

Метод hashCode

  • Що робить їх швидкими -> hashCode()
  • У прикладі з ArrayList ми не знали індекс імені користувача
  • Метод hashCode() дає змогу перетворити об'єкт на індекс для пошуку
  • Наприклад, pavlos.2020 -> 35189

pavlos.2020 оброблено через hashCode, у результаті 35189

Оптимізація коду в Java

Індексація елементів

  • HashMap і HashSet мають підкладений масив
  • Коли додаємо елемент:
    • Java викликає hashCode() для елемента, щоб отримати ціле число
    • Застосовує модуль за цим числом, щоб отримати номер бакета

Приклад:

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

"optimizingCodeInJava" -> 1406313774 // Реалізовано в Java
1406313774 % 16 = 14 <- це наш бакет!
Оптимізація коду в Java

Колізії

  • Коли кілька елементів потрапляють у той самий бакет
    • Це називається колізія
  • Для бакета використовується LinkedList
  • Тому ми кажемо $O(1)$ у середньому
Оптимізація коду в Java

Варто запам'ятати

Вибір структури даних — як вибір інструмента: молоток (ArrayList) добрий для цвяхів, але поганий для гвинтів (де краще підійде Set).

Інструменти

Оптимізація коду в Java

Давайте потренуємось!

Оптимізація коду в Java

Preparing Video For Download...