It sounds more like you're using it as an array then. Maybe you should use the Queue instead.

If you need both insertion order access and random access by key you will have to store a separate array that keeps track of the order that keys were inserted.