Насколько тяжелая операция remove в HashSet и как она реализована под капотом

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

Понимаете ли вы, что стоит за оценкой O(1). Ответ «константа» без объяснения, из чего эта константа складывается, не отличает вас от того, кто вчера прочитал шпаргалку. От кандидата на Android дополнительно ждут понимания цены коллекций на телефоне, где важны и память, и лишние объекты.

Как отвечать

HashSet это обёртка над HashMap: элементы лежат ключами, а значением подставляется один общий объект-заглушка. Удаление делегируется в карту и идёт так:

• считается hashCode объекта, результат домешивается сдвигом, чтобы на индекс влияли и старшие биты;
• по индексу берётся корзина;
• внутри корзины идёт перебор со сравнением через equals, а если корзина успела превратиться в дерево, поиск идёт по дереву.

Средняя сложность O(1), худшая O(n) для списка и O(log n) для дерева. Но реальная цена почти всегда не в поиске корзины, а в ваших hashCode и equals: у строки хеш посчитан однажды и закеширован, у класса данных с вложенными списками он обходит все поля при каждом вызове.

Важное свойство: удаление не сжимает таблицу. Массив корзин остаётся прежнего размера, память не возвращается, и обход набора, из которого удалили почти всё, стоит столько же, сколько обход полного.

На Android к этому добавляется выбор структуры: для небольших наборов ArraySet и ArrayMap из androidx экономят память, платя за это двоичным поиском по отсортированному массиву хешей вместо прямого доступа, а SparseArray для целочисленных ключей убирает упаковку в объекты.

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

Отвечают «O(1)» и замолкают. Следующий вопрос всегда про худший случай, и там выясняется, что про превращение корзины в дерево кандидат не слышал.

Второе: не связывают удаление с контрактом equals и hashCode. Измените после вставки поле, участвующее в хеше, и объект окажется не в той корзине: remove вернёт false, contains тоже, а элемент останется в наборе навсегда.

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