There are ordered hash tables. Knuth did some work with them. You can also have a parallel array with the order information.