{}.pop() sounds like the right thing given its symmetry with [].pop().
It would have the semantics that it would remove and return a random /item/ from the dictionary, which the implementation can make the "first" item for convenience purposes.
It shouldn't dictate though, that {}.pop() == dict.items().pop() or make any other guarantees about which item gets popped, because other implementations (or indeed, other mapping-conformant objects) may use different underlying representations that could make this inefficient.
For added symmetry, {}.pop() should take an optional argument which is the key of the item to remove and return.
That seems a nice touch, until you realize that [].pop() returns the value, while {}.pop() returns a (key, value) pair. Also: if you already know the key, the argument that you can't do it in O(1) time is no longer valid. So, a -0.5. One more concern: if you repeatedly remove the *first* item, the hash table will start looking lobsided. Since we don't resize the hash table on deletes, maybe picking an item at random (but not using an expensive random generator!) would be better. --Guido van Rossum (home page: http://www.python.org/~guido/)