Use OrderedDicts: http://docs.python.org/2/library/collections.html#collections.OrderedDict
>>> x = OrderedDict((("a", "1"), ("c", '3'), ("b", "2")))
>>> x["d"] = 4
>>> x.keys().index("d")
3
>>> x.keys().index("c")
1
For those using Python 3
>>> list(x.keys()).index("c")
1