Доступ к элементам в HashMap при выполнении базовых операций (get, put, remove) в лучшем случае (при равномерном распределении хеш-кодов и отсутствии коллизий) составляет O(1).
При наличии коллизий и их разрешении методом цепочек (linked lists) в худшем случае скорость доступа может достигать O(n), где n — количество элементов в "корзине" (bucket), так как приходится последовательно обходить элементы связанного списка для поиска или вставки.
Начиная с Java 8, для улучшения производительности при большом количестве коллизий в одной "корзине" связанный список преобразуется в сбалансированное дерево (например, красно-черное дерево). В этом случае скорость доступа при наличии коллизий в худшем случае уменьшается до O(log n). На практике это существенно улучшает производительность при наличии большого количества коллизий.
Фактическая скорость зависит от:
load factor увеличивает вероятность коллизий. При превышении порога HashMap перестраивается (rehash), что может быть дорогостоящей операцией O(n).hashCode() и equals(), обеспечивают лучшую производительность.