What are some main advantages of Tries over Hash Tables

Technology CommunityCategory: Data StructuresWhat are some main advantages of Tries over Hash Tables
VietMX Staff asked 3 years ago

The following are the main advantages of tries over hash tables:

  • Tries support ordered iteration, whereas iteration over a hash table will result in a pseudorandom order given by the hash function (also, the order of hash collisions is implementation defined), which is usually meaningless.
  • Tries facilitate longest-prefix matching, but hashing does not, as a consequence of the above. Performing such a “closest fit” find can, depending on implementation, be as quick as an exact find.
  • Tries tend to be faster on average at insertion than hash tables because hash tables must rebuild their index when it becomes full – a very expensive operation. Tries therefore have much better bounded worst case time costs, which is important for latency sensitive programs.
  • By avoiding the hash function, tries are generally faster than hash tables for small keys like integers and pointers.