Associative data structure with random access and random removals based on insertion order, item are only appended

Question

The data structure I am looking for should be a standard associative, allowing fast (at least better than O(n)) retrievals/replaces/adds/removals of an item given a unique key, much like any tree or hashmap.

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; }

The tricky part is to also expose the following (better than O(n) as well):

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

index being the insertion order (at the time of the Add), updated if removals occur.

Here is an example of what I want:

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));

I think I have an idea of how to implement one myself, but I would like to know if such container already exist.