Ассоциативная структура данных с произвольным доступом и случайным удалением на основе порядка вставки, элемент добавляется только

Question

Структура данных, которую я ищу, должна быть стандартной ассоциативной, позволяющей быстро (по крайней мере, лучше, чем O(n)) извлекать / заменять / добавлять / удалять элемент с заданным уникальным ключом, очень похожим на любое дерево или хэш-карту.

bool ContainsKey(TKey key);
bool TryGetValue(TKey key, out TValue value);
void Remove(TKey key);
Add(TKey key, TValue value);
Update(TKey key, TValue value);
int Count { get; }

Сложная часть также состоит в том, чтобы показать следующее (лучше, чем O(n)):

int IndexOf(TKey key);
TKey GetKey(int index);

index - порядок вставки (во время добавления), обновляется при удалении.

Вот пример того, что я хочу:

InsertionOrderedMap<string, T> map = new InsertionOrderedMap<string, T>();

map.Add("id1", t1);
map.Add("id2", t2);
map.Add("id0", t0);

Assert.AreEquals(0, map.IndexOf("id1"));
Assert.AreEquals(1, map.IndexOf("id2"));
Assert.AreEquals(2, map.IndexOf("id0"));

map.Remove("id2");

Assert.AreEquals(0, map.IndexOf("id1"));
Assert.AreEquals(-1, map.IndexOf("id2"));
Assert.AreEquals(1, map.IndexOf("id0"));

map.Update("id0", t3);

Assert.AreEquals(0, map.IndexOf("id1"));
Assert.AreEquals(1, map.IndexOf("id0"));

Assert.AreEquals("id1", map.GetKey(0));
Assert.AreEquals("id0", map.GetKey(1));

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