Как хэш-таблицы реализованы внутренне на популярных языках?

Perl использует массив со связанными списками для предотвращения конфликтов. Он имеет простую эвристику для автоматического удвоения размера массива по мере необходимости. Также есть код для обмена ключами между хешами, чтобы сэкономить немного памяти. Вы можете прочитать об этом в устаревшем, но все еще актуальном Perl Illustrated Guts в разделе «HV». Если вы действительно любите приключения, вы можете покопаться в hv.c .

Раньше алгоритм хеширования был довольно простым, но теперь с Unicode он, вероятно, намного сложнее. Поскольку алгоритм был предсказуем, произошла DoS-атака, в результате которой злоумышленник сгенерировал данные, которые могли вызвать коллизии хешей. Например, огромный список ключей, отправленных на веб-сайт в виде данных POST. Программа Perl, скорее всего, разделит его и выгружает в хэш, который затем помещает все в одну корзину. Полученный хэш был O (n), а не O (1). Отправьте на сервер большое количество запросов POST, и вы можете засорить ЦП. В результате Perl теперь возмущает хэш-функцию небольшим количеством случайных данных.

Вы также можете посмотреть , как Parrot реализует базовые хеши , что значительно менее ужасно, чем реализация Perl 5.

] Что касается «наиболее эффективного и практичного», используйте чужую хеш-библиотеку. Ради бога, не пишите сами для использования в производстве. Уже есть много надежных и эффективных.

Вы также можете посмотреть , как Parrot реализует базовые хэши , что значительно менее устрашающе, чем реализация Perl 5.

Что касается «наиболее эффективного и практичного», используйте чужую хеш-библиотеку. Ради бога, не пишите сами для использования в производстве. Уже есть много надежных и эффективных.

Вы также можете посмотреть , как Parrot реализует базовые хэши , что значительно менее устрашающе, чем реализация Perl 5.

Что касается «наиболее эффективного и практичного», используйте чужую хеш-библиотеку. Ради бога, не пишите сами для использования в производстве. Уже есть много надежных и эффективных.

Таблицы Lua используют чрезвычайно изобретательную реализацию , которая для произвольных ключей ведет себя как «массив корзин», но если вы используете последовательные целые числа в качестве ключей, у них есть то же представление и накладные расходы на пространство, что и массив. В реализации каждая таблица имеет хэш-часть и часть массива .

Я думаю, что это круто: -)

Привлекательный хаос содержит сравнение библиотек хеш-таблиц и обновление . Исходный код доступен на языках C и C ++

Сбалансированные деревья вроде как поражают цель хеш-таблицы, поскольку хеш-таблица может обеспечивать поиск за (амортизированное) постоянное время, тогда как средний поиск в сбалансированном дереве - O (log (n)).

Отдельная цепочка (массив со связанным списком) действительно работает достаточно хорошо, если вы имеет достаточно ведер, и ваша реализация связанного списка использует распределитель пула, а не malloc () для каждого узла из кучи по отдельности. Я' Я обнаружил, что при правильной настройке он столь же эффективен, как и любая другая техника, и его очень легко и быстро писать. Попробуйте начать с 1/8 количества сегментов, чем исходные данные.

Вы также можете использовать открытую адресацию с квадратичным или полиномиальным зондированием , как это делает Python .

If you can read Java, you might want to check out the source code for its various map implementations, in particular HashMap, TreeMap and ConcurrentSkipListMap. The latter two keep the keys ordered.

Java's HashMap uses the standard technique you mention of chaining at each bucket position. It uses fairly weak 32-bit hash codes and stores the keys in the table. The Numerical Recipes authors also give an example (in C) of a hash table essentially structured like Java's but in which (a) you allocate the nodes of the bucket lists from an array, and (b) you use a stronger 64-bit hash code and dispense with storing keys in the table.

Crashworks имел в виду…

Назначение хеш-таблиц - постоянный поиск, добавление и удаление. С точки зрения алгоритма, операция для всех операций амортизируется O (1). В то время как в случае использования tree ... время работы в худшем случае будет O (log n) для сбалансированного дерева. N - количество узлов. но действительно ли у нас реализован хэш в виде дерева?