Как внутренне реализованы хеш-таблицы на популярных языках? - PullRequest
26 голосов
/ 24 мая 2009

Может ли кто-нибудь пролить свет на то, как популярные языки, такие как Python, Ruby реализуют внутренние хеш-таблицы для поиска символов? Используют ли они классический метод «массив со связанным списком» или сбалансированное дерево?

Мне нужен простой (меньше LOC) и быстрый метод для индексирования символов в DSL, написанном на C. Интересно, что другие нашли наиболее эффективным и практичным.

Ответы [ 7 ]

16 голосов
/ 24 мая 2009

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

Одной из наиболее образовательных версий является реализация хэша на языке Tcl в файле tcl / generic / tclHash.c . Более половины строк в файле - это комментарии, объясняющие все в деталях: распределение, поиск, различные типы хеш-таблиц, стратегии и т. Д. * читабельно.

12 голосов
/ 24 мая 2009

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

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

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

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

8 голосов
/ 26 мая 2009

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

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

4 голосов
/ 24 мая 2009

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

4 голосов
/ 24 мая 2009

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

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

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

2 голосов
/ 24 мая 2009

Если вы можете прочитать Java, вы можете проверить исходный код для его различных реализаций карты, в частности HashMap, TreeMap и ConcurrentSkipListMap. Последние два держат ключи в порядке.

Java HashMap использует стандартную технику, о которой вы упомянули, для цепочки в каждой позиции сегмента. Он использует довольно слабые 32-битные хеш-коды и сохраняет ключи в таблице. Авторы «Числовых рецептов» также приводят пример (на С) хеш-таблицы, по существу структурированной как Java, в которой (а) вы выделяете узлы списков сегментов из массива и (б) вы используете более сильный 64-битный хеш код и обойтись без хранения ключей в таблице.

1 голос
/ 24 мая 2009

Что Crashworks хотел сказать, было ....

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...