Как работает метод contains в arraylist и linkedlist
Перейти к содержимому

Как работает метод contains в arraylist и linkedlist

  • автор:

Производительность contains() в HashSet и ArrayList

В этом кратком руководстве мы собираемся обсудить производительность метода contains() , доступного в java.util. HashSet и java.util. список массивов . Обе они являются коллекциями для хранения объектов и управления ими.

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

ArrayList — популярная реализация интерфейса java.util.List .

У нас есть расширенная статья об ArrayList , доступная здесь .

2. Набор хешей.содержит()

Внутри реализация HashSet основана на экземпляре HashMap . Метод contains() вызывает HashMap.containsKey(object) .

Здесь проверяется, есть объект на внутренней карте или нет. Внутренняя карта хранит данные внутри узлов, известных как сегменты. Каждое ведро соответствует хеш-коду, сгенерированному методом hashCode() . Таким образом , contains() на самом деле использует метод hashCode() для определения местоположения объекта .

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

В среднем, contains () для HashSet выполняется за время O(1) . Получение местоположения корзины объекта — это операция с постоянным временем. Принимая во внимание возможные коллизии, время поиска может увеличиться до log(n) , поскольку внутренняя структура сегмента представляет собой TreeMap .

Это улучшение по сравнению с Java 7, в котором для внутренней структуры корзины использовался LinkedList . Как правило, коллизии хеш-кодов случаются редко. Таким образом, мы можем рассматривать сложность поиска элементов как O(1) .

3. ArrayList.c содержит() ​

Внутри ArrayList использует метод indexOf(object) для проверки наличия объекта в списке . Метод indexOf(object) перебирает весь массив и сравнивает каждый элемент с методом equals(object) .

Возвращаясь к анализу сложности, ArrayList . Метод contains() требует O(n) времени. Таким образом, время, которое мы тратим на поиск конкретного объекта здесь, зависит от количества элементов, которые у нас есть в массиве.

4. Сравнительное тестирование

Теперь давайте разогреем JVM с помощью теста производительности. Мы будем использовать продукт OpenJDK JMH (Java Microbenchmark Harness). Чтобы узнать больше о настройке и выполнении, ознакомьтесь с нашим полезным руководством .

Для начала создадим простой класс CollectionsBenchmark :

 @BenchmarkMode(Mode.AverageTime)   @OutputTimeUnit(TimeUnit.NANOSECONDS)   @Warmup(iterations = 5)   public class CollectionsBenchmark     @State(Scope.Thread)   public static class MyState    private SetEmployee> employeeSet = new HashSet>();   private ListEmployee> employeeList = new ArrayList>();    private long iterations = 1000;    private Employee employee = new Employee(100L, "Harry");    @Setup(Level.Trial)   public void setUp()     for (long i = 0; i  iterations; i++)    employeeSet.add(new Employee(i, "John"));   employeeList.add(new Employee(i, "John"));   >    employeeList.add(employee);   employeeSet.add(employee);   >   >   > 

Здесь мы создаем и инициализируем объекты HashSet и ArrayList of Employee :

 public class Employee     private Long id;   private String name;    // constructor and getter setters go here   > 

Мы добавляем экземпляр employee = new Employee(100L, «Harry») в качестве последних элементов в обе коллекции. Итак, мы проверяем время поиска объекта сотрудника для наихудшего возможного случая.

@OutputTimeUnit(TimeUnit.NANOSECONDS) указывает, что нам нужны результаты в наносекундах. В нашем случае количество итераций @Warmup по умолчанию равно 5. @BenchmarkMode имеет значение Mode.AverageTime , что означает, что нас интересует вычисление среднего времени выполнения. Для первого выполнения мы поместили в наши коллекции итерации = 1000 элементов.

После этого мы добавляем наши тестовые методы в класс CollectionsBenchmark :

 @Benchmark   public boolean testArrayList(MyState state)    return state.employeeList.contains(state.employee);   > 

Здесь мы проверяем, содержит ли список сотрудников объект сотрудника .

Точно так же у нас есть знакомый тест для employeeSet :

 @Benchmark   public boolean testHashSet(MyState state)    return state.employeeSet.contains(state.employee);   > 

Наконец, мы можем запустить тест:

 public static void main(String[] args) throws Exception    Options options = new OptionsBuilder()   .include(CollectionsBenchmark.class.getSimpleName())   .forks(1).build();   new Runner(options).run();   > 
Benchmark Mode Cnt Score Error Units CollectionsBenchmark.testArrayList avgt 20 4035.646 ± 598.541 ns/op CollectionsBenchmark.testHashSet avgt 20 9.456 ± 0.729 ns/op 

Мы ясно видим, что метод testArrayList имеет средний показатель поиска 4035,646 нс , в то время как testHashSet работает быстрее со средним значением 9,456 нс .

Теперь давайте увеличим количество элементов в нашем тесте и запустим его для итераций = 10 000 элементов:

Benchmark Mode Cnt Score Error Units CollectionsBenchmark.testArrayList avgt 20 57499.620 ± 11388.645 ns/op CollectionsBenchmark.testHashSet avgt 20 11.802 ± 1.164 ns/op 

Здесь также метод contains() в HashSet имеет огромное преимущество в производительности по сравнению с ArrayList .

5. Вывод

Этот краткий обзор объясняет производительность метода contains () коллекций HashSet и ArrayList . С помощью бенчмаркинга JMH мы представили производительность contains() для каждого типа коллекции.

В заключение мы можем узнать, что метод contains() работает быстрее в HashSet по сравнению с ArrayList .

Как обычно, полный код для этой статьи закончился на GitHub project .

Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 10

Java-университет

Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 10 - 1

Привет! Как много часов нужно потратить, чтобы стать в чём-то мастером? Часто слышал что-то вроде: “Чтобы стать мастером в любом деле, нужно потратить 10000 часов”. Пугающая цифра, не так ли? Тем не менее, мне интересно, а правда ли это? И я постоянно пытаюсь прикидывать, сколько часов я уже вложил в овладение программистским искусством. И когда я перешагну те заветные 10000 часов и стану мастером, почувствую ли я эту разницу? Или я уже их давно перешагнул, не осознав этого? Так или иначе, чтобы стать программистом, не нужно вкладывать такое огромное количество времени. Главное — использовать его с умом. Ваша первостепенная цель — пройти собеседование. А на собеседованиях новичков в первую очередь как раз спрашивают теорию, поэтому вы должны быть в ней сильны. Собственно, при самой подготовке к собеседованию ваша задача — обнаружить все ваши пробелы в базовой теории Java-разработчика и покрыть их знаниями. И сегодня я вам помогу в этом деле, ведь я тут, чтобы продолжить разбор самых популярных вопросов. Итак, продолжим!

89. Чем отличается ArrayList от LinkedList?

Это один из самых популярных вопросов наравне с вопросом о внутреннем устройстве HashMap . Ни одно собеседование не обходится без него, и поэтому ответ на него у вас должен “отскакивать от зубов”. Помимо очевидного — разного названия — они отличаются внутренним устройством. Ранее мы разбирали внутренние устройство и ArrayList -а и LinkedList -а, поэтому вдаваться в детали их реализации я не буду. Лишь напомню, что ArrayList реализован на основе внутреннего массива, который по надобности увеличивается по формуле:

  * 3 / 2 + 1 

Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 10 - 2

В то же время LinkedList реализован на основе внутреннего двухсвязного списка, то есть, каждый элемент имеет ссылку на предыдущий и следующий, исключая значения, которые являются началом/концом списка. Этот вопрос любят задавать в формате: “Что лучше — ArrayList или LinkedList ?”, надеясь вас подловить. Ведь если вы в качестве ответа укажете на один из них, это будет неправильный ответ. Вместо этого вам стоит уточнить, о какой конкретной ситуации идет речь — доступ по индексу или вставка в середину списка. В зависимости от ответа вы сможете объяснить свой выбор. Ранее я уже описывал, как работает ArrayList и LinkedList в той или иной ситуации. Давайте подытожим это, поставив их в один ряд для сравнения: Добавление элемента (add)

  1. Добавление нового элемента без указания индекса как местоположения будет происходить автоматически в конец обоих списков. В LinkedList новый элемент станет новым хвостом (происходит только перезаписывание пары ссылок — алгоритмическая сложность O(1) ). В ArrayList будет добавлен новый элемент в последнюю пустую ячейку массива — O(1) .
  2. Добавление элемента по индексу как правило подразумевает вставку примерно в середину списка. В LinkedList сперва будет вестись поиск нужного места с помощью перебора элементов с “хвоста” и “головы” — O(n/2) , а после — вставка значения путем переопределения ссылок элементов, между которыми вставляется новый — O(1) . Суммарная алгоритмическая сложность данного действия будет O(n/2) . ArrayList в данной ситуации по индексу находит элемент — O(1) , и все элементы справа (включая элемент, который уже хранится по данному индексу) двигаются на одну единицу вправо (при этом возможно понадобится создание нового списка и копирование элементов в него) — O(n/2) . Суммарная сложность — O(n/2) .
  3. Добавление элемента в начало списка в LinkedList будет ситуация схожая с добавлением в конец: новый элемент станет новой “головой” — O(1) , в то же время когда ArrayList -у нужно будет двигать все элементы вправо — O(n) .

Итог: в LinkedList алгоритмическая сложность будет колебаться от O(1) до O(n/2) . То есть, чем ближе вставка к концу или началу списка, тем она быстрее. В то же время у ArrayList она колеблется от O(1) до O(n) : чем вставка ближе к концу списка, тем она быстрее. Задание элемента (set) Данная операция записывает элемент в указанную позицию в списке, перезаписывая предыдущий, если он есть. В LinkedList эта операция будет схожа с добавлением, т.к. самая большая сложность тут — поиск элемента. Перезапись элемента будет проходить путем перезаписывания пары ссылок, поэтому тут также алгоритмическая сложность будет колебаться от O(1) до O(n/2) в зависимости от удаленности позиции от конца или начала списка. В то время в ArrayList для этой операции по индексу будет найдена нужная ячейка, а в нее записан новый элемент. Поиск по индексу, как и данная операция, имеет алгоритмическую сложность O(1) . Взять элемент по индексу (get) В LinkedList взятие элемента будет происходить по тому же принципу, что и поиск для других операций — в зависимости от удаленности от конца или начала, т.е. от O(1) до O(n/2) . В ArrayList , как я и сказал ранее, поиск элемента в массиве по индексу имеет сложность O(1) . Удалить элемент по индексу (remove) Для LinkedList тут тоже срабатывает его принцип действия: сперва находится элемент, а потом происходит перезаписывание ссылок — соседи элемента начинают ссылаться друг на друга, теряя ссылки на данный элемент, который впоследствии будет удален сборщиком мусора. То есть, алгоритмическая сложность всё такая же — от O(1) до O(n/2) . Для ArrayList данная операция больше схожа с операцией добавления нового элемента (add). Сперва находится искомый элемент — O(1) , потом он удаляется, и все элементы, которые были справа от него перемещаются на одну единицу влево, чтобы закрыть образовавшуюся брешь. Операция удаления будет иметь ту же алгоритмическую сложность, что и операция добавления — от O(1) до O(n) . Чем удаление ближе к концу списка, тем меньшая у него алгоритмическая сложность. Собственно, это были все основные операции. Напоминаю: при сравнении этих двух списков вам нужно уточнить, о какой конкретной ситуации идёт речь, и тогда уже и можно однозначно ответить на поставленный вопрос.

90. Чем отличается ArrayList от HashSet?
  • ArrayList реализует интерфейс List , в то время как HashSet реализует интерфейс Set ;
  • В ArrayList возможен доступ по индексу элемента: операция get имеет алгоритмическую сложность O(1) , а в HashSet необходимый элемент можно получить лишь путём перебора, а это у нас от O(1) до O(n) ;
  • ArrayList допускает присутствие дубликатов элементов. В HashSet все элементы уникальны: добавить в HashSet элемент, аналог которого уже присутствует в коллекции, не получится (проверка дубликатов ведется по hashcode, отсюда и название этой коллекции);
  • ArrayList реализован с помощью внутреннего массива, а HashSet реализован с помощью внутренней HashMap ;
  • ArrayList поддерживает порядок вставки элементов, в то время как HashSet — это неупорядоченное множество и не поддерживает порядок элементов;
  • ArrayList допускает любое количество пустых значений (null), в HashSet можно вставить лишь одно значение null (как-никак, уникальность элементов).
91. Зачем в Java такое разнообразие имплементации динамического массива?

Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 10 - 3

Ну, это скорее философский вопрос. Ну а зачем придумывают такое количество новых разнообразных технологий? Для удобства. Собственно, так же и с большим количеством имплементаций динамического массива. Ни одну из них нельзя назвать лучшей или идеальной. У каждой есть преимущество в какой-то конкретной ситуации. И наша задача — знать их различия, их сильные/слабые стороны: чтобы суметь в нужной ситуации использовать самую подходящую из них.

92. Зачем в Java такое разнообразие имплементаций key-value storage?

Здесь ситуация такая же, как и с имплементациями динамического массива. Однозначно лучших нет: у каждой есть сильные и слабые стороны. И мы, конечно, должны по максимуму использовать сильные стороны. Пример: в пакете concurrent, в котором есть множество многопоточных технологий, имеются свои Concurrent коллекции. У той же ConcurrentHashMap есть преимущество в безопасности многопоточной работы с данными в сравнении с обычной HashMap , но не в многопоточной среде она проигрывает в скорости работы. Ну а имплементации, которые ни в одной из ситуаций не бывают сильнейшими, постепенно перестают использовать. Пример: Hashtable , которая изначально задумывалась как потокобезопасная HashMap , но ConcurrentHashMap превзошла ее при работе в многопоточной среде, и в итоге о Hashtable позабыли и перестали использовать.

93. Как отсортировать коллекцию элементов?

Первое, что нужно сказать, — класс элемента коллекции должен имплементировать интерфейс Comparable и его метод compareTo . Или же нужен класс, который имплементирует Comaprator с его методом comparator . Подробнее о них можно почитать в этом посте. Оба способа указывают, каким образом нужно сравнивать объекты данного типа. При сортировке это критически важно, ведь нужно понимать принцип, по которому элементы можно сравнить. В основном используется способ через имплементацию Comparable , реализуемый непосредственно в классе, который вы хотите сортировать. В то же время применение Comparator -а более редко. Скажем, вы используете класс с какой-то библиотеки, у которого нет реализации Comparable , но вам как-то нужно будет его сортировать. Не имея возможности изменить код данного класса (кроме как расширить его), вы можете написать реализацию Comparator -а, в котором укажете, по какому принципу нужно сравнивать объекты данного класса. И еще один пример. Допустим, вам нужны разные принципы сортировки объектов одного и того же типа, поэтому вы пишете несколько Comparator -ов которые используете в разных ситуациях. Как правило, многие классы из коробки уже реализуют интерфейс Comparable — тот же String . Собственно, при их использовании вам не нужно париться, как их сравнить. Вы просто берете и используете их. Первый и самый очевидный способ — использовать коллекцию типа TreeSet или TreeMap , которые хранят элементы в ужеотсортированном порядке, согласно компаратору класса элементов. Не забывайте, что TreeMap сортирует ключи, но не значения. Если вы используете имплементацию Comparator вместо Comparable , вам нужно будет передать его объект в конструктор коллекции при создании:

 TreeSet treeSet = new TreeSet(customComparator); 

А что если у вас коллекция другого типа? Как её отсортировать? В этом случае подходит второй способ утилитного класса Collections — метод sort() . Он статический, поэтому всё, что вам нужно — имя класса и метод, в который передается необходимый список. Например:

 Collections.sort(someList); 

Если вы используете не Comparable , а реализацию Comparator , его нужно передать вторым параметром:

 Collections.sort(someList, customComparator); 

В итоге внутренний порядок элементов переданного списка изменится: он будет отсортирован согласно компаратору элементов. Отмечу, что передаваемый список элементов должен быть мутабельным, т.е. изменяемым, иначе метод не сработает и будет выброшено UnsupportedOperationException . В качестве третьего способа можно использовать Stream операцию sort , которая сортирует элементы коллекции, если используется имплементация Comparable :

 someList = someList.stream().sorted().collect(Collectors.toList()); 

если Comparator :

 someList = someList.stream().sorted(customComparator).collect(Collectors.toList()); 

Подробнее о Stream можно почитать в этой статье. Четвертый способ — ручная реализация сортировки, например, сортировки пузырьком или сортировки слиянием.

Class Object. Equals and HashCode

94. Дайте краткую характеристику class object в Java

Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 10 - 4

Во второй части разбора мы уже говорили о методах класса Object , и я напомню, что класс Object — прародитель всех классов в Java. У него есть 11 методов, которые, соответственно, наследуются всеми классами. Информацию обо всех 11 методах можно найти во второй части разбора вопросов.

95. Для чего используют Equals и HashCode в Java?

Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 10 - 5

hashCode() — это метод класса Object , который наследуется всеми классами. Его задача — генерирование некоторого числа, которое представляет конкретный объект. Примером использования данного метода может служить его применение в HashMap на объекте ключа для дальнейшего определения локального хешкода, по которому определится ячейка внутреннего массива (бакета), в которой будет сохранена пара. Подробно о работе HashMap мы говорили в 9 части разбора, поэтому особо останавливаться на этом не будем. Также как правило данный метод используется в методе equals() как один из его основных инструментов определения идентичности объектов. equals() — метод класса Object , задача которого — сравнивать объекты и определять, равны они или нет. Данный метод используется повсеместно там, где нам необходимо сравнить объекты, ведь обычное сравнение через == не подходит для объектов, т.к. сравнивает только ссылки на них.

96. Расскажите про контракт между Equals и HashCode в Java?

Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 10 - 6

Первое, что скажу — для корректной работы методов equals() и hashCode() их нужно правильно переопределить. После этого они должны соблюдать правила:

  • одинаковые объекты, для которых сравнение через equals возвращает true, обязательно имеют одинаковые хеш-коды;
  • объекты с одинаковыми хеш-кодами не всегда могут быть равны.

На этом мы и сделаем паузу до следующей части разбора!

  • Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 1
  • Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 2
  • Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 3
  • Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 4
  • Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 5
  • Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 6
  • Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 7
  • Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 8
  • Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 9
  • Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 11
  • Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 12
  • Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 13
  • Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 14
  • Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 15
  • Разбор вопросов и ответов с собеседований на Java-разработчика. Часть 16

Метод contains ArrayList

В меня такие задачи.
В двух ArrayLists, каждый из которых содержит по 3 объекты класса Car, в свою очередь, содержит поля String model, String owner, int price, int produceYear, определить факт наличия в коллекциях автомобилей владельца «Serg». Задача определить двумя способами — с помощью метода contains класса ArrayList и с помощью других произвольных методов. Почему везде выдает true?

 Car car1 = new Car("BMW X5","Oleg",9999,2018); Car car2 = new Car("BMW X4","Serg",12313,2017); Car car3 = new Car("BMW X3","Arsen",31231,2015); Car car4 = new Car("VOLGA ","Petro",3123132,2009); Car car5 = new Car("Mercedes-Benz","Serg",999999,2014); Car car6 = new Car("BMW X3","Vitalii",123131,2015); List cars1 = new ArrayList<>(); cars1.add(car1); cars1.add(car2); cars1.add(car3); List cars2 = new ArrayList<>(); cars2.add(car4); cars2.add(car5); cars2.add(car6); for (Car car : cars2) < System.out.println(cars2.contains(car)); >> class Car < @Override public boolean equals(Object o) < if (this == o) return true; if (!(o instanceof Car)) return false; Car car = (Car) o; return owner.equals(car.owner); >> 

Отслеживать
user176262
задан 4 окт 2021 в 15:30
vasilpetrovich vasilpetrovich
37 8 8 бронзовых знаков

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Вы перебираете элементы списка cars2 и проверяете, содержится ли каждый из них в списке cars2 . Ответ, наверное, будет «да» для каждого элемента списка.

 for (Car car : cars2) < if ("Serg".equals(car.owner)) < System.out.println("cars2 contains a car owned by Serg"); break; >> 

Отслеживать
ответ дан 4 окт 2021 в 15:36
user176262 user176262
какие можете порекомендовать другие методы чтобы проверить?
4 окт 2021 в 15:39
@vasilpetrovich Какие «другие»? Проверить что?
– user176262
4 окт 2021 в 15:41

Определить факт наличия в коллекциях автомобилей владельца «Serg».Задача определить двумя способами — с помощью метода contains класса ArrayList и с помощью других произвольных методов.

Как работает метод contains в hashset java

Конструкция contains в HashSet используется для проверки наличия элемента в данном наборе.

Вот пример использования метода contains :

HashSetString> elements = new HashSet<>(); elements.add("foo"); elements.add("bar"); elements.add("baz"); if (elements.contains("foo"))  System.out.println("hashSet contains foo"); > 

Здесь мы создаем новый объект HashSet и добавляем в него несколько строковых элементов. Затем мы проверяем, содержит ли набор строку «foo» с помощью метода contains . Если элемент присутствует, выводится сообщение «hashSet contains foo». Если элемент отсутствует, ничего не происходит.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *