Какая алгоритмическая сложность метода contains в HashSet в Java

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

Знаете ли вы, что за contains стоит HashMap, и понимаете ли, откуда берётся O(1) и когда она перестаёт работать. Вопрос короткий, но это вход в разговор про хеш-таблицы. Следом спрашивают про худший случай, про контракт equals и hashCode и про то, что будет, если поменять объект, уже лежащий в множестве.

Как отвечать

Дайте цифры сразу, потом механику:

• средний случай: O(1). HashSet внутри это HashMap, где ваш элемент лежит ключом, а значением служит один общий объект-заглушка;
• худший случай: O(log n) начиная с Java 8. До неё было O(n): корзина была связным списком, и при массовых коллизиях поиск вырождался в полный перебор.

Дальше по шагам: считается hashCode(), к нему применяется перемешивание h ^ (h >>> 16), индекс корзины берётся как (n - 1) & hash. Внутри корзины сравнение идёт сначала по хешу и ==, затем по equals(). Корзина превращается в красно-чёрное дерево, когда в ней набирается 8 элементов и массив уже не меньше 64 ячеек, иначе таблица просто расширяется вдвое. При падении до 6 элементов дерево разворачивается обратно в список.

Упомяните нагрузочный фактор 0.75 и начальную ёмкость 16: расширение переносит все элементы, поэтому O(1) здесь амортизированная. И оговорку, которую любят слышать: константа считается по числу элементов, а сам hashCode() строки линеен по её длине, просто String кэширует посчитанное значение.

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

Отвечают «в худшем случае O(n)» и не знают про деревья в корзинах. Формально это верно только для Java 7 и для ключей, которые не удаётся упорядочить даже запасным сравнением по имени класса.

Путают контракт: равные объекты обязаны давать равный hashCode, обратное неверно. Свой equals без hashCode превращает множество в набор дубликатов, а поиск в стабильный промах.

Кладут изменяемый объект и правят поле, участвующее в хеше. Элемент остаётся в старой корзине, contains идёт искать в другую и возвращает false, хотя объект физически лежит в множестве.