Как определяется время получения значения по ключу в структуре данных?

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

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

Пример:

$array = ['key' => 'value'];
echo $array['key']; // быстрый доступ по ключу