G'day all. Quoting oleg@pobox.com:
If indeed the read performance is at premium and updates are infrequent, by bother with ternary etc. trees -- why not to use just a single, one-level array. Given a reasonable hash function, the retrieval performance is O(1).
Ah, but key comparison and computing the hash function is _not_ an O(1) operation for keys of non-fixed-size. At the very least, it's O(k) where k is the length of the key. If you have a perfect hash function, and you know that you are not searching for elements which are not in the set, hash searching will take precisely one scan through the whole key. Radix searching, on the other hand, only needs to scan through as much of the key as is necessary to discriminate between them. Plus, even if you need to search for keys which are not in the set, it takes at most one pass through the key, as opposed to at least two for hashing. If constant factors matter, and your keys are appropriately decomposable, I would recommend radix searching over hashing any day. Cheers, Andrew Bromage