Как выбрать нужную коллекцию под задачу в Java?

Выбор нужной коллекции в Java

Java Collections Framework предоставляет множество реализаций для работы с группами объектов. Выбор правильной коллекции критичен для производительности и корректности программы. Давайте разберемся в основных типах и их применении.

Иерархия коллекций

Collection
├── List (упорядоченные, дубли разрешены)
│   ├── ArrayList
│   ├── LinkedList
│   └── CopyOnWriteArrayList
├── Set (уникальные элементы)
│   ├── HashSet
│   ├── LinkedHashSet
│   ├── TreeSet
│   └── ConcurrentHashMap.newKeySet()
└── Queue (FIFO и приоритеты)
    ├── LinkedList
    ├── PriorityQueue
    ├── Deque
    └── BlockingQueue

Map (ключ-значение)
├── HashMap
├── LinkedHashMap
├── TreeMap
├── ConcurrentHashMap
└── WeakHashMap

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

ArrayList — DEFAULT для большинства случаев

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

• Быстрый доступ по индексу: O(1)
• Медленная вставка/удаление в середину: O(n)
• Потокобезопасность: нет
• Память: непрерывный блок

public class UserService {
    // Применение: нужно часто обращаться по индексу
    private List<User> users = new ArrayList<>();

    public void process() {
        // ✓ Быстро
        User first = users.get(0);
        User last = users.get(users.size() - 1);

        // ✓ OK (редко)
        users.add(new User());

        // ✗ Избегай (медленно в большом списке)
        users.add(0, new User()); // O(n)
    }
}

LinkedList — для частых операций в начале/конце

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

• Вставка/удаление в начало: O(1)
• Доступ по индексу: O(n)
• Память: разреженная (Node objects)
• Реализует Deque: можно использовать как очередь

public class TaskQueue {
    // Применение: нужны операции с обоих концов
    private Deque<Task> tasks = new LinkedList<>();

    public void enqueue(Task task) {
        tasks.addLast(task);     // ✓ O(1)
    }

    public Task dequeue() {
        return tasks.removeFirst(); // ✓ O(1)
    }

    public void addPriority(Task task) {
        tasks.addFirst(task);    // ✓ O(1), ArrayList был бы O(n)
    }
}

CopyOnWriteArrayList — для многопоточного чтения

public class EventDispatcher {
    // Применение: много читателей, редкие записи
    private List<EventListener> listeners = new CopyOnWriteArrayList<>();

    public void subscribe(EventListener listener) {
        listeners.add(listener); // Медленно (копирует весь массив)
    }

    public void fireEvent(Event event) {
        // ✓ Быстро и безопасно для многопоточности
        for (EventListener listener : listeners) {
            listener.onEvent(event);
        }
    }
}

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

HashSet — для уникальных элементов без порядка

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

• Поиск: O(1) в среднем
• Добавление/удаление: O(1) в среднем
• Порядок: не гарантирован
• Синхронизация: нет

public class DuplicateFilter {
    // Применение: удалить дубликаты
    private Set<String> seen = new HashSet<>();

    public boolean isNew(String value) {
        return seen.add(value); // true если добавлено (было новым)
    }

    // Очистка дубликатов в коллекции
    List<String> items = Arrays.asList("a", "b", "a", "c", "b");
    List<String> unique = new ArrayList<>(new HashSet<>(items));
}

LinkedHashSet — для уникальных элементов с сохранением порядка

public class CacheWithOrder {
    // Применение: нужен порядок добавления, но без дубликатов
    private Set<String> cache = new LinkedHashSet<>();

    public void add(String key) {
        cache.add(key);
    }

    // Итерация в порядке добавления
    public void printInOrder() {
        for (String key : cache) {
            System.out.println(key); // Порядок добавления сохраняется
        }
    }
}

TreeSet — для отсортированных уникальных элементов

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

• Поиск: O(log n)
• Итерация в порядке: O(n log n)
• Требует сравнения: Comparable или Comparator

public class RangeQuery {
    // Применение: нужны элементы в сортированном виде и диапазоны
    private TreeSet<Integer> scores = new TreeSet<>();

    public void addScore(int score) {
        scores.add(score);
    }

    public Set<Integer> getScoresInRange(int min, int max) {
        return scores.subSet(min, true, max, true); // ✓ O(log n)
    }

    public int getMedian() {
        // ✓ Элементы в порядке
        return scores.stream()
            .skip(scores.size() / 2)
            .findFirst()
            .orElse(0);
    }
}

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

HashMap — для быстрого поиска по ключу

public class UserCache {
    // Применение: быстрый поиск по ID
    private Map<Long, User> usersById = new HashMap<>();

    public void cache(User user) {
        usersById.put(user.getId(), user); // O(1)
    }

    public User find(Long id) {
        return usersById.get(id); // ✓ O(1) - очень быстро
    }
}

LinkedHashMap — HashMap с сохранением порядка

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    // Применение: LRU кеш (недавно использованные элементы в конце)
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(16, 0.75f, true); // true = порядок доступа
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize; // Удали самый старый при переполнении
    }
}

TreeMap — отсортированная Map

public class PriceRange {
    // Применение: нужны элементы по диапазону ключей
    private TreeMap<Date, Double> prices = new TreeMap<>();

    public Map<Date, Double> getPricesAfter(Date date) {
        return prices.tailMap(date); // ✓ O(log n)
    }

    public Map<Date, Double> getPricesBetween(Date start, Date end) {
        return prices.subMap(start, end); // ✓ Диапазон
    }
}

ConcurrentHashMap — многопоточная Map

public class SessionManager {
    // Применение: множество потоков пишут/читают одновременно
    private Map<String, Session> sessions = new ConcurrentHashMap<>();

    public void registerSession(String sessionId, Session session) {
        sessions.put(sessionId, session); // ✓ Потокобезопасно
    }

    public Session getSession(String sessionId) {
        return sessions.get(sessionId); // ✓ Быстро, потокобезопасно
    }
}

Чеклист выбора коллекции

1. Нужны ли уникальные элементы?
   ✓ Да → Set (HashSet, LinkedHashSet, TreeSet)
   ✗ Нет → List (ArrayList, LinkedList) или Map

2. Нужна ли сортировка?
   ✓ Да → TreeSet, TreeMap (или сортируй List отдельно)
   ✗ Нет → Hash* варианты

3. Часто ли обращаешься по индексу?
   ✓ Да → ArrayList
   ✗ Нет → LinkedList для Deque, или Set/Map

4. Нужен ли порядок вставки?
   ✓ Да → LinkedHashSet, LinkedHashMap, LinkedList
   ✗ Нет → HashSet, HashMap

5. Многопоточный код?
   ✓ Да → ConcurrentHashMap, CopyOnWriteArrayList
   ✗ Нет → обычные реализации быстрее

6. Нужны ли диапазоны?
   ✓ Да → TreeSet, TreeMap (subSet, headSet, tailSet)
   ✗ Нет → Hash* варианты

Сравнительная таблица производительности

Практический пример: Выбор для задачи

public class ShoppingCart {
    // ArrayList: нужен порядок, часто читаем, редко удаляем из середины
    private List<CartItem> items = new ArrayList<>();

    // HashMap: быстрый поиск товара по ID
    private Map<Long, CartItem> itemsById = new HashMap<>();

    // TreeSet: уникальные категории товаров в сортированном виде
    private Set<String> categories = new TreeSet<>();

    public void addItem(CartItem item) {
        items.add(item);
        itemsById.put(item.getProductId(), item);
        categories.add(item.getCategory());
    }

    public CartItem findById(Long productId) {
        return itemsById.get(productId); // O(1) вместо O(n)
    }

    public List<CartItem> getItems() {
        return new ArrayList<>(items); // Сохраняет порядок
    }
}

Заключение

Правильный выбор коллекции — это баланс между:

• Производительностью (временная сложность операций)
• Памятью (пространственная сложность)
• Функциональностью (нужны ли порядок, уникальность, диапазоны)
• Многопоточностью (требуется ли синхронизация)

Начни с ArrayList и HashMap, затем специализируй под конкретные требования.