Как стать автором
Обновить

Комментарии 40

Васнецов он…
Ох, я плох в искусстве.
Я похоже тоже…
А он там даже копирайт поставил ) слева снизу.
Да-да! Я видел, но так и не разглядел что там написано, увы.
Где?
Обычно buckets в русскоязычной литературе называют «корзинами», а не «вёдрами».
НЛО прилетело и опубликовало эту надпись здесь
Увеличивается в два раза при заполнении для амортизации операции выделения памяти, а не потому что в нет массивов с нефиксированным размером.
Если нужна матчасть, гуглите амортизационный анализ.
в C нет массивов*
В реализации по большей части для того, чтобы уменьшить число коллизий и соответственно уменьшить число итераций по сколлайденным бакетам при поиске.
Может расскажете нам про амортизацию выделения памяти под массив для бакетов хэштаблицы? Гугл особо делиться информацией не хочет.
Или Вы имели ввиду, что амортизацией является именно удвоение массива, а не, скажем, инкрементальное увелечение? В таком случае да, я даже не знал что у этого действия есть свое название и как-то глупо было бы увеличивать массив инкрементально, поэтому я не стал вдаваться в детали очевидного решения.
И вообще хотя бы про хэштаблицы — это же совсем базовые вещи. При чём тут вообще PHP?
Гм… Что значит причем тут пхп? Загляните в заголовок, там сюрприз =)
Это базовая структура данных сделанная в пхп так же как в во всех других языках, правда немного через задницу, как это обычно в пхп.
Через задницу т.к. это комбинированная структура. Я смотрю, что даже автор к примеру не знает как организовать эффективный список на основе массива.
У вас отличное зрение!
Что-то вы про классический hash table слишком подробно расписали, а чем PHP-шная реализация отличается от классической не отметили.
Я, например, не понял чем обеспечивается упорядоченность массива после сортировки… pListNext может ссылаться на элемент из другой корзины? Получается, что эффективная итерация в обратном порядке невозможна?
А, блин. Понял. Тут в одной структуре скрестили практически независимые друг от друга хеш-таблицу (h, pData) и двусвязный список (pListNext, pListLast)…
И почему назвали pListLast а не pListPrev…

Чувствую оверхед на это должен быть приличный (по 3 указателя на каждый элемент против 1 на классическую hash table и 0 для массива). Ну и поиск по числовому индексу в такой структуре происходит через хеш-таблицу тоже, что не очень круто.

Кстати, кто-то объяснит зачем им понадобился именно двусвязный список? Или это исключительно для удаления элементов?
pListLast меня тоже сначала смутил… И не понятно зачем нужен pLast (могли бы и односвязным списком для сколлайденых обойтись)

А в чем проблема поиска по числовому индексу через хештаблицу? Он не может быть реализован иначе т.к. массив в пхп это еще и мэп и вы можете использовать не только последовательные ключи.

Двусвязный так же и сортировку упрощает. На самом деле в бакете в пхп, так на память, где-то шесть членов и примерно десять в хештаблице (в структурах), это об экономии памяти.
Проблема поиска по числовому индексу в том, что это намного медленнее, чем в массивах в более типизированных языках. Я всё думал, может в пхп всё же массивы реализованы в комбинации обычный массив (для целых индексов) + хэш… Но в такой реализации непонятно как реализовать: $m[0] = $m[10000000] = «ok». Всё же надеялся, что светлые умы что-нибудь да придумали)
Я не знаю такого алгоритма, который был бы в данном случае оптимальнее, чем open addressed hash table. А если в пхп нужен обычный массив (не такой, где при размере в 100 элементов можно пользоваться ключом больше 99), то можно юзать SplFixedArray.
О, это же Open adressed hash tables en.wikipedia.org/wiki/Open_addressing
Даже не подозревал что они используются. Это и про python 2.7 и про 3.x?
Linear Probing используется в стандартном Java-классе IdentityHashMap.
Брэндон делал замеры для доклада на 2.6.
Я решил не возвращаться к нашему кейсу с ключами 54 и 90… А вообще спасибо, мне нравятся ваши статьи, довольно интересно заглядывать внутрь.
Не очень понял график с памятью. Типа при 4096 элементах памяти требуется дофига, а при 4097 уже с гулькин нос? И вообще научитесь подписывать оси на графике. Это ж технический пост, а не какой-то дешёвый маркетинг.
4096-8191 элементов потребляется одинаковое количество памяти. Графики можете в виде лестницы представить.
А вот вы неправы. Я вчитался в детали и запустил тест. График в статье показывает разницу до и после вставки определённого элемента и падает он не до нуля, а до 132-136. А график кумулятивного потребления памяти выглядел бы так:

(по вертикали общий объём памяти в байтах)
Заметьте, совсем другая картина: нет никаких ужасающих скачков. Сами корзины едят гораздо больше памяти, чем собственно хэш-таблица.
Вот оно что. Да, недопонял я этот момент. Спасибо
Интересно ещё представить график в другом виде, как я это делал в своей недавней статье:

По вертикали отношение используемой памяти в байтах к числу элементов в массиве, то есть количество байт на элемент. Тестировалось на PHP 5.3.2-1ubuntu4.14 (i686).
Видно, что в пределе расширение хэш-таблицы вызывает прыжки на 4 байта, со 140 до 144, вызывая трёхпроцентные колебания вокруг общего среднего. Кстати, интересен вопрос, почему у маленьких таблиц затраты на запись от 132, а дальше нижний порог доходит до 140.
Да, простите за хреновые графики. Просто так долго искал тулзу, которая способна построить график по, хотя бы, 1000 точек (тобишь не юзает гугловские чарты, которые вываливаются в 400 из-за длинных урлов), что терпения уже еле хватало на детали.
Кстати если кто-нибудь подскажет действительно хорошую тулзу для чартов, буду признателен.
Я использую неправославный Excel, но вообще люди любят gnuplot.
Спасибо
Асимптотика O(1) при работе с массивами радует.
Когда читаю книги о том же PHP, всегда, когда сталкивался вновь с теми же массивами (циклы, функции и тп.), хотелось видеть не только описание на примере, но также пару строк о том, где эти массивы применяются при разработке приложений. Ведь, легче разобраться в том, что понятно, как и где это можно будет применить на практике.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.