Node value:
So far we have seen two searching strategies: the binary search (binary search tree) and hashCode indexed array search (hash table). Binary search find a key in O(logN) time, while hashtable find a key in O(1) time. Binary search tree keeps binary order for fast search, while hashtable introduces randomness for efficient key distribution.
Both binary search tree and hash table store a key in a particular address. When the keys are strings, we got a better strategy to store the key. We break down a key into chars, and store those chars in connected addresses. In order to retrieve a key, we travel across all the storing addresses. This storage delocalize or smear up has a big advantage -- we are less concerned about collision than the hash table does -- many keys can share large portion of their storages. Cloud computing uses the similar sharing strategy.
If the key length is w characters, the cost for a search hit is exam w storage nodes, the search miss is even faster, range from 1 exam to w exam. Statistically, the average search cost is logN/logR, where R (256 for ASCII) is the total number of alphabets.
Trie.java
