See Objects/dictnotes.txt for some of the results.
I spent about full month trying to optimize dict
performance either by tuning parameters or using
different algorithms.

There were a couple wins that were not implemented.
1) Allowing users to control insertion order or
at least specify which keys are frequently accessed
so that we could assure a first-time hit.
2) Allowing users to pre-size a dictionary so that
resizes wouldn't be needed or an so they could control
density.
Guido didn't want to expose these controls.

The PyPy guys published a paper on their results with
alternative dict implementations and specialized dicts.
You might want to look at that.  IIRC, they found only
minor wins.