Как ассоциативные массивы реализованы в PHP?
Может кто-нибудь объяснить, как PHP реализует ассоциативные массивы? Какую базовую структуру данных использует PHP? Хеширует ли PHP ключ и хранит ли его в какой-то хэш-карте? Мне любопытно, потому что мне было интересно, какова производительность ассоциативных массивов при вставке и поиске ключей.
Ответы 5
Ну, как бы то ни было, массивы все PHP являются ассоциативными массивами.
Согласно источникам на различных форумах, это все хеш-таблицы: http://www.usenet-forums.com/php-language/15348-zend-engine-array-implementation.html
Если вы хотите быть уверенным, прочтите исходный код, затем скомпилируйте его, но убедитесь, что вы можете доверяй своему компилятору (Предупреждение: PDF и не связанные, но очень крутые).
@EBGreen правильный.
Это дает вам некоторые интересные проблемы с производительностью, особенно когда массив рассматривается как список и используется оператор [] (добавление массива). Кажется, что PHP не кэширует самый большой числовой ключ и не добавляет к нему единицу, вместо этого он, кажется, просматривает все ключи, чтобы найти, каким должен быть следующий числовой ключ. Я переписал скрипты на Python из-за унылой производительности PHP в виде массива в виде списка.
У ассоциативных массивов есть стандартные накладные расходы на производительность dict / hash.
Ты уверен насчет этого? Я только что провел тесты на тестовом массиве из 1000 записей (копирование в новый массив, одну за другой), и если вы не укажете ключ для нового массива, он будет последовательно на 7% быстрее (на PHP 5.2.6 )
Возможно, они его недавно изменили. Я использовал 5.1, когда делал работу. Массив PHP был УЖАСНЫМ, когда вы говорите о 10К или более записях.
AFAIK это не так, сравните: В хеш-таблице zend есть элемент nNextFreeElement ...
@RickyMason. Вероятно, вы бы этого не сделали, но для тщательного тестирования вычисление времени для каждого элемента для 10, 100, 1k и 10k действительно выявило бы проблемы с производительностью масштабируемости, особенно если есть вероятность, что 10k, возможно, придется обработать.
Это хеш-таблица. Объявление типа и функция хеширования находятся здесь:
http://svn.php.net/viewvc/php/php-src/trunk/Zend/zend_hash.h?view=markup
В spl (стандартная библиотека php) есть облегченный массив и связанный список.
Источник перемещен на GitHub: github.com/php/php-src/blob/master/Zend/zend_hash.h
Ссылка на ответ, получившая наибольшее количество голосов, не работает и не дает подробного объяснения.
PHP написан на C, а основная структура - это просто массив C. Массивы C - это просто фрагменты памяти. Индексы в массивах C должны быть непрерывными, у вас не может быть индекса 0 и индекса 1000, который идет после него. Чтобы ключи ассоциативного массива работали, перед их добавлением в массив C они преобразуются в соответствующие индексы C с помощью хэш-функции.
Для полного объяснения я нашел эту ссылку гораздо более информативной.
http://nikic.github.io/2012/03/28/Understanding-PHPs-internal-array-implementation.html
Я оставлю эту ссылку, чтобы кто-нибудь еще мог ее изучить, но вы можете просмотреть фактический исходный код C для PHP на http://svn.php.net/viewvc/php/php-src/