Какая скорость поиска в ArrayList в Java

Что проверяют

Различаете ли вы доступ по индексу и поиск по значению: у ArrayList это операции разной сложности. Следом спрашивают, как ускорить поиск и что для этого должно быть в классе элемента.

Как отвечать

ArrayList хранит ссылки в массиве Object[] elementData, отсюда вся арифметика:

• get(index): O(1), это обращение по смещению в массиве плюс проверка границ;
• indexOf, contains, lastIndexOf: O(n), линейный проход со сравнением через equals(). contains просто вызывает indexOf(o) >= 0, а null ищется отдельной веткой через ==;
• add(e) в конец: амортизированное O(1). При заполнении массив растёт примерно в полтора раза (oldCapacity + (oldCapacity >> 1)) с копированием через Arrays.copyOf;
• add(index, e) и remove(index): O(n) из-за сдвига хвоста через System.arraycopy;
• Collections.binarySearch: O(log n), но только на списке, отсортированном тем же порядком. На несортированном результат не определён.

Если поиск по значению частый, меняют структуру: HashSet или HashMap дают O(1) в среднем. При множестве коллизий переполненный бакет начиная с Java 8 превращается в красно-чёрное дерево, и для Comparable ключей поиск в нём деградирует до O(log n), а не до O(n). Для хэш-коллекций у элемента должны быть согласованно переопределены equals() и hashCode(). Нужен порядок и поиск по диапазону, берут TreeSet или TreeMap с O(log n).

Где спотыкаются

Отвечают «O(1)», путая get с поиском. Интервьюер сразу уточнит про contains, и ответ разваливается.

Вызывают contains у списка внутри цикла по другому списку. Получается O(n × m), на двух списках по сто тысяч элементов это десять миллиардов сравнений; перенос одного списка в HashSet сводит задачу к линейному времени.

Ищут объект своего класса без переопределённого equals(). Тогда сравнение идёт по ссылке, и indexOf(new User(42)) возвращает -1, хотя пользователь с таким id в списке есть.