Может ли кто-нибудь пролить свет на то, как популярные языки, такие как Python и Ruby, реализуют внутренние хеш-таблицы для поиска символов? Используют ли они классический метод «массива со связанным списком» или используют сбалансированное дерево?
Мне нужен простой (меньше LOC) и быстрый метод индексации символов в DSL, написанном на C. Мне было интересно, что другие сочли наиболее эффективным и практичным.
Классический «массив хэш-контейнеров», о котором вы упоминаете, используется в каждой реализации, которую я видел.
Одной из самых познавательных версий является реализация хэша на языке Tcl в файле tcl/generic/tclHash.c. Более половины строк в файле представляют собой комментарии, объясняющие все в деталях: размещение, поиск, различные типы хеш-таблиц, стратегии и т. д. Примечание: код, реализующий язык Tcl, действительно< /em> читаемый.
Perl использует массив со связанными списками для хранения коллизий. Он имеет простую эвристику для автоматического удвоения размера массива по мере необходимости. Также есть код для обмена ключами между хэшами, чтобы сэкономить немного памяти. Вы можете прочитать об этом в устаревшем, но все еще актуальном Perl Illustrated Guts. под "ВВ". Если вы действительно любите приключения, вы можете покопаться в hv.c.
Алгоритм хеширования раньше был довольно простым, но теперь он, вероятно, намного сложнее с Unicode. Поскольку алгоритм был предсказуем, произошла DoS-атака, в результате которой злоумышленник сгенерировал данные, которые могли вызвать коллизии хэшей. Например, огромный список ключей, отправляемых на веб-сайт в виде данных POST. Программа Perl, скорее всего, разделила бы его и выгрузила бы в хэш, который затем запихнул бы все это в одно ведро. Полученный хэш был O(n), а не O(1). Направьте на сервер множество POST-запросов, и вы можете забить ЦП. В результате Perl теперь возмущает хеш-функцию небольшим количеством случайных данных.
Вы также можете посмотреть как Parrot реализует базовые хэши, что значительно менее страшно, чем реализация Perl 5.
Что касается «наиболее эффективного и практичного», используйте чужую хеш-библиотеку. Ради бога, не пишите сами для производственного использования. Там уже есть миллион надежных и эффективных.
Lua таблицы используют совершенно гениальная реализация, которая для произвольных ключей ведет себя как "массив сегментов", но если вы используете последовательные целые числа в качестве ключей, она имеет такое же представление и пространство накладные расходы в виде массива. В реализации каждая таблица имеет хеш-часть и массивную часть.
Я думаю, это круто :-)
Привлекательный хаос имеет сравнение библиотек хэш-таблиц и update. Исходный код доступен и написан на C и C++.
Сбалансированные деревья как бы противоречат назначению хеш-таблиц, поскольку хеш-таблица может обеспечить поиск за (амортизированное) постоянное время, тогда как средний поиск в сбалансированном дереве составляет O (log (n)).
Раздельная цепочка (массив со связанным списком) действительно работает достаточно хорошо, если у вас достаточно сегментов, и ваша реализация связанного списка использует распределитель пула, а не malloc() для каждого узла из кучи по отдельности. Я обнаружил, что при правильной настройке он столь же эффективен, как и любой другой метод, и его очень легко и быстро писать. Попробуйте начать с 1/8 количества сегментов от исходных данных.
Вы также можете использовать открытую адресацию с квадратичным или полиномиальным определением, как это делает Python.
Если вы умеете читать Java, возможно, вы захотите проверить исходный код различных реализаций карт, в частности HashMap, TreeMap и ConcurrentSkipListMap. Последние двое держат ключи в порядке.
Java HashMap использует стандартный метод, который вы упомянули о цепочке в каждой позиции корзины. Он использует довольно слабые 32-битные хеш-коды и хранит ключи в таблице. Авторы Numerical Recipes также приводят пример (на C) хеш-таблицы, по существу структурированной как в Java, но в которой (а) вы выделяете узлы списков сегментов из массива и (б) вы используете более надежный 64-битный хеш. код и отказаться от хранения ключей в таблице.
TreeMap реализовано на основе Red-BlackTree, ConcurrentSkipListMap реализовано на основе SkipList.
- person coderz; 25.03.2015
Crashworks хотел сказать, что...
Целью хеш-таблиц является постоянный поиск, добавление и удаление. С точки зрения алгоритма, операция для всех операций амортизируется за O(1). Принимая во внимание, что если вы используете дерево... время работы в худшем случае будет O (log n) для сбалансированного дерева. N - количество узлов. но действительно ли у нас есть хеш, реализованный как дерево?
