1. введение
В этом кратком руководстве мы обсудим производительность метода contains () , доступного в java.util. HashSet и java.util. ArrayList . Они оба являются коллекциями для хранения объектов и управления ими.
HashSet – это коллекция для хранения уникальных элементов. Чтобы узнать больше о HashSet, проверьте эту ссылку .
ArrayList является популярной реализацией java.util.Список интерфейс.
У нас есть расширенная статья о ArrayList , доступная здесь .
2. HashSet.содержит()
Внутренне реализация HashSet основана на экземпляре HashMap . Метод contains() вызывает HashMap.contains (объект) .
Здесь он проверяет, находится ли объект во внутренней карте или нет. Внутренняя карта хранит данные внутри узлов, известных как сегменты. Каждое ведро соответствует хэш-коду, сгенерированному с помощью метода hashCode () . Таким образом, содержит() на самом деле использует метод hashCode() для поиска местоположения |/объекта.
Теперь давайте определим сложность времени поиска. Прежде чем двигаться дальше, убедитесь, что вы знакомы с нотацией Big-O .
В среднем | содержит() из хэш-набора выполняется в O(1) время . Получение местоположения объекта ведра является постоянной операцией времени. Принимая во внимание возможные коллизии, время поиска может увеличиться до log(n) , поскольку внутренняя структура ведра представляет собой древовидную карту .
Это улучшение по сравнению с Java 7, которая использовала LinkedList для внутренней структуры корзины. Как правило, коллизии хэш-кода встречаются редко. Таким образом, мы можем рассматривать сложность поиска элементов как O(1) .
3. ArrayList.содержит()
Внутренне ArrayList использует метод indexOf(object) для проверки наличия объекта в списке . Метод indexOf(object) выполняет итерацию всего массива и сравнивает каждый элемент с методом equals(object) .
Возвращаясь к анализу сложности, ArrayList . содержит() метод требует O(n) времени. Таким образом, время, которое мы тратим на поиск конкретного объекта здесь, зависит от количества элементов, которые у нас есть в массиве.
4. Контрольное тестирование
Теперь давайте разогреем JVM с помощью теста производительности. Мы будем использовать продукт OpenJDK JMH (Java Microbenchmark Harness). Чтобы узнать больше о настройке и выполнении, ознакомьтесь с нашим полезным руководством .
Для начала давайте создадим простой Collections Benchmark класс:
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5)
public class CollectionsBenchmark {
@State(Scope.Thread)
public static class MyState {
private Set employeeSet = new HashSet<>();
private List 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 Employee(100L, “Гарри”) в качестве последних элементов в обе коллекции. Поэтому мы проверяем время поиска объекта employee на наихудший возможный случай.
@OutputTimeUnit(TimeUnit.NANOSECONDS) указывает, что мы хотим получить результаты в наносекундах. Количество итераций по умолчанию @Warmup в нашем случае равно 5. @BenchmarkMode установлен в режим .AverageTime , что означает, что мы заинтересованы в вычислении среднего времени выполнения. Для первого выполнения мы помещаем итерации элементы в наши коллекции.
После этого мы добавим наши методы бенчмарка в класс Collections Benchmark :
@Benchmark
public boolean testArrayList(MyState state) {
return state.employeeList.contains(state.employee);
}Здесь мы проверяем, содержит ли список сотрудников объект сотрудник|/.
Аналогично, у нас есть знакомый тест для сотрудников :
@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
Мы ясно видим, что тестАррайЛист метод имеет 4035.646 нс средний балл поиска, в то время как testHashSet работает быстрее с 9.456 нс в среднем.
Теперь давайте увеличим количество элементов в нашем тесте и запустим его для 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() in HashSet имеет огромное преимущество в производительности по сравнению с ArrayList .
5. Заключение
Эта быстрая запись объясняет производительность метода contains() коллекций HashSet и ArrayList . С помощью бенчмаркинга JMH мы представили производительность contains() для каждого типа коллекции.
В качестве вывода мы можем узнать, что метод |/contains() работает быстрее в HashSet по сравнению с ArrayList .
Как обычно, полный код для этой статьи находится над проектом GitHub .