Tim Chase <python.l...@tim.thechases.com> writes: > From an interface perspective, I suppose it would work. However one > of the main computer-science reasons for addressing by a hash is to > get O(1) access to items (modulo pessimal hash structures/algorithms > which can approach O(N) if everything hashes to the same > value/bucket), rather than the O(logN) time you'd get from a tree. So > folks reaching for a hash/map might be surprised if performance > degraded with the size of the contents.
In a language like Python, the difference between O(1) and O(log n) is not the primary reason why programmers use dict; they use it because it's built-in, efficient compared to alternatives, and convenient to use. If Python dict had been originally implemented as a tree, I'm sure it would be just as popular. Omitting the factor of O(log n) as functionally equivalent to O(1) is applicable to many situations and is sometimes called "soft-O" notation. One example from practice is the pre-2011 C++, where the standardization committee failed to standardize hash tables on time for the 1998 standard. Although this was widely recognized as an oversight, a large number of programs simply used tree-based std::maps and never noticed a practical difference between between average-constant-time and logarithmic complexity lookups. -- http://mail.python.org/mailman/listinfo/python-list