The Trie - A powerful data structure

[giscus[bot]]

The Trie - A powerful data structure

A Trie is a common data structure used for example for auto completing words. We will discover how to built our own Trie and check how fast he competes against a "normal" Hashset.
Also we will build a TypeAHead input component which automatically offers us some suggestion based on our input. Of course, we will use our newly created Trie.

https://steven-giesel.com/blogPost/3b5e865d-0c84-4d82-a981-d8fac1772419

[miroslavp]

Hi Steven,
Your implementation of FindOneInHashSet does not really test HashSet capabilities. The Any() method is an extension method of IEnumerable, the complexity of which is O(n). If you really want to test how fast the HashSet is, you should use Contains() method instead (it is O(1)). The performance should be very similar to the Trie or it might be even faster

[linkdotnet]

Hey @miroslavp ,

thanks for the comment and you are absolutely right - I missed that completely and as you said, it will equalize both structures. Or even, as you said, the HashSet would win here, as it is constant time (on average).

The Trie might have something around O(k) where k is the average length of all strings in the trie itself.