Java Tree: HashMap and Strings Example

Implement a tree that can be used to store and look up strings. Quickly search strings.

Tree. A tree stores nodes. Each node can reference other nodes—these are child nodes. In Java we can develop a simple tree to store many strings.

With this method, we store a HashMap on each node. This map points to child nodes. To traverse the tree, we access elements in the HashMap.

Example program. This program is simple. We first see the TreeNode class—this contains the children node (in a HashMap). We also have get and add() methods.

Program: In the Program class we have an addWord and an exists() method. These handle strings and manipulate the tree.

AddWord: This loops over all the characters in the String. It calls add() on each letter to add nodes.

charAt

Exists: This method tests the tree to see if a string exists in it. The result is a boolean.

Java program that implements tree import java.util.HashMap; class TreeNode { boolean word; HashMap<Character, TreeNode> children = new HashMap<>(); public TreeNode get(char value) { // Get anode from the HashMap. return children.getOrDefault(value, null); } public TreeNode add(char value, TreeNode node) { // Add a node if one does not yet exists. // ... Return the matching node. children.putIfAbsent(value, node); return get(value); } } public class Program { static TreeNode root = new TreeNode(); static void addWord(String value) { // Add all characters from the string to the tree. TreeNode node = root; for (int i = 0; i < value.length(); i++) { node = node.add(value.charAt(i), node); } node.word = true; } static boolean exists(String value) { // See if a word exists in the tree. TreeNode node = root; for (int i = 0; i < value.length(); i++) { node = node.get(value.charAt(i)); if (node == null) { return false; } } return node.word; } public static void main(String[] args) { // Add three words to the tree. addWord("cat"); addWord("bird"); addWord("dog"); // These three words should exist. boolean exists1 = exists("cat"); boolean exists2 = exists("bird"); boolean exists3 = exists("dog"); System.out.println(exists1); System.out.println(exists2); System.out.println(exists3); // These words do not exist. exists1 = exists("fish"); exists2 = exists("123456"); exists3 = exists("turnip"); System.out.println(exists1); System.out.println(exists2); System.out.println(exists3); } } Output true true true false false false

Tests. In the main() method we test the tree with the addWord and exists() methods. We add three strings—exists returns true on these strings.

And: The exists() method fortunately returns false on the strings we did not add to the tree.

Some performance issues. A tree like this one can be used to optimize string lookups. This can implement a Scrabble or anagram program.

However: The implementation here is not perfect. The HashMap could be changed to an array of TreeNode references.

And: With an array, we could lazily allocate the array to save memory. We could use a lookup method to match chars to indexes.

In my experience, an optimized form of this tree can be used to vastly improve word lookups. This style of tree, similar to a "directed acyclic word graph," is a clear performance win.

Note: For word lists, a tree can share nodes at the ends of words (suffixes). This is not available in this simple program.

And: A custom lookup method, which may be recursive, can encode many restrictions in which nodes to traverse.

Recursion

A review. Trees (tries) are powerful. In the field of artificial intelligence, nodes represent search steps. And traversing a tree is a performance challenge.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

Java Tree: HashMap and Strings Example

Related Links:

.Net

Java

Related Links