Средняя сложность — O(1), в худшем случае — O(n).
- Средний случай (O(1)): При хорошей хэш-функции и равномерном распределении элементов по корзинам (buckets) поиск сводится к вычислению хэша ключа и прямому доступу к соответствующей корзине массива. Внутри корзины, если нет коллизий, элемент находится за константное время.
- Худший случай (O(n)): Возникает, когда все элементы хэшируются в одну и ту же корзину. В таком случае поиск превращается в линейный перебор элементов в связанном списке (или сбалансированном дереве в Java 8+ для корзин с большим количеством элементов, но даже обход дерева может занимать O(log n), что при очень большом количестве коллизий в одной корзине всё равно приближается к O(n) относительно общего числа элементов, если все они попали в одну корзину).
Начиная с Java 8, для корзин, содержащих более определенного порога (TREEIFY_THRESHOLD, по умолчанию 8) элементов, связанный список преобразуется в сбалансированное дерево (Red-Black Tree). Это улучшает худший случай поиска в пределах одной корзины до O(log n), но если все ключи имеют одинаковый хэш, общий поиск по-прежнему может быть близок к O(n).