Всегда ли доступ к элементам в HashMap в Java происходит за константное время O(1)?

Нет, не всегда. В идеальном случае (хорошая хеш-функция, отсутствие коллизий) доступ происходит за амортизированное время O(1). Однако есть ситуации, когда производительность деградирует:

1. Коллизии: При большом количестве коллизий элементы в одной корзине хранятся как связанный список (до Java 8) или дерево (Java 8+). В худшем случае поиск может занять O(n) или O(log n).
2. Неподходящая емкость (capacity): Если количество элементов сильно превышает текущую емкость, происходит рехеширование (rehashing) — создание нового массива корзин и перераспределение элементов, что является операцией O(n).

Пример деградации из-за коллизий (искусственный):

// Плохая хеш-функция, всегда возвращающая 1
class BadKey {
    @Override
    public int hashCode() { return 1; }
}

HashMap<BadKey, String> map = new HashMap<>();
for (int i = 0; i < 1000; i++) {
    map.put(new BadKey(), "value" + i); // Все элементы попадут в одну корзину
}
// Поиск по любому ключу будет перебирать список/дерево из 1000 элементов.

Best practice: Для ключей используйте неизменяемые объекты с эффективной и равномерно распределяющей значения хеш-функцией (например, стандартные классы вроде String, Integer).