Когда скорость доступа к элементам в Hash-таблице будет равна O(n)

Скорость доступа к элементам в хеш-таблице деградирует до O(n) в двух случаях:

1. Коллизии – когда много элементов попадают в одну корзину (bucket). В худшем случае все элементы могут оказаться в одной корзине, превратив хеш-таблицу в связный список.

2. Плохая хеш-функция – если хеш-функция возвращает одинаковые значения для разных ключей, это приводит к коллизиям.

Пример плохой хеш-функции в Java:

@Override
public int hashCode() {
    return 42; // Все объекты будут в одной корзине
}

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