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