ArrayList против LinkedList против HashMap в Java

1. Обзор

Коллекции в Java основаны на паре основных интерфейсов и более чем дюжине классов реализации. Широкий выбор различных реализаций иногда может привести к путанице.

Принятие решения о том, какой тип коллекции использовать для конкретного варианта использования, — нетривиальная задача. Это решение может сильно повлиять на читаемость и производительность нашего кода.

Вместо того, чтобы объяснять все типы коллекций в одной статье, мы расскажем о трех наиболее распространенных: ArrayList, LinkedList и HashMap. В этом руководстве мы рассмотрим, как они хранят данные, их производительность и порекомендуем, когда их использовать.

2. Коллекции

Коллекция — это просто объект Java, который объединяет другие объекты. Java Collections Framework содержит набор структур данных и алгоритмов для представления коллекций и управления ими . При правильном применении предоставленные структуры данных помогают сократить усилия по программированию и повысить производительность. ``

2.1. Интерфейсы

Java Collections Framework содержит четыре основных интерфейса: List , Set , Map и Queue . Прежде чем рассматривать классы реализации, важно понять предполагаемое использование этих интерфейсов.

Давайте кратко рассмотрим три из четырех основных интерфейсов, которые мы будем использовать в этой статье:

• Интерфейс списка предназначен для хранения упорядоченных коллекций объектов. Это позволяет нам позиционно получать доступ и вставлять новые элементы, а также сохранять повторяющиеся значения.
• Интерфейс Map поддерживает парное сопоставление данных ключ-значение. Чтобы получить доступ к определенному значению, нам нужно знать его уникальный ключ
• Интерфейс Queue позволяет хранить данные в порядке «первым поступил — первым обслужен». Похожа на реальную очередь

HashMap реализует интерфейс карты . Интерфейс List реализуется как ArrayList , так и LinkedList . LinkedList дополнительно реализует интерфейс Queue .

2.2. Список против карты

Распространенный антипаттерн, с которым мы иногда сталкиваемся, — это попытка поддерживать порядок с помощью карты. Таким образом, не используя другие типы коллекций, более подходящие для работы.

Тот факт, что мы можем решить множество проблем с помощью одного типа коллекции, не означает, что мы должны это делать.

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

Map<Integer, String> map = new HashMap<>();
map.put(1, "Daniel");
map.put(2, "Marko");
for (String name : map.values()) {
    assertThat(name).isIn(map.values());
}
assertThat(map.values()).containsExactlyInAnyOrder("Daniel", "Marko");

Когда мы перебираем значения карты, мы не гарантируем, что получим их в том же порядке, в котором мы их разместили. Это просто потому, что карта не предназначена для поддержания порядка элементов.

Мы можем переписать этот пример в гораздо более читабельном виде, используя список. Списки упорядочены по определению, поэтому мы можем перебирать элементы в том же порядке, в котором мы их вставляли:

List<String> list = new ArrayList<>();
list.add("Daniel");
list.add("Marko");
for (String name : list) {
    assertThat(name).isIn(list);
}
assertThat(list).containsExactly("Daniel", "Marko");

Карты предназначены для быстрого доступа и поиска по уникальным ключам. Когда мы хотим поддерживать порядок или работать с позиционными индексами, списки — естественный выбор.

3. Список массивов

ArrayList — это наиболее часто используемая реализация интерфейса List в Java. Он основан на встроенных массивах , но может динамически увеличиваться и уменьшаться при добавлении или удалении элементов.

Мы используем индексы, начинающиеся с нуля, для доступа к элементам списка. Мы можем вставить новый элемент либо в конец, либо в определенную позицию списка:

List<String> list = new ArrayList<>();
list.add("Daniel");
list.add(0, "Marko");
assertThat(list).hasSize(2);
assertThat(list.get(0)).isEqualTo("Marko");

Чтобы удалить элемент из списка, нам нужно указать ссылку на объект или его индекс:

List<String> list = new ArrayList<>(Arrays.asList("Daniel", "Marko"));
list.remove(1);
assertThat(list).hasSize(1);
assertThat(list).doesNotContain("Marko");

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

ArrayList предоставляет нам динамические массивы в Java. Хотя ArrayList медленнее, чем встроенные массивы, он помогает нам сократить усилия по программированию и улучшить читаемость кода.

Когда мы говорим о временной сложности , мы используем нотацию Big-O. Обозначение описывает, как время выполнения алгоритма увеличивается с размером входных данных.

ArrayList допускает произвольный доступ, поскольку массивы основаны на индексах. Это означает, что доступ к любому элементу всегда занимает постоянное время O(1) .

Добавление новых элементов также занимает время O(1) , за исключением случаев, когда добавление элемента в определенную позицию/индекс занимает O(n) . Проверка существования определенного элемента в заданном списке выполняется за линейное время O(n) .

То же самое верно и для удаления элементов. Нам нужно перебрать весь массив, чтобы найти элемент, выбранный для удаления.

3.2. Применение

Всякий раз, когда мы не уверены, какой тип коллекции использовать, вероятно, будет хорошей идеей начать с ArrayList. Имейте в виду, что доступ к элементам на основе индексов будет очень быстрым. Однако поиск элементов по их стоимости или добавление/удаление элементов в определенной позиции будет дорогостоящим.

Использование ArrayList имеет смысл, когда важно поддерживать один и тот же порядок элементов, а быстрое время доступа на основе позиции/индекса является важным критерием.

Избегайте использования ArrayList , когда порядок элементов не важен. Кроме того, старайтесь избегать этого, `когда элементы часто нужно добавлять в определенную позицию. Кроме того, имейте в виду, что ArrayList` может быть не лучшим вариантом, когда поиск определенных значений элемента является важным требованием, особенно если список большой.

4. Связанный список

LinkedList — это реализация двусвязного списка. Реализация интерфейсов List и Deque (расширение Queue) . В отличие от ArrayList , когда мы сохраняем данные в LinkedList , каждый элемент сохраняет ссылку на предыдущий.

Помимо стандартных методов вставки списка , LinkedList поддерживает дополнительные методы, которые могут добавлять элемент в начало или конец списка:

LinkedList<String> list = new LinkedList<>();
list.addLast("Daniel");
list.addFirst("Marko");
assertThat(list).hasSize(2);
assertThat(list.getLast()).isEqualTo("Daniel");

Эта реализация списка также предлагает методы для удаления элементов из начала или из конца списка:

LinkedList<String> list = new LinkedList<>(Arrays.asList("Daniel", "Marko", "David"));
list.removeFirst();
list.removeLast();
assertThat(list).hasSize(1);
assertThat(list).containsExactly("Marko");

Реализованный интерфейс Deque предоставляет методы, подобные очередям, для извлечения, добавления и удаления элементов:

LinkedList<String> list = new LinkedList<>();
list.push("Daniel");
list.push("Marko");
assertThat(list.poll()).isEqualTo("Marko");
assertThat(list).hasSize(1);

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

LinkedList потребляет немного больше памяти, чем ArrayList , поскольку каждый узел хранит две ссылки на предыдущий и следующий элемент.

Операции вставки, добавления и удаления в LinkedList выполняются быстрее, поскольку в фоновом режиме размер массива не изменяется. Когда новый элемент добавляется где-то в середине списка, необходимо изменить только ссылки в окружающих элементах.

LinkedList поддерживает вставку с постоянным временем O(1) в любой позиции в коллекции. Однако он менее эффективен при доступе к элементам в определенной позиции, занимая время O(n) .

Удаление элемента также занимает постоянное время O(1) , так как нам просто нужно изменить несколько указателей. Проверка наличия определенного элемента в заданном списке занимает линейное время O(n) , как и для ArrayList.

4.2. Применение

Большую часть времени мы можем использовать ArrayList как реализацию списка по умолчанию . Однако в некоторых случаях нам следует использовать LinkedList. К ним относятся случаи, когда мы предпочитаем постоянное время вставки и удаления, постоянное время доступа и эффективное использование памяти.

Использование LinkedList `` имеет смысл при сохранении того же порядка элементов, а быстрое время вставки (добавление и удаление элементов в любой позиции) является важным критерием.

Как и в случае с ArrayList , нам следует избегать использования LinkedList ` , когда порядок элементов не важен. LinkedList` — не лучший вариант, когда важным требованием является быстрое время доступа или поиск элементов.

5. Хэш-карта

В отличие от ArrayList и LinkedList , HashMap реализует интерфейс Map . Это означает, что каждому ключу соответствует ровно одно значение. Нам всегда нужно знать ключ для извлечения соответствующего значения из коллекции:

Map<String, String> map = new HashMap<>();
map.put("123456", "Daniel");
map.put("654321", "Marko");
assertThat(map.get("654321")).isEqualTo("Marko");

Точно так же мы можем удалить значение из коллекции только с помощью его ключа:

Map<String, String> map = new HashMap<>();
map.put("123456", "Daniel");
map.put("654321", "Marko");
map.remove("654321");
assertThat(map).hasSize(1);

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

Кто-то может спросить, а почему бы просто не использовать список и полностью избавиться от ключей? Тем более , что HashMap потребляет больше памяти для сохранения ключей и его записи не упорядочены. Ответ заключается в преимуществах производительности для элементов поиска.

HashMap очень эффективно проверяет наличие ключа или извлекает значение на основе ключа. Эти операции занимают в среднем O(1) .

Добавление и удаление элементов из HashMap на основе ключа занимает O(1) постоянное время. Проверка элемента без знания ключа занимает линейное время O(n), так как необходимо перебрать все элементы.

5.2. Применение

Наряду с ArrayList , HashMap является одной из наиболее часто используемых структур данных в Java. В отличие от других реализаций списков, HashMap использует индексирование для перехода к определенному значению, что делает время поиска постоянным даже для больших коллекций.

Использование HashMap имеет смысл только тогда, когда доступны уникальные ключи для данных, которые мы хотим сохранить. Мы должны использовать его при поиске элементов на основе ключа, и быстрое время доступа является важным требованием.

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

6. Заключение

В этой статье мы рассмотрели три распространенных типа коллекций в Java : ArrayList, LinkedList и HashMap . Мы рассмотрели их производительность при добавлении, удалении и поиске элементов. Исходя из этого, мы предоставили рекомендации о том, когда применять каждый из них в наших Java-приложениях.

В примерах мы рассмотрели только основные методы добавления и удаления элементов. Для более подробного ознакомления с каждой реализацией API посетите наши статьи, посвященные ArrayList, ArrayList и HashMap .

Как всегда, полный исходный код доступен на GitHub .