![image][1]



В конце концов я должен был к этому прийти. Когда-то я опубликовал статью «[Я написал быструю хеш-таблицу][2]», а потом ещё одну — «[Я написал ещё более быструю хеш-таблицу][3]». Теперь я завершил работу над самой быстрой хеш-таблицей. И под этим я подразумеваю, что реализовал самый быстрый поиск по сравнению со всеми хеш-таблицами, какие мне только удалось найти. При этом операции вставки и удаления также работают очень быстро (хотя и не быстрее конкурентов).



Я использовал хеширование по алгоритму Robin Hood с ограничением максимального количества наборов. Если элемент должен быть на расстоянии больше Х позиций от своей идеальной позиции, то увеличиваем таблицу и надеемся, что в этом случае каждый элемент сможет быть ближе к своей желаемой позиции. Похоже, такой подход действительно хорошо работает. Величина Х может быть относительно невелика, что позволяет реализовать некоторые оптимизации внутреннего цикла поиска по хеш-таблице.



Если вы хотите только попробовать её в работе, то можете скачать [отсюда][4]. Либо пролистайте вниз до раздела «Исходный код и использование». Хотите подробностей — читайте дальше.

[Читать дальше →][5]

[1]: https://habrastorage.org/files/ae9/0bc/82c/ae90bc82ce48463b84451d079dcc4a8c.jpg
[2]: https://probablydance.com/2014/05/03/i-wrote-a-fast-hash-table/
[3]: https://probablydance.com/2014/05/31/i-wrote-a-faster-hash-table/
[4]: https://github.com/skarupke/flat_hash_map/blob/master/flat_hash_map.hpp
[5]: https://habrahabr.ru/post/323242/?utm_source=habrahabr&utm_medium=rss&utm_campaign=feed_posts#habracut