Я пытаюсь оптимизировать библиотеку, в которой я использую хеш-таблицу с блокировкой. Один из способов сделать это - заменить эту блокирующую структуру без блокировки.Существует ли стоп-блокировка хэш-таблиц, которые сохраняют порядок вставки?
Я нашел некоторые алгоритмы о, и я решил реализовать в С помощью этой статьи: Split-ordered lists: lock-free extensible hash tables
Проблема заключается в том, что этот вид структуры не сохраняет порядок вставки элементов, и мне нужна эта функция для две причины:
1), чтобы получить следующий элемент к текущему (в соответствии с приказом вставки, а не в порядке hashkey),
2), чтобы заменить старые записи (новыми), когда максимальное число элементов в ht. Это потому, что я использую хеш-таблицу как буфер, и я хочу зафиксировать ее размер.
Итак, я прошу вас, все блокировки хеш-таблицы без блокировки страдают от этой проблемы с отсутствием вставки? Или есть решение?
Если вы можете создать хеш-таблицу без блокировки, которая не сохраняет порядок вставки, и вы можете создать блокировку «прирастить этот счетчик», а затем на каждой вставке вы можете увеличить счетчик и сохранить пар и что по определению запоминает порядок. Возможно, ваш следующий вопрос: «... и как эффективно перечислять ключи в порядке ввода?» Не знаю; возможно, вы можете связать динамический массив, который сопоставляет индексы индекса вставки с ключами. Но у вас есть доказательство того, что ваш исходный вопрос имеет ответ «да». –
Если вам нужно сохранить порядок вставки, то, возможно, хеш-таблица (без блокировки или иначе) не является правильной структурой данных. Простой связанный список, очередь или deque могут быть лучше. – twalberg
Хэш-таблицы имеют свои приятные свойства, потому что они ** никогда не поддерживают порядок. –