> > > It depends on the problem. A dictionary is a hash table. An ordered > dictionary is a binary search tree (BST). Those are different data > structures. > > The main things to note is that: > > - Access is best-case O(1) for the hash table and O(log n) for the > BST. > > - Worst case behavior is for access is O(n) for both. The pathologic > conditions are excessive collisions (hash) or an unbalanced tree > (BST). In pathologic cases they both converge towards a linked list. > > - Searches are only meaningful for == and != for a hash table, but BST > searches are also meaningful for >, <, <=, and >=. For this reason, > databases are often implemented as BSTs. > > - A BST can be more friendly to cache than a hash table, particularly > when they are large. (Remember that O(1) can be slower than O(log n). > Big-O only says how run-time scales with n.) > > Thanks, this was really insightful :)
-- http://mail.python.org/mailman/listinfo/python-list
