LinkedList, HashSet, HashMap

Знакомимся с другими популярными коллекциями Java: LinkedList для последовательного доступа, HashSet для уникальных элементов и HashMap для пар ключ-значение

Введение: разнообразие коллекций

В прошлом уроке мы познакомились с ArrayList — самым простым и популярным типом коллекции. Но в реальном программировании одних универсальных списков часто недостаточно. У разных задач разные потребности: где-то важна скорость вставки в начало, где-то — гарантия уникальности, а где-то — работа с парами «ключ-значение».

Представьте, что вы строите дом. Для стен вам нужны кирпичи, для крыши — черепица, для проводки — медные провода. Все они строительные материалы, но у каждого своя специфика. Так и коллекции: все они хранят данные, но каждая оптимизирована под свою задачу.

В этом уроке мы разберём три важнейшие коллекции: LinkedList (связный список), HashSet (множество) и HashMap (словарь). Каждая из них решает свою проблему и используется в определённых сценариях.

LinkedList — связный список

LinkedList — это реализация интерфейса List, которая хранит элементы не в непрерывном массиве, а в виде цепочки связанных объектов. Каждый элемент (называемый узлом или нодой) содержит значение и ссылку на следующий элемент.

Аналогия из жизни: Представьте поезд. Каждый вагон связан с предыдущим и следующим специальными крюками. Чтобы добавить новый вагон в середину поезда, не нужно перестраивать весь поезд — достаточно расцепить два вагона и вставить между ними новый. Но чтобы добраться до 10-го вагона, нужно проехать через 9 предыдущих.

Вот как создаётся LinkedList:

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> cities = new LinkedList<>();

        cities.add("Москва");
        cities.add("Питер");
        cities.add("Казань");

        System.out.println(cities);
    }
}

Синтаксис почти идентичен ArrayList. Разница — только в имени класса.

Главное преимущество LinkedList: быстрая вставка и удаление в начале и середине списка. В ArrayList при вставке в середину нужно сдвинуть все последующие элементы (копирование массива). В LinkedList нужно лишь перекинуть ссылки — это работает заconstantное время O(1).

LinkedList<String> list = new LinkedList<>();

list.addFirst("Начало");
list.addLast("Конец");

list.add(1, "Середина");

System.out.println(list);
// [Начало, Середина, Конец]

LinkedList также реализует интерфейс Deque (двусторонняя очередь), поэтому он имеет дополнительные методы для работы с обоими концами списка:

LinkedList<String> list = new LinkedList<>();

list.addFirst("Первый");
list.addLast("Последний");

String first = list.getFirst();
String last = list.getLast();

System.out.println("Первый: " + first);  // Первый: Первый
System.out.println("Последний: " + last); // Последний: Последний

list.removeFirst();
list.removeLast();

System.out.println(list); // []

ArrayList vs LinkedList

Давайте подробно сравним эти две реализации списка, чтобы понять, когда что использовать.

* Амортизированно O(1) — иногда приходится расширять массив, но в среднем быстрое.

** O(1) только если уже знаете позицию (например, итератор). Если ищете позицию — это O(n).

HashSet — множество уникальных элементов

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

Аналогия: Представьте коробку с магнитами. Каждый магнит уникален — два одинаковых магнита не поместятся (один оттолкнёт другой). HashSet работает так же: он не допускает повторов.

Ещё одна важная особенность HashSet — он не сохраняет порядок элементов. Элементы могут быть в любом порядке, и этот порядок может меняться.

import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        HashSet<String> colors = new HashSet<>();

        colors.add("Красный");
        colors.add("Синий");
        colors.add("Зелёный");
        colors.add("Красный");

        System.out.println(colors);
        System.out.println("Размер: " + colors.size());
    }
}

Результат: [Зелёный, Красный, Синий] (порядок может отличаться), Размер: 3. Обратите внимание — мы добавили «Красный» дважды, но он появился только один раз. Размер списка — 3, а не 4.

Основные методы HashSet:

HashSet<String> fruits = new HashSet<>();

fruits.add("Яблоко");
fruits.add("Банан");
fruits.add("Вишня");

boolean added = fruits.add("Яблоко");
System.out.println("Добавлен: " + added); // Добавлен: false

System.out.println("Содержит банан: " + fruits.contains("Банан")); // true

fruits.remove("Банан");
System.out.println("После удаления: " + fruits);

System.out.println("Размер: " + fruits.size());
System.out.println("Пустой: " + fruits.isEmpty());

fruits.clear();
System.out.println("После очистки: " + fruits);

Обратите внимание — у HashSet нет методов get(index) или set(index), потому что элементы не имеют порядка. Вы не можете сказать «дай мне третий элемент» — их расположение случайно.

Как HashSet определяет уникальность: hashCode и equals

Когда вы добавляете элемент в HashSet, он должен определить, такой ли элемент уже есть в множестве. Для этого используются два метода: hashCode() и equals().

hashCode() возвращает числовое значение (хеш-код), которое определяет, в какой «корзине» (bucket) будет храниться элемент. Если у двух объектов разные хеш-коды, они точно разные — HashSet даже не будет сравнивать их содержимое.

equals() сравнивает содержимое двух объектов. Если хеш-коды совпали (объекты попали в одну «корзину»), вызывается equals(), чтобы точно определить, равны ли они.

Аналогия: Представьте библиотеку. Книги сортируются по алфавиту (это как хеш-код). Если вы ищете книгу на букву «Б», вам не нужно проверять все книги — только те, что стоят на полке «Б». А на полке вы сравниваете названия (это как equals).

Стандартные классы Java (String, Integer, Double и т.д.) уже имеют правильную реализацию这两个 методов. Но если вы создаёте собственный класс и хотите использовать его в HashSet, вам нужно переопределить оба метода:

import java.util.HashSet;
import java.util.Objects;

class Student {
    String name;
    int age;

    Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age && Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public String toString() {
        return name + " (" + age + ")";
    }
}

public class Main {
    public static void main(String[] args) {
        HashSet<Student> students = new HashSet<>();

        students.add(new Student("Анна", 20));
        students.add(new Student("Борис", 22));
        students.add(new Student("Анна", 20));

        System.out.println(students);
        System.out.println("Размер: " + students.size());
    }
}

Без переопределения hashCode() и equals() каждый объект считался бы уникальным (даже если имя и возраст совпадают), и размер множества был бы 3. С правильной реализацией — 2, потому что вторая Анна признана дубликатом.

LinkedHashSet и TreeSet

Помимо HashSet, есть ещё две реализации Set, которые стоит знать:

LinkedHashSet — хранит элементы в порядке добавления. Он работает немного медленнее HashSet, но зато вы точно знаете, в каком порядке элементы были добавлены:

import java.util.LinkedHashSet;

public class Main {
    public static void main(String[] args) {
        LinkedHashSet<String> colors = new LinkedHashSet<>();

        colors.add("Красный");
        colors.add("Синий");
        colors.add("Зелёный");
        colors.add("Красный");

        System.out.println(colors);
        // [Красный, Синий, Зелёный] — порядок добавления сохранён
    }
}

TreeSet — хранит элементы в отсортированном порядке. Он использует дерево вместо хеш-таблицы:

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> numbers = new TreeSet<>();

        numbers.add(5);
        numbers.add(2);
        numbers.add(8);
        numbers.add(1);
        numbers.add(5);

        System.out.println(numbers);
        // [1, 2, 5, 8] — отсортировано по возрастанию
    }
}

HashMap — словарь ключ-значение

HashMap — это реализация интерфейса Map, который хранит пары «ключ-значение». Это одна из самых полезных коллекций в Java. Она позволяет обращаться к значению по ключу заconstantное время O(1).

Аналогия: Словарь. Вы знаете слово (ключ) и хотите найти его значение. В бумажном словаре вы ищете слово по алфавиту. В HashMap значение находится мгновенно — как будто словарь сам открывается на нужной странице.

Ещё одна аналогия: шкаф с ящиками. На каждом ящике наклейка (ключ). Вы знаете, что в ящике «Носки» лежат носки, а в ящике «Рубашки» — рубашки. Вам не нужно открывать все ящики — вы сразу идёте к нужному.

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> ages = new HashMap<>();

        ages.put("Анна", 20);
        ages.put("Борис", 22);
        ages.put("Вика", 19);

        System.out.println(ages);
    }
}

Результат: {Анна=20, Борис=22, Вика=19}. Ключи — строки (имена), значения — целые числа (возраст).

Основные методы HashMap

Давайте подробно разберём все основные методы HashMap:

put(key, value) — добавляет пару ключ-значение. Если ключ уже существует, значение заменяется:

HashMap<String, Integer> ages = new HashMap<>();

ages.put("Анна", 20);
ages.put("Борис", 22);

Integer oldValue = ages.put("Анна", 21);
System.out.println("Старое значение: " + oldValue); // 20

System.out.println(ages); // {Анна=21, Борис=22}

get(key) — возвращает значение по ключу. Если ключ не найден — возвращает null:

HashMap<String, Integer> ages = new HashMap<>();
ages.put("Анна", 20);

Integer age = ages.get("Анна");
System.out.println("Возраст Анны: " + age); // 20

Integer unknown = ages.get("Дмитрий");
System.out.println("Возраст Дмитрия: " + unknown); // null

containsKey(key) — проверяет, существует ли ключ:

HashMap<String, Integer> ages = new HashMap<>();
ages.put("Анна", 20);

System.out.println(ages.containsKey("Анна"));    // true
System.out.println(ages.containsKey("Борис"));   // false

containsValue(value) — проверяет, существует ли значение:

HashMap<String, Integer> ages = new HashMap<>();
ages.put("Анна", 20);

System.out.println(ages.containsValue(20));  // true
System.out.println(ages.containsValue(25));  // false

remove(key) — удаляет пару по ключу:

HashMap<String, Integer> ages = new HashMap<>();
ages.put("Анна", 20);
ages.put("Борис", 22);

Integer removed = ages.remove("Борис");
System.out.println("Удалено: " + removed); // 22
System.out.println(ages); // {Анна=20}

size(), isEmpty(), clear() — работают аналогично другим коллекциям.

Обход HashMap

HashMap можно обходить несколькими способами. Давайте рассмотрим каждый из них.

Способ 1: Через entrySet() — самые пары:

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> ages = new HashMap<>();
        ages.put("Анна", 20);
        ages.put("Борис", 22);
        ages.put("Вика", 19);

        for (Map.Entry<String, Integer> entry : ages.entrySet()) {
            System.out.println(entry.getKey() + " — " + entry.getValue() + " лет");
        }
    }
}

Способ 2: Через keySet() — только ключи:

for (String name : ages.keySet()) {
    System.out.println(name + " — " + ages.get(name) + " лет");
}

Способ 3: Через values() — только значения:

for (Integer age : ages.values()) {
    System.out.println(age);
}

Способ 1 (entrySet) самый удобный, потому что даёт доступ и к ключу, и к значению одновременно. Способ 2 (keySet) требует дополнительного вызова get(), что немного медленнее.

LinkedHashMap и TreeMap

Как и с Set, у Map есть дополнительные реализации с особыми свойствами:

LinkedHashMap — сохраняет порядок добавления ключей:

import java.util.LinkedHashMap;

public class Main {
    public static void main(String[] args) {
        LinkedHashMap<String, Integer> ages = new LinkedHashMap<>();

        ages.put("Вика", 19);
        ages.put("Анна", 20);
        ages.put("Борис", 22);

        System.out.println(ages);
        // {Вика=19, Анна=20, Борис=22} — порядок добавления
    }
}

TreeMap — хранит ключи в отсортированном порядке:

import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        TreeMap<String, Integer> ages = new TreeMap<>();

        ages.put("Вика", 19);
        ages.put("Анна", 20);
        ages.put("Борис", 22);

        System.out.println(ages);
        // {Анна=20, Борис=22, Вика=19} — отсортировано по алфавиту
    }
}

Практический пример: подсчёт слов

Давайте создадим программу, которая подсчитывает, сколько раз каждое слово встречается в тексте. Это классическая задача для HashMap.

import java.util.HashMap;

public class WordCounter {
    public static void main(String[] args) {
        String text = "яблоко банан яблоко вишня банан яблоко";

        String[] words = text.split(" ");

        HashMap<String, Integer> counter = new HashMap<>();

        for (String word : words) {
            if (counter.containsKey(word)) {
                int current = counter.get(word);
                counter.put(word, current + 1);
            } else {
                counter.put(word, 1);
            }
        }

        for (String word : counter.keySet()) {
            System.out.println(word + ": " + counter.get(word));
        }
    }
}

Результат: яблоко: 3, банан: 2, вишня: 1. Программа проходит по каждому слову и увеличивает счётчик для этого слова в HashMap.

Практический пример: телефонная книга

Ещё один полезный пример — простая телефонная книга, где ключ — имя, а значение — номер телефона:

import java.util.HashMap;

public class PhoneBook {
    public static void main(String[] args) {
        HashMap<String, String> phoneBook = new HashMap<>();

        phoneBook.put("Анна", "+7-999-111-22-33");
        phoneBook.put("Борис", "+7-999-444-55-66");
        phoneBook.put("Вика", "+7-999-777-88-99");

        String phone = phoneBook.get("Анна");
        System.out.println("Телефон Анны: " + phone);

        phoneBook.put("Анна", "+7-999-000-11-22");
        System.out.println("Новый телефон Анны: " + phoneBook.get("Анна"));

        System.out.println("Все записи:");
        for (String name : phoneBook.keySet()) {
            System.out.println("  " + name + ": " + phoneBook.get(name));
        }
    }
}

Когда какую коллекцию использовать

Давайте подведём итог и определим, какую коллекцию лучше использовать в каждой ситуации:

Полный пример: меню ресторана

Давайте создадим программу, которая использует разные коллекции вместе для решения реальной задачи — ведения меню ресторана:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class RestaurantMenu {
    public static void main(String[] args) {
        ArrayList<String> menuItems = new ArrayList<>();
        menuItems.add("Борщ");
        menuItems.add("Пельмени");
        menuItems.add("Оливье");
        menuItems.add("Компот");

        HashMap<String, Double> prices = new HashMap<>();
        prices.put("Борщ", 350.0);
        prices.put("Пельмени", 420.0);
        prices.put("Оливье", 280.0);
        prices.put("Компот", 120.0);

        HashSet<String> vegetarian = new HashSet<>();
        vegetarian.add("Оливье");
        vegetarian.add("Компот");

        System.out.println("Меню ресторана:");
        for (String item : menuItems) {
            double price = prices.get(item);
            String vegTag = vegetarian.contains(item) ? " [вегетарианское]" : "";
            System.out.println("  " + item + " — " + price + " руб." + vegTag);
        }
    }
}

Эта программа использует ArrayList для порядка блюд, HashMap для цен и HashSet для пометки вегетарианских блюд. Каждая коллекция решает свою задачу.

Итоги урока

• LinkedList — связный список, быстрый для вставок/удалений в начало и середину, медленный для доступа по индексу
• В 90% случаев лучше использовать ArrayList — он быстрее для случайного доступа
• HashSet хранит только уникальные элементы без сохранения порядка
• LinkedHashSet хранит уникальные элементы в порядке добавления
• TreeSet хранит уникальные элементы в отсортированном порядке
• HashMap хранит пары «ключ-значение» с быстрым поиском по ключу
• LinkedHashMap сохраняет порядок добавления ключей
• TreeMap хранит ключи в отсортированном порядке
• Для определения уникальности в HashSet/HashMap используются hashCode() и equals()
• Всегда переопределяйте оба метода, если используете собственный класс в HashSet/HashMap

Следующий урок: Iterable, Iterator и for-each →