В предыдущих статьях (раз, два) мы рассматривали классический hash map с хеш-таблицей и списком коллизий. Был построен lock-free ordered list, который послужил нам основой для lock-free hash map.
К сожалению, списки характеризуются линейной сложностью поиска O(N), где N — число элементов в списке, так что наш алгоритм lock-free ordered list сам по себе представляет небольшой интерес при больших N.
Или все же представляет?..
Читать полностью »