В одном из прежних постов я рассказывал, как реализовать [«простейшую в мире lock-free хеш-таблицу»][1] на C++. Она была настолько проста, что было невозможно удалять из нее записи или менять ее размерность. С тех пор прошло несколько лет, и не так давно я написал несколько многопоточных ассоциативных массивов без таких ограничений. Их можно найти в моем проекте [Junction][2] на GitHub.

Junction содержит несколько многопоточных реализаций интерфейса map – даже «самая простая в мире» среди них, под названием `ConcurrentMap_Crude`. Для краткости будем называть ее **Crude** map. В этом посте я объясню разницу между Crude map и **Linear** map из библиотеки Junction. Linear — самый простой map в Junction, поддерживающий и изменение размера, и удаление.

Можете ознакомиться с объяснением того, как работает Crude map, [в первоначальном посте][3]. Если коротко, то она основана на _открытой адресации_ и _линейном пробировании_. Это значит, что она по сути является большим массивом ключей и значений, использующим линейный поиск. Во время добавления или поиска заданного ключа мы вычисляем хеш от ключа, чтобы определить, с какого места начать поиск. Добавление и поиск данных возможны в многопоточном режиме.

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

[1]: https://habrahabr.ru/company/wunderfund/blog/322496/
[2]: https://github.com/preshing/junction
[3]: http://preshing.com/20160201/new-concurrent-hash-maps-for-cpp/
[4]: https://habrastorage.org/files/e64/1eb/a82/e641eba82cc14f4c80fac5cacc26ea78.png
[5]: https://habrahabr.ru/post/324060/?utm_source=habrahabr&utm_medium=rss&utm_campaign=feed_posts#habracut