Editing Trie (section)

=== Replacement for hash tables ===
A trie can be used to replace a [[hash table]], over which it has the following advantages:{{r|reema18|p=358}}
* Searching for a node with an associated key of size <math>m</math> has the complexity of <math>O(m)</math>, whereas an imperfect hash function may have numerous colliding keys, and the worst-case lookup speed of such a table would be <math>O(N)</math>, where <math>N</math> denotes the total number of nodes within the table.
* Tries do not need a hash function for the operation, unlike a hash table; there are also no [[hash collision|collisions]] of different keys in a trie.
* Buckets in a trie, which are analogous to hash table buckets that store key collisions, are necessary only if a single key is associated with more than one value.
* String keys within the trie can be sorted using a predetermined alphabetical ordering.

However, tries are less efficient than a hash table when the data is directly accessed on a [[Computer data storage#Secondary storage|secondary storage device]] such as a hard disk drive that has higher [[random access]] time than the [[main memory]].<ref name="triememory">{{cite journal | author=Edward Fredkin| author-link=Edward Fredkin| title=Trie Memory| journal=Communications of the ACM| year=1960| volume=3| issue=9| pages=490–499| doi=10.1145/367390.367400 | s2cid=15384533| doi-access=free}}</ref> Tries are also disadvantageous when the key value cannot be easily represented as string, such as [[floating point numbers]] where multiple representations are possible (e.g. 1 is equivalent to 1.0, +1.0, 1.00, etc.),{{r|reema18|p=359}} however it can be unambiguously represented as a [[binary number]] in [[IEEE 754]], in comparison to [[two's complement]] format.<ref>{{cite web|publisher=Department of Mathematics and Computer Science, [[Emory University]]|title=The IEEE 754 Format|url=http://mathcenter.oxford.emory.edu/site/cs170/ieee754/|access-date=17 April 2022|author1=S. Orley|author2=J. Mathews|url-status=live|archive-date=28 March 2022|archive-url=https://web.archive.org/web/20220328093853/http://mathcenter.oxford.emory.edu/site/cs170/ieee754/}}</ref>