[issue44555] Dictionary operations are LINEAR for any dictionary (for a particular code).

[Raymond Hettinger]

Raymond Hettinger <raymond.hettinger at gmail.com> added the comment:

> I still disagree with this design since it's not 
> how a person using a hash map expects it to behave.

All mapping data structures have tradeoffs.  For the core dict type, we chose a structure that benefits most Python users most of the time.  If a user expects that the core dict type magically handles all cases optimally, that is a bug in their expectation, not a bug in Python.  

For the atypical pattern shown in slow_dictionary(), we recommend choosing a different data structure such as an OrderedDict or simply storing the keys in a deque.  This isn't a blow-off answer -- the stated goal of the collections module is to offer "specialized container datatypes providing alternatives to Python’s general purpose built-in containers, dict, list, set, and tuple."  Those alternatives have different performance characteristics that may better serve particular access patterns.

Thanks for the suggestion, but this is not a bug.  It is an intentional design decision.  Changing the dict implementation to a linked list would make your case perform better but would make most users worse off.

----------
resolution:  -> not a bug
stage:  -> resolved
status: open -> closed

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue44555>
_______________________________________