3 ms·
I will argue that a properly implemented tries are more compact but not necessarily faster than hash table. The fact is, there are some badly implemented tries
by liuliu 17y ago
I will argue that a properly implemented tries are more compact but not necessarily faster than hash table. The fact is, there are some badly implemented tries which even worse than hash table in term of memory consumption. Also, I'd like to point out the actually trie implementation may not have a fix k child node. I most often use k = 256 or 512 for the first few layers and 4~8 for the last few one in order to get "hash table" like performance for the first few layers and "tree" like performance for a deeper lookup.
- mhansen 17y agoI will argue that a properly implemented tries are more compact but not necessarily faster than hash table. Where do you argue this? The fact is, there are some badly implemented tries which even worse than hash table in term of memory consumption. Any data structure can be badly implemented. What use is comparing a badly implemented data structure to a well-implemented one?
- liuliu 17y agoIt seems in the article the author suggests that in certain case tries is faster than hash table. Yes, you are right about every data structure can be badly implemented. But some data structures are more easily to get wrong. For example, everyone have no problem with selection sort, it is just hard to get it wrong. But for binary search, some decent programmer may write (a + b) / 2. Same case for tries, people more commonly (intuitively) write things like node_t* child[26];