Como é determinado o tempo de obtenção do valor por chave na estrutura de dados?

Na estrutura de dados, o tempo para obter um valor por chave depende do tipo de estrutura e do método de implementação. Por exemplo, em arrays associativos (tabelas de hash), usados em PHP para arrays com chaves, o tempo de acesso médio é O(1) — tempo constante, graças ao cálculo rápido do hash da chave.

No entanto, no pior caso (quando há colisões), o tempo pode aumentar até O(n). Em PHP, os arrays são implementados como tabelas de hash, portanto, o acesso por chave geralmente é muito rápido.

Exemplo:

$array = ['key' => 'value'];
echo $array['key']; // acesso rápido por chave