Коллекции trainee
Какая сложность операций в HashMap?
Ответ
Среднее: get / put / containsKey — O(1). Худший случай при плохих хэшах: O(log n) при treeified бакете, O(n) если treeify ещё не сработал.
Разбор: В среднем операции O(1) благодаря равномерному распределению по бакетам; при плохих хэшах бакет с >=8 элементами становится красно-чёрным деревом и даёт O(log n), а до treeify-порога — O(n). Поэтому неверно, что среднее O(log n), что худший всегда O(1), и что treeification не существует.
Хочешь так же по своей компании — с вопросами по грейдам и задачами? Закажи гайд или забери свежее в Telegram.