How to insert an item into a key/value pair object?

Ok...here's a softball question...

I just need to be able to insert a key/value pair into an object at a specific position. I'm currently working with a Hashtable which, of course, doesn't allow for this functionality. What would be the best approach?

UPDATE: Also, I do need the ability to lookup by the key.

For example...oversimplified and pseudocoded but should convey the point

// existing Hashtable
myHashtable.Add("somekey1", "somevalue1");
myHashtable.Add("somekey2", "somevalue2");
myHashtable.Add("somekey3", "somevalue3");

// Some other object that will allow me to insert a new key/value pair.
// Assume that this object has been populated with the above key/value pairs.
oSomeObject.Insert("newfirstkey","newfirstvalue");

Thanks in advance.

List<KeyValuePair<string, string>> kvpList = new List<KeyValuePair<string, string>>()
{
    new KeyValuePair<string, string>("Key1", "Value1"),
    new KeyValuePair<string, string>("Key2", "Value2"),
    new KeyValuePair<string, string>("Key3", "Value3"),
};

kvpList.Insert(0, new KeyValuePair<string, string>("New Key 1", "New Value 1"));

Using this code:

foreach (KeyValuePair<string, string> kvp in kvpList)
{
    Console.WriteLine(string.Format("Key: {0} Value: {1}", kvp.Key, kvp.Value);
}

the expected output should be:

Key: New Key 1 Value: New Value 1
Key: Key 1 Value: Value 1
Key: Key 2 Value: Value 2
Key: Key 3 Value: Value 3

The same will work with a KeyValuePair or whatever other type you want to use..

Edit -

To lookup by the key, you can do the following:

var result = stringList.Where(s => s == "Lookup");

You could do this with a KeyValuePair by doing the following:

var result = kvpList.Where (kvp => kvp.Value == "Lookup");

Last edit -

Made the answer specific to KeyValuePair rather than string.

Maybe the OrderedDictonary will help you out.

Do you need to look up objects by the key? If not, consider using List<Tuple<string, string>> or List<KeyValuePair<string, string>> if you're not using .NET 4.

I would use the Dictionary<TKey, TValue> (so long as each key is unique).

EDIT: Sorry, realised you wanted to add it to a specific position. My bad. You could use a SortedDictionary but this still won't let you insert.

You could use an OrderedDictionary, but I would question why you would want to do that.

Use a linked list. It was designed for this exact situation.
If you still need the dictionary O(1) lookups, use both a dictionary and a linked list.

Hashtables are not inherently sorted, your best bet is to use another structure such as a SortedList or an ArrayList