Какая скорость доступа к элементу в HashMap

В среднем O(1) для get() и put() операций при хорошей хеш-функции и равномерном распределении элементов. В худшем случае (коллизии) может деградировать до O(n), когда все элементы попадают в одну корзину.

Пример:

Map<String, Integer> map = new HashMap<>();
map.put("key", 42);  // O(1)
int value = map.get("key");  // O(1)

Факторы влияющие на скорость:

• Качество hashCode() - должен равномерно распределять ключи
• Load factor (по умолчанию 0.75) - определяет когда происходит рехеширование
• Размер capacity - начальный размер массива корзин

Java 8 улучшила обработку коллизий - при большом количестве коллизий в корзине (>8 элементов) переходит с linked list на balanced tree (O(log n)).