Автор оригинала: baeldung.

ArrayList vs. LinkedList vs. HashMap на Java

1. Обзор

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

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

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

2. Коллекции

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

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

Java Collections Framework содержит четыре основных интерфейса: Список , Установить , Карта и Очередь . Важно понимать предполагаемое использование этих интерфейсов, прежде чем смотреть на классы реализации.

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

• Список интерфейс предназначен для хранения заказанных коллекций объектов. Это позволяет нам позиционировать доступ и вставки новых элементов, а также сохранить дубликаты значений
• Карта интерфейс поддерживает отображение данных парой ключевых значений. Чтобы получить доступ к определенному значению, мы должны знать его уникальный ключ
• Очередь интерфейс позволяет хранить данные на основе первого в первом порядке. Похож на реальную линию очереди

HashMap реализует Карта интерфейс. Список интерфейс реализуется обеими ArrayList и LinkedList . LinkedList дополнительно реализует Очередь интерфейс.

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

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

Просто потому, что мы можем решить многие проблемы с одним типом коллекции не означает, что мы должны.

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

Map 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 list = new ArrayList<>();
list.add("Daniel");
list.add("Marko");
for (String name : list) {
    assertThat(name).isIn(list);
}
assertThat(list).containsExactly("Daniel", "Marko");

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

3. ArrayList

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

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

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

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

List 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) время, за исключением добавления элемента на определенную позицию/индекс, затем О(н) . Проверка того, существует ли определенный элемент в данном списке, выполняется в линейных О(н) Время.

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

3.2. Использование

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2. Использование

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

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

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

5. ХэшМэп

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

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

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

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

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

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

ХэшМэп очень эффективен при проверке, существует ли ключ, или при извлечении значения, основанного на ключе. Эти операции принимают O(1) в среднем.

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

5.2. Использование

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

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

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

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

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

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

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