Какая скорость доступа к значениям в HashMap

В среднем, доступ к элементам в HashMap осуществляется за константное время O(1) — для операций get() и put(). Это достигается благодаря хешированию ключей и использованию массива бакетов.

Нюансы:

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

Пример:

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 10);
int value = map.get("key1");  // O(1) в среднем

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

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