Java Tree: HashMap and Strings Example

This Java example implements a tree that can be used to store and look up strings. It can be optimized to 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.
© 2007-2019 Sam Allen. Every person is special and unique. Send bug reports to info@dotnetperls.com.
HomeSearch
Home
Dot Net Perls