Dan Stromberg <drsali...@gmail.com>: > On Sun, Mar 9, 2014 at 2:43 PM, Marko Rauhamaa <ma...@pacujo.net> wrote: >>>> There is no O(1) hash table. > [...] > > it's still amortized O(1).
So we are in perfect agreement. Hash tables are a useful family of techniques but involve quite a bit of cost/benefit heuristics. You can only claim O(1) if your hash table is at least as large as the number of elements. As for comparing them with balanced trees, I think one of the main advantages hash tables have is better CPU cache performance. A tree involves much more jumping around the RAM than a hash table. Still, trees have many things going for them: * no need to find a good hashing function * no need to spend time on calculating the hash value * no need to find optimal hash table sizes -- no costly resizing And of course, the main point: * trees are ordered Note that most key comparisons tend to be very quick as you don't need to traverse the whole key to locate the element. Also, it is hard to say if going O(log n) levels deep in the tree is slower than calculating the hash value, although, as I said, the latter operation tends to benefit from a cache locality. Trees are also crucial when you don't have exact matches, but for example, when you are looking for prefix or wild-card matches. Marko -- https://mail.python.org/mailman/listinfo/python-list
