Choosing the Right Container

You need a container that supports O(1) average lookup by key, maintains insertion order, and allows O(1) removal by key. Which approach works?