Какое время поиск элемента в ArrayList, HashSet?

Короткий ответ

Ответ зависит от того, что понимается под «поиском». В ArrayList доступ по индексу get(i) занимает O(1): массив хранится непрерывно. Поиск по значению — contains(element) — требует линейного прохода с проверкой через equals, поэтому в худшем случае это O(n). В HashSet contains вычисляет хэш-код, находит корзину и сравнивает элементы внутри неё — в среднем O(1) независимо от размера множества.

Как это работает подробнее

Худший случай HashSet — когда из-за плохих хэш-кодов все элементы «свалились» в одну корзину: поиск деградирует до O(n). В Java 8+ длинные цепочки превращаются в сбалансированное дерево, и тогда худший случай ограничен O(log n). Для корректной работы HashSet элементы должны правильно переопределять equals и hashCode.

• Практический вывод: частые проверки «содержится ли элемент» быстрее делать через HashSet, чем через список.

Пример кода

ContainsDemo.javaКопировать

List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));
String s = list.get(1);              // O(1): доступ по индексу
boolean inList = list.contains("c"); // O(n): линейный перебор
Set<String> set = new HashSet<>(list);
boolean inSet = set.contains("c");    // в среднем O(1)

Что использовать на практике

• Для частых проверок «содержится ли элемент» используйте HashSet — в среднем O(1) против O(n) у списка.
• ArrayList берите там, где нужен доступ по индексу и порядок элементов.
• Следите за корректными equals и hashCode у элементов, помещаемых в HashSet.

Подводные камни

• contains у ArrayList всегда O(n) — индекс здесь не помогает.
• Плохие хэши (например, константа hashCode) ломают O(1) у HashSet — все узлы падают в одну корзину.
• Вопрос про «поиск в ArrayList» проверяет, различаете ли вы доступ по индексу и поиск по значению.

Как отвечать на собеседовании

• Разделите «поиск» на два случая: в ArrayList get(i) за O(1), а contains — линейный перебор по equals за O(n) → для HashSet: contains по hashCode сразу находит корзину — в среднем O(1) → упомяните худший случай O(n) при плохих хэшах и дерево Java 8+, дающее O(log n) → завершите правилом выбора по частоте проверок.