11 ms·
Why is a trie obviously better then a hash map?
by sorokod 10y ago
Why is a trie obviously better then a hash map?
- teraflop 10y agoA hash map doesn't solve the same problem. Given a collection of routes, you need to find the longest one which is a prefix of the given URL.
- jeremiep 10y agoThey allow you to match the URL in a series of steps. Where each step can be static (ie "/foo") or dynamic (ie /images/). You can then easily add features to this structure, like route middlewares at every level in the tree; just apply them while doing the routing. This also allows you to match route variants easily, ie "foo" and "foo/" are the same, so are "/" and "/index.html". In the same way you can extract query parameters for middleware/handler use.
- mstade 10y agoAlso, tries means it's trivial to do detect routing ambiguities, so your routing table doesn't necessarily have to be built up front, or in any particular order. This is particularly powerful when you're developing an application with a team distributed both over space and time.
- SEJeff 10y agoFixed lookup time. A trie (aka radix tree) 3 levels deep with 1 million entries has the same lookup time as a 3 level deep trie with 5 entries.
- zbobet2012 10y agoA trie is O(k), where k is the length of the key on inserts and deletes. Generally, any hashing algorithm is also O(k) with the additional overhead of the lookup in the table. This also ignores that most hashes have only amortized O(1) inserts. A trie usually also exhibits better memory locality and caching behavior. Also, a trie (like most tree data structures) can be implemented in a lock-free format fairly easily.
- buckhx 10y agoA trie can efficiently match all routes that start with a prefix. With a hashmap you wouldn't be off any better than a list efficiency wise.