Самая простая в мире lock-free хеш-таблица

[lorc]

Не совсем понятно почему массив никогда не будет заполнен.

Операцию удаления реализовать кажется несложно: атомарно записать 0 в найденный ключ. Само значение не трогать.

А вот с хранением данных отличных от int32/int64 сложнее. Я могу придумать только один метод — выделять память для каждого значения, а в таблице хранить атомарный указатель на этот буфер. Но при таком подходе нам будет нужен lock-free аллокатор, потому что обычный malloc скорее всего пользуется мютексами.

[arseny30]

С удалением проблемы. Нужно не только 0 записать, но и сдвинуть влево часть ключей, идущих прямо за ним.

И не понятно, как изменять значение, когда удаленный ключ добавится снова. Ведь это значение сейчас кто-то может еще читать.

[lorc]

А, да, действительно. Не подумал. И то и другое представляет проблему.

Можно попробовать завести ещё один специальный ключ типа 0xFFFFFFFF для удаленных значений. Это решит первую проблему.

Со второй сложнее. Не могу придумать решение сходу.

[robert_ayrapetyan]

>безблокировочные хеш-таблицы частота кадров в самом неблагоприятном случае улучшилась с 4 FPS до 10 FPS.
Замерять скорость работы с структурой данных в FPS это забавно, а можно хотя бы в «запросах в секунду» предоставить бенчмарки? И что с чем сравнивалось?