Ответ
Хеш-таблица, на которой построены ассоциативные массивы в PHP, обеспечивает в среднем константное время выполнения ключевых операций.
Сложность основных операций:
- Вставка (
$table[$key] = $value): O(1) (амортизированное). - Поиск по ключу (
$value = $table[$key]): O(1). - Удаление по ключу (
unset($table[$key])): O(1).
Объяснение "амортизированного O(1)": Иногда при вставке требуется рехеширование (увеличение размера внутреннего массива и пересчет хешей для всех элементов), что стоит O(n). Однако эта дорогая операция происходит редко, и ее стоимость "распределяется" по множеству быстрых вставок, давая в среднем O(1).
Пример на PHP:
$userCache = []; // Хеш-таблица
// Вставка: O(1)
$userCache['user_123'] = ['name' => 'Alice', 'role' => 'admin'];
$userCache['user_456'] = ['name' => 'Bob', 'role' => 'editor'];
// Поиск: O(1)
$aliceData = $userCache['user_123']; // Мгновенный доступ по хешу ключа 'user_123'
// Удаление: O(1)
unset($userCache['user_456']);
// Итерация по всем элементам: O(n)
foreach ($userCache as $id => $data) {
echo $data['name'];
}Что влияет на производительность? Качество хеш-функции PHP (минимизирует коллизии) и коэффициент заполнения. В реальности для хеш-таблиц PHP худший случай O(n) почти не наблюдается. Это делает их идеальными для кешей, словарей и быстрого поиска данных по ключу.