Я не уверен, что полностью согласен с мнением Конрада о том, что большое количество операций удаления разрушит структуру хеш-таблицы.
Без операций удаления вы можете сохранить все объекты в хеш-таблице и сохранить верхнюю букву K в куче приоритетов, которая будет постепенно обновляться. Это сделало бы вставку O (1 + log K), то есть постоянное время в N, предполагая, что K является постоянным и не зависит от N (N = количество объектов в таблице). Однако это не работает, если у вас есть операция удалить . Предложенная куча Фибоначчи имеет амортизированную операцию удаления O (log N), поэтому она также не дает хорошего решения, поскольку все объекты необходимо будет хранить в куче, и если вы в конечном итоге удалите каждый вставленный объект, вы получите O (log N) поведение в целом для пары вставка + удаление.
Возможно, я бы попробовал следующий подход:
Храните объекты в хеш-таблице, предполагая, что вам нужна вся таблица для каких-то других целей, кроме возврата верхних объектов. Поддерживайте приоритетную кучу (стандартная куча), которая содержит объекты K * C для C, значение которого необходимо искать экспериментально. Всякий раз, когда вы добавляете новый объект, попробуйте вставить его в кучу; если он помещается в пространство K C (куча еще не заполнена, или он отталкивает другой объект), вставьте его и установите бит в хеш-таблицу, чтобы указать, что объект находится в куче; когда вы выталкиваете объект из кучи, очищайте бит. Когда вы удалите объект, проверьте бит; если бит = 1, т. е. объект находился в куче, удалите его оттуда (его нужно искать, если у вас нет указателя на него из хеш-таблицы; лучше сохранить указатель). Что происходит сейчас, так это то, что куча уменьшается. Ключевым моментом является то, что , пока в куче еще как минимум K объектов , в нем гарантированно содержатся все верхние K объектов. Вот где появляется фактор С, поскольку он обеспечивает «запас» для кучи. Когда размер кучи опускается ниже K, вы запускаете линейное сканирование всей хеш-таблицы и заполняете кучу обратно до емкости K C.
Установка C является эмпирической, потому что она зависит от того, как ваши объекты приходят и уходят; но его настройка должна быть простой, поскольку вы можете настроить его только на основе профилирования во время выполнения.
Сложность: вставка O (1 + log (KC)). Remove - это O (1 + p log (KC) + q N), где p - вероятность того, что удаленный объект был в куче, а q - вероятность того, что куча должна быть восстановлена. р зависит от характеристик того, как объекты приходят и уходят. Для простого анализа мы можем установить p = (KC / N), то есть принять равномерную вероятность. q еще более чувствителен к «потоку» объектов. Например, если новые объекты в целом со временем увеличивают свою стоимость и вы всегда удаляете более старые объекты, q стремится к нулю.
Обратите внимание, что, как ни странно, p равно обратно пропорционально пропорционально N, так что на самом деле эта часть ускоряется при увеличении N:)