Внутренняя структура и процесс .NET Dictionary<TKey,TValue> - это высокооптимизированный дизайн, о котором говорил Саймон Купер в этом замечательном блоге .
В документах MSDN указано, что Add(TKey,TValue) - это O (1) - если только количество элементов в Словаре не соответствует емкости, то для этого необходимо сначала выполнить операцию динамического изменения размера, в результате чего в этих точках выполняется Add () O (n).
По мере увеличения словаря операции изменения размера становятся все более редкими, и поэтому можно сказать, что при усреднении по большому n Add () приближается к O (1).
Об этом свидетельствует Купер в этом графике общего прошедшего времени для n / 2 операций добавления как функции от n.
Тем не менее, средний худший случай производительности Add () равен O (n).
Мой вопрос: возможно ли спроектировать более стабильную структуру данных, чем словарь .NET?
В частности, я хочу, чтобы средний наихудший случай производительность операций добавления, удаления и извлечения всех составляла O (1).
Обратите внимание, что постоянство характеристик («большой O») является единственным релевантным критерием проектирования. Использование памяти и абсолютная производительность (включая степень кластеризации и производительность кэша) не соответствуют критериям проектирования.
Выбор начальной емкости, намного превышающей ожидаемые, является одним из вариантов, но это шаг инициализации, и я ищу проект структуры данных.