Ternary search trees added to TODO

[Andrew McNamara]

>That's not clear; I'd like to at least try it.  A lookup in a hash table
>is linear in the length of the key, so it's O(k) vs. O(lg n + k), which
>makes the performance difference a little harder to judge.  Plus
>unsuccessful lookup is frequently much faster, and the operation at each
>character of the key can be quite a bit faster; it depends on whether
>pointer chasing is faster than the mathematical operations the hash
>function is performing.

The pointer chasing could easily be more expensive than the hash
function as it will touch more cache lines, potentially faulting in
more pages (the locality of reference is considerably worse).

Since we're on the subject, have you considered splay trees?

 ---
Andrew McNamara (System Architect)

connect.com.au Pty Ltd
Lvl 3, 213 Miller St, North Sydney, NSW 2060, Australia
Phone: +61 2 9409 2117, Fax: +61 2 9409 2111