Re:Coding tricks I learnt at Apple
by geocar on Saturday June 11, 2011 @02:31PM
(#2644484)
Only if you neglect hashing time (significant with perfect hashes) and comparison-time. That makes them O(k), not O(1). It is helpful to me to think of hashing as expensive as copying.
Radix tries on the other hand don't hash. They're always at least O(k), and you can find the next and previous values (lexicographically) in O(k) as well. They're also more compact and you never have to resize your tables.
Radix tries on the other hand don't hash. They're always at least O(k), and you can find the next and previous values (lexicographically) in O(k) as well. They're also more compact and you never have to resize your tables.