время поиска в массиве php - PullRequest
Новая
       30

время поиска в массиве php

2 голосов
/ 04 января 2012

Я просто думал, что прочесал бы это, чтобы найти ответ: http://svn.php.net/viewvc/php/php-src/

Но я не смог его найти. В C ++ <map> реализовано сбалансированное двоичное дерево поиска со значениями константных ключей. это хорошо, вы получаете O(log n) время поиска, вставки, удаления и т. д. O(n) время перечисления.

Что мне интересно, так это основная структура данных массивов PHP. В PHP-массивах есть несколько SO-сообщений, в которых говорится, что «они делают одно и то же, так что не беспокойтесь об этом!». не то, что я после. Это поиск O(1) (хэш-таблица) или O(log n) (сбалансированное двоичное дерево)? (например)

Если кто-нибудь может помочь мне или указать мне правильный исходный файл PHP C, это было бы замечательно (хотя небольшое объяснение было бы хорошо - я действительно плох в C). Или, если у вас есть отличная информация о PHP массивах, это тоже хорошо - я пытаюсь понять всю базовую структуру данных.

1 Ответ

2 голосов
/ 04 января 2012

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

Реализация на самом деле является своего рода HashTable.

-> http://php.net/manual/en/language.types.array.php
-> Как массив PHP реализован на уровне C?

...