Comments 11
По переводу, - терминология хромает.
По смыслу, - сама идея таблицы с открытой (или, сплошной, как её еще называют в русской литературе по алгоритмам) адресацией и линейным зондированием действительно хороша, и, на современных архитектурах ЦП показывает себя намного лучше многих других вариантов. Однако, реализация излишне усложнена. Можно сделать гораздо проще, и, не менее быстро.
Присоединяюсь к мнению. Хотя бы про надрогбия пояснить надо, а то выходит, что тем кому было понятно и так понятно, а остальным будет сложно.
И (риторический) вопрос к автору. Я ведь все тоже самое давно читал в "Искусстве Программирования", что автор привнес нового?
Ну и кроме того открытая адресация не всегда быстрее например метода цепочек (который нередко в реализации ещё проще), очень зависит от того, на какие из операций у нас приоритет.
Да, метод цепочек еще проще в реализации, и, часто эффективнее, если размеры ключа/значения достаточно велики.
А, если пара ключ+значение укладываются хотя бы в половину-четверть длины строки кэша, то открытая адресация с линейным зондированием обычно выигрывают.
Вроде же "всё придумано до нас" - есть swiss table, который решает все эти проблемы: отдельный блок для хешей(1 байт каждый), отдельный для ключей+значений; квадратичное пробирование, но блоками по 8/16 ячеек/байт. Вроде как такая схема работает всегда быстрее (кроме итерации — но кто вообще итерируется по хештаблицам (я знаю кто =/))
В общем случае, - да, но для частного случая с маленьким размером ключ+значение все же будет медленнее раза в полтора-два при большом размере таблицы. Просто потому, что на больших таблицах узкое место, - случайный доступ в память. И, у подобной простой реализации он будет только один. А у swiss table, - два (отдельно в блок хэшей и в блок ключей+значений).
А можете привести пример, когда метод цепочек будет быстрее?
Достаточно взять размер значения (value) больше двукратного размера страницы кэша ЦП. Все бонусы от особенностей работы префетчера и кэша ЦП на open addressed linear probing будут утеряны. Ну, и, взять таблицу, которая не помещается к кэш ЦП целиком.
И, кроме того, в сценарии, когда операций добавления и удаления примерно равное количество и они примерно в той же последовательности идут (но при этом может быть очень очень много добавлений подряд). При открытой адресации будем очень много переставлять элементы, а в случае с цепочками удаление будет чаще всего просто подрезанием головы соответствуюшего списка.
Очень странная структура. Она работает быстро только для весьма равномерно распределенных ключей во всем диапазоне значений, что на практике далеко не всегда бывает. В противном случае там почти гарантирована линейная сложность из-за длинной цепочки коллизии.
Спасибо, но только за ссылку на оригинальную статью.
Перевод можно было бы сделать получше. Пример: "... Разумеется, у такого дизайна есть пределы растяжимости ...", правильнее было бы перевести "...может простираться только до определенного предела..."
Моя любимая маленькая хеш-таблица