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

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

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

Пример:

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