String Interning – Trie vs. Hash Table Deathmatch

Re:String Interning – Trie vs. Hash Table Deathmatch by kryps on Monday June 29, 2015 @06:22PM (#9801560)

For critbit trees the entire string _up to_ the critical bit where the string differs from all others already in the datastructure needs to be scanned.

critbit trees degenerate badly if you store strings and their prefixes, e.g. storing a, aa, aaa, ...

[ Parent | on HN ]

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.

[ Parent | on HN ]