В конце концов я должен был к этому прийти. Когда-то я опубликовал статью «Я написал быструю хеш-таблицу», а потом ещё одну — «Я написал ещё более быструю хеш-таблицу». Теперь я завершил работу над самой быстрой хеш-таблицей. И под этим я подразумеваю, что реализовал самый быстрый поиск по сравнению со всеми хеш-таблицами, какие мне только удалось найти. При этом операции вставки и удаления также работают очень быстро (хотя и не быстрее конкурентов).
Я использовал хеширование по алгоритму Robin Hood с ограничением максимального количества наборов. Если элемент должен быть на расстоянии больше Х позиций от своей идеальной позиции, то увеличиваем таблицу и надеемся, что в этом случае каждый элемент сможет быть ближе к своей желаемой позиции. Похоже, такой подход действительно хорошо работает. Величина Х может быть относительно невелика, что позволяет реализовать некоторые оптимизации внутреннего цикла поиска по хеш-таблице.
Если вы хотите только попробовать её в работе, то можете скачать отсюда. Либо пролистайте вниз до раздела «Исходный код и использование». Хотите подробностей — читайте дальше.
Читать дальше →
[Перевод] Я написал самую быструю хеш-таблицу
Source: habrahabr