Какие структуры данных позволяют находить элемент не за линейное время

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

Знаете ли вы асимптотику основных структур и их реализации в JDK, а не только слово «хеш-таблица». Следом обычно спрашивают, от чего зависит O(1) у HashMap и когда TreeMap предпочтительнее.

Как отвечать

• хеш-таблица: HashMap и HashSet, O(1) в среднем. Всё держится на качестве hashCode. С Java 8 длинная корзина превращается в красно-чёрное дерево, и худший случай становится O(log n), если ключи реализуют Comparable;
• сбалансированное дерево поиска: TreeMap и TreeSet на красно-чёрном дереве, O(log n) гарантированно. Плюс порядок: диапазоны, floorKey, ceilingKey, первый и последний элемент. AVL-дерево сбалансировано строже, поиск чуть быстрее, вставка дороже;
• сортированный массив: Arrays.binarySearch и Collections.binarySearch, O(log n). Компактно и дружит с кэшем процессора, но вставка стоит O(n);
• список с пропусками: ConcurrentSkipListMap, O(log n) в среднем, потокобезопасная упорядоченная карта;
• B-дерево и B+дерево: широкие узлы под страницы диска, поэтому на них построены индексы баз данных;
• префиксное дерево (trie): поиск за O(L), где L длина ключа, удобно для автодополнения;
• фильтр Блума: отвечает «точно нет» или «возможно да», ложных отрицаний не бывает. Готовая реализация есть в Guava.

Подведите итог: нужен только поиск по ключу, берите хеш; нужен порядок или диапазоны, дерево; данные статичны, сортированный массив.

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

Называют кучу. PriorityQueue отдаёт минимум за O(1), но contains в ней линейный.

Говорят, что HashMap работает за O(1) всегда. При плохом hashCode, например константном, все ключи падают в одну корзину, а при нарушении контракта equals и hashCode элемент просто не находится.

Применяют бинарный поиск к несортированному массиву или забывают, что сортировка стоит O(n log n). Ради одного поиска выгоднее пройти массив линейно.