Какая сложность доступа к элементу по ключу HashMap в худшем случае

В идеальном случае (хорошо распределенные хэши) - O(1). В худшем случае (все ключи попали в одну корзину из-за коллизий) - O(n), так как превращается в поиск по связанному списку или дереву (в Java 8+ при большом количестве коллизий корзина становится деревом).

Пример:

Map<String, Integer> map = new HashMap<>();
// Все ключи имеют одинаковый хэш
map.put("a", 1);  // O(1)
map.put("b", 2);  // O(1) 
map.put("c", 3);  // O(n) - если все в одной корзине