1. Введение
В этом кратком руководстве мы собираемся обсудить производительность метода 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 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 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 .