Java Trie Implementation I am creating a Trie class in Java, and am wondering what else can be done to make it even better. I am hoping to add concurrency to speed querying up.

public class Trie {
    private HashMap&lt;Character, HashMap&gt; root;
    private final Character END_CHARACTER = '$';

    public Trie() {
        initializeRoot();
    }

    public Trie(String s) {
        initializeRoot();
        add(s);
    }

    public Trie(Collection&lt;String&gt; collection) {
        initializeRoot();
        for (String s : collection) {
            add(s);
        }
    }

    private void initializeRoot() {
        root = new HashMap&lt;&gt;();
    }

    public void add(String s) {
        HashMap&lt;Character, HashMap&gt; node = root;
        for (int i = 0; i &lt; s.length(); i++) {
            Character character = s.charAt(i);
            if (!node.containsKey(character)) {
                node.put(character, new HashMap&lt;Character, HashMap&gt;());
            }
            node = node.get(character);
        }
        node.put(END_CHARACTER, new HashMap&lt;&gt;());
    }

    public boolean contains(String s) {
        HashMap&lt;Character, HashMap&gt; node = root;
        for (int i = 0; i &lt; s.length(); i++) {
            Character character = s.charAt(i);
            if (node.containsKey(character)) {
                node = node.get(character);
            } else {
                return false;
            }
        }
        return node.containsKey(END_CHARACTER);
    }
}
Initializing private HashMap&lt;Character, HashMap&gt; root; at declaration will simplify your code

public class Trie {
    private HashMap&lt;Character, HashMap&gt; root = new HashMap&lt;&gt;();
    private final Character END_CHARACTER = '$';

    public Trie() {}

    public Trie(String s) {
        add(s);
    }

    public Trie(Collection&lt;String&gt; collection) {
        for (String s : collection) {
            add(s);
        }
    }

    public void add(String s) {
        HashMap&lt;Character, HashMap&gt; node = root;
        for (int i = 0; i &lt; s.length(); i++) {
            Character character = s.charAt(i);
            if (!node.containsKey(character)) {
                node.put(character, new HashMap&lt;Character, HashMap&gt;());
            }
            node = node.get(character);
        }
        node.put(END_CHARACTER, new HashMap&lt;&gt;());
    }

    public boolean contains(String s) {
        HashMap&lt;Character, HashMap&gt; node = root;
        for (int i = 0; i &lt; s.length(); i++) {
            Character character = s.charAt(i);
            if (node.containsKey(character)) {
                node = node.get(character);
            } else {
                return false;
            }
        }
        return node.containsKey(END_CHARACTER);
    }
}


From whats-wrong-with-overridable-method-calls-in-constructors  


  Simply put, this is wrong because it unnecessarily opens up possibilities to MANY bugs. When the @Override is invoked, the state of the object may be inconsistent and/or incomplete.


This having in mind we will refactor the class, to add a private internalAdd() method which we call from the constructor and the public add() methods

public class Trie {
    private HashMap&lt;Character, HashMap&gt; root = new HashMap&lt;&gt;();
    private final Character END_CHARACTER = '$';

    public Trie() {}

    public Trie(String s) {
        internalAdd(s);
    }

    public Trie(Collection&lt;String&gt; collection) {
        for (String s : collection) {
            internalAdd(s);
        }
    }

    public void add(String s) {
        internalAdd(s);
    }

    private void internalAdd(String s) {
        HashMap&lt;Character, HashMap&gt; node = root;
        for (int i = 0; i &lt; s.length(); i++) {
            Character character = s.charAt(i);
            if (!node.containsKey(character)) {
                node.put(character, new HashMap&lt;Character, HashMap&gt;());
            }
            node = node.get(character);
        }
        node.put(END_CHARACTER, new HashMap&lt;&gt;());
    }

    public boolean contains(String s) {
        HashMap&lt;Character, HashMap&gt; node = root;
        for (int i = 0; i &lt; s.length(); i++) {
            Character character = s.charAt(i);
            if (node.containsKey(character)) {
                node = node.get(character);
            } else {
                return false;
            }
        }
        return node.containsKey(END_CHARACTER);
    }
}


but we can do better.. let us take a look at internalAdd()  


private void internalAdd(String s) {
    HashMap&lt;Character, HashMap&gt; node = root;
    for (int i = 0; i &lt; s.length(); i++) {
        Character character = s.charAt(i);
        if (!node.containsKey(character)) {
            node.put(character, new HashMap&lt;Character, HashMap&gt;());
        }
        node = node.get(character);
    }
    node.put(END_CHARACTER, new HashMap&lt;&gt;());
}



If node.isEmpty() we won't need to check if (!node.containsKey(character)) anymore.
Also if (!node.containsKey(character)) evaluates one time to true, we won't need to check this anymore. Let us add a new method:  

private void internalAdd(String s, HashMap&lt;Character, HashMap&gt; node) {
    for (int i = 0; i &lt; s.length(); i++) {
        Character character = s.charAt(i);
        node.put(character, new HashMap&lt;&gt;());
        node = node.get(character);
    }
}


and call it  

private void internalAdd(String s) {
    HashMap&lt;Character, HashMap&gt; node = root;
    for (int i = 0; i &lt; s.length(); i++) {
        Character character = s.charAt(i);
        if (node.isEmpty() || !node.containsKey(character)) {
            internalAdd(s.substring(i), node);
            break;
        }
        node = node.get(character);
    }
    node.put(END_CHARACTER, new HashMap&lt;&gt;());
}


But wait, we can do even better, as node.isEmpty() should also be used in the contains() method  

public boolean contains(String s) {
    HashMap&lt;Character, HashMap&gt; node = root;
    for (int i = 0; i &lt; s.length(); i++) {
        if(node.isEmpty()){
            return false;
        }
        Character character = s.charAt(i);
        if (node.containsKey(character)) {
            node = node.get(character);
        } else {
            return false;
        }
    }
    return node.containsKey(END_CHARACTER);
}


Finished ? No, we still can do better. As the passed String parameters won't be changed, let us make them final the same is true for the root field. Also as janos has answered


  use interface types instead of the implementation   


Putting altogether

public class Trie {

    private final Map&lt;Character, HashMap&gt; root = new HashMap&lt;&gt;();
    private final Character END_CHARACTER = '$';

    public Trie() {
    }

    public Trie(final String s) {
        internalAdd(s);
    }

    public Trie(final Collection&lt;String&gt; collection) {
        for (String s : collection) {
            internalAdd(s);
        }
    }

    public void add(final String s) {
        internalAdd(s);
    }

    private void internalAdd(final String s) {
        Map&lt;Character, HashMap&gt; node = root;

        for (int i = 0; i &lt; s.length(); i++) {
            Character character = s.charAt(i);
            if (node.isEmpty() || !node.containsKey(character)) {
                internalAdd(s.substring(i), node);
                break;
            }
            node = node.get(character);
        }
        node.put(END_CHARACTER, new HashMap&lt;&gt;());
    }

    private void internalAdd(final String s, Map&lt;Character, HashMap&gt; node) {
        for (int i = 0; i &lt; s.length(); i++) {
            Character character = s.charAt(i);
            node.put(character, new HashMap&lt;&gt;());
            node = node.get(character);
        }
    }

    public boolean contains(final String s) {
        Map&lt;Character, HashMap&gt; node = root;

        for (int i = 0; i &lt; s.length(); i++) {
            if (node.isEmpty()) {
                return false;
            }
            Character character = s.charAt(i);
            if (node.containsKey(character)) {
                node = node.get(character);
            } else {
                return false;
            }
        }
        return node.containsKey(END_CHARACTER);
    }
}