Java Program to Implement Hash Trie

This is a Java Program to implement Hash Trie. A trie is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node, instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest.

Here is the source code of the Java program to implement Hash Trie. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  *   Java Program to Implement Hash Trie
  3.  **/
  4.  
  5. import java.io.*;
  6. import java.util.*;
  7.  
  8. class HashTrie
  9. {
  10.     private HashMap<Character, HashMap> root;
  11.  
  12.     /** Constructor **/
  13.     public HashTrie() 
  14.     {
  15.        root = new HashMap<Character, HashMap>();
  16.     }
  17.     /** Parameterised Constructor **/
  18.     public HashTrie(String[] arr) 
  19.     {
  20.         root = new HashMap<Character, HashMap>();
  21.         for (String s: arr)
  22.             add(s);
  23.     }
  24.  
  25.     /** Function to add a string to hash trie **/
  26.     public void add(String str) 
  27.     {
  28.         HashMap<Character, HashMap> node = root;
  29.         for (int i = 0; i < str.length(); i++)
  30.         {
  31.             if (node.containsKey(str.charAt(i)))
  32.                 node = node.get(str.charAt(i));
  33.             else 
  34.             {
  35.                 node.put(str.charAt(i), new HashMap<Character, HashMap>());
  36.                 node = node.get(str.charAt(i));
  37.             }
  38.         }
  39.         /** end of string **/
  40.         node.put('\0', new HashMap<Character, HashMap>(0)); 
  41.     }
  42.  
  43.     /** Function to check if hash trie contains a given word **/
  44.     public boolean contains(String str) 
  45.     {
  46.         HashMap<Character, HashMap> currentNode = root;
  47.         for (int i = 0; i < str.length(); i++)
  48.         {
  49.             if (currentNode.containsKey(str.charAt(i)))
  50.                 currentNode = currentNode.get(str.charAt(i));
  51.             else 
  52.                 return false;
  53.         }        
  54.         return currentNode.containsKey('\0') ? true : false;            
  55.     }
  56. }
  57.  
  58. /** Class HashTrieTest **/
  59. public class HashTrieTest
  60. {
  61.     public static void main(String[] args) throws IOException
  62.     {    
  63.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  64.         /** Accept words **/        
  65.         System.out.println("Trie Test\n");
  66.         System.out.println ("Enter words to be entered into trie");
  67.         String input = br.readLine();
  68.         String[] s = input.split(" ");
  69.         /** Create Trie with accepted words **/
  70.         HashTrie t = new HashTrie(s);
  71.         /** Trie Test **/
  72.         char ch = 'n';
  73.         do
  74.         { 
  75.             System.out.println("\nEnter word to search ");
  76.             String key = br.readLine();
  77.             System.out.println("Search status : "+ t.contains(key));
  78.  
  79.             System.out.println("\nDo you want to continue (Type y or n) \n");
  80.             ch = br.readLine().charAt(0);                        
  81.         } while (ch == 'Y'|| ch == 'y');         
  82.     }
  83. }

Trie Test
 
Enter words to be entered into trie
trie tree test branch leaf root fruit key lock hash
 
Enter word to search
trie
Search status : true
 
Do you want to continue (Type y or n)
 
y
 
Enter word to search
tree
Search status : true
 
Do you want to continue (Type y or n)
 
y
 
Enter word to search
trench
Search status : false
 
Do you want to continue (Type y or n)
 
y
 
Enter word to search
triee
Search status : false
 
Do you want to continue (Type y or n)
 
y
 
Enter word to search
trei
Search status : false
 
Do you want to continue (Type y or n)
 
y
 
Enter word to search
branch
Search status : true
 
Do you want to continue (Type y or n)
 
n

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.