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