C #: словарь отсортирован по ключу с поиском ~ O (1)

Question

не нашел ответа на этот вопрос.

Мне нравится KeyedCollection, потому что он сохраняет порядок вставки и время поиска ключа ~ O (1).

Теперь я ищуаналогичный тип, который будет сортировать по ключу вместо порядка вставки.

SortedDictionary делает именно это, однако реализация в точности противоположна тому, что я хочу.Вставки O (1), поиск O (log n).Тем не менее, я хотел бы искать ~ O (1) (например, хэш-таблицу), и вставки могут быть O (log n) (двоичное дерево?).

Существует ли это?Не должно быть жесткой реализации мудро ...

Спасибо

Answer 1

В .NET BCL нет структуры данных, обеспечивающей то, что вы ищете. Может быть, есть сторонние решения.

В большинстве случаев O (log n) будет достаточно. Возможно, вы будете микрооптимизировать, если попытаетесь реализовать собственную структуру данных.

Однако самым быстрым способом сделать это может быть простое объявление нового класса, который имеет словарь и SortedDictionary в качестве закрытых членов. Для всех методов чтения вы бы выбрали более эффективный словарь для возврата значения. Для всех методов записи вы должны обрабатывать оба внутренних словаря и быть осторожными, чтобы они оставались синхронизированными. Это может быть не самый эффективный подход к памяти, хотя. Но если вы хотите оптимизировать здесь, вам придется заново реализовать большую часть функциональности хеш-таблицы.

Answer 2

Я думаю, что OrderedBag может быть тем, что вы хотите:

Частые вставки в отсортированную коллекцию