«1. Введение

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

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

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

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

2. HashSet.contains()

Внутренне реализация 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.contains()

Внутри 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 Set<Employee> employeeSet = new HashSet<>();
        private List<Employee> 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 объектов 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.

«