Hash is O(1). I am unaware of anything faster.
|
I can explain. For example you have key 256 bytes long.
Let's compare two scenarios, what happens in hashtable and trie.
Hashtable
1. Scan all 256 bytes of key and calculates hash
2. Jump to calculated slot in array
3. Scan all 256 bytes of key again. Check that 256 bytes it's our key (because of collision in ht)
So in hashtable we scan Key at least twice + hash calculation + possible chunks of collision
HArray (Trie)
1. Scan all 256 bytes.
2. Rare branches if there are many keys and our Key path is spitted on two or more paths.
In Trie we scan Key only once.
+ and other aspect - cache of processor
If we have two keys for example: 0000001 and 0000002, in hashtable 000000 bytes will be duplicated for two different keys, but in Trie is no. In Trie in most cases 000000 will be writed once and will be situated in cache. It also increases speed of Trie in compare with Hashtable.
An optimized tree is just a vector with funky access smoke and mirrors and is very fast and allows a lot of tricks under the hood while looking like a tree to the user. The 'pointers' are just indices. But I have no idea how that compares to the trie.
|
You can find on my GitHub page image where I compare functionality of different structures.
https://github.com/Bazist/HArray
These both structures (Tree and Trie) have ordered keys and allow scan it by range