Re:String Interning – Trie vs. Hash Table Deathmatch
by beagle3 on Monday June 29, 2015 @11:56PM
(#9802855)
True, but that's not worse than "standard" tries, and big O()-wise, not even worse than hashing - you do have to scan through the string to hash it.
Worst case data for a critbit tree is also worst case for any other kind of trie, and better than worst case for a classic hash (which is O(items in table) and can often be triggered by an adversary). Constants are different, though.
Worst case data for a critbit tree is also worst case for any other kind of trie, and better than worst case for a classic hash (which is O(items in table) and can often be triggered by an adversary). Constants are different, though.