# 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<Character, HashMap> root;
private final Character END_CHARACTER = '$'; public Trie() { initializeRoot(); } public Trie(String s) { initializeRoot(); add(s); } public Trie(Collection<String> collection) { initializeRoot(); for (String s : collection) { add(s); } } private void initializeRoot() { root = new HashMap<>(); } public void add(String s) { HashMap<Character, HashMap> node = root; for (int i = 0; i < s.length(); i++) { Character character = s.charAt(i); if (!node.containsKey(character)) { node.put(character, new HashMap<Character, HashMap>()); } node = node.get(character); } node.put(END_CHARACTER, new HashMap<>()); } public boolean contains(String s) { HashMap<Character, HashMap> node = root; for (int i = 0; i < s.length(); i++) { Character character = s.charAt(i); if (node.containsKey(character)) { node = node.get(character); } else { return false; } } return node.containsKey(END_CHARACTER); } }  ## 2 Answers Initializing private HashMap<Character, HashMap> root; at declaration will simplify your code public class Trie { private HashMap<Character, HashMap> root = new HashMap<>(); private final Character END_CHARACTER = '$';

public Trie() {}

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

public Trie(Collection<String> collection) {
for (String s : collection) {
add(s);
}
}

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

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


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<Character, HashMap> root = new HashMap<>();
private final Character END_CHARACTER = '$'; public Trie() {} public Trie(String s) { internalAdd(s); } public Trie(Collection<String> collection) { for (String s : collection) { internalAdd(s); } } public void add(String s) { internalAdd(s); } private void internalAdd(String s) { HashMap<Character, HashMap> node = root; for (int i = 0; i < s.length(); i++) { Character character = s.charAt(i); if (!node.containsKey(character)) { node.put(character, new HashMap<Character, HashMap>()); } node = node.get(character); } node.put(END_CHARACTER, new HashMap<>()); } public boolean contains(String s) { HashMap<Character, HashMap> node = root; for (int i = 0; i < 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<Character, HashMap> node = root; for (int i = 0; i < s.length(); i++) { Character character = s.charAt(i); if (!node.containsKey(character)) { node.put(character, new HashMap<Character, HashMap>()); } node = node.get(character); } node.put(END_CHARACTER, new HashMap<>()); }  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<Character, HashMap> node) { for (int i = 0; i < s.length(); i++) { Character character = s.charAt(i); node.put(character, new HashMap<>()); node = node.get(character); } }  and call it private void internalAdd(String s) { HashMap<Character, HashMap> node = root; for (int i = 0; i < 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<>()); }  But wait, we can do even better, as node.isEmpty() should also be used in the contains() method public boolean contains(String s) { HashMap<Character, HashMap> node = root; for (int i = 0; i < 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<Character, HashMap> root = new HashMap<>(); private final Character END_CHARACTER = '$';

public Trie() {
}

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

public Trie(final Collection<String> collection) {
for (String s : collection) {
internalAdd(s);
}
}

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

private void internalAdd(final String s) {
Map<Character, HashMap> node = root;

for (int i = 0; i < 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<>());
}

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

public boolean contains(final String s) {
Map<Character, HashMap> node = root;

for (int i = 0; i < 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);
}
}

• I agree on the first point. But for the second, we have a problem with the 2nd iteration of the loop - root.get(character) will stay at the "top level". That's what we have the "node" element (i.e. the current node).
– Ryan
Aug 7 '14 at 15:38
• Ahhh, I thought (in my mind only) that there is a break out of the loop. Will remove this part. Aug 7 '14 at 15:43

Use interface types instead of implementations. Instead of:

HashMap<Character, HashMap> node = new HashMap<>();


Do like this:

Map<Character, HashMap> node = new HashMap<>();


Immutable things are good. If you can make member variables final, make them final:

private final Map<Character, HashMap> root = new HashMap<>();


After this step, the constructor without arguments becomes completely pointless, so you can remove it.

class Trie {
private final Map<Character, HashMap> root = new HashMap<>();
private final Character END_CHARACTER = '\$';

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

public Trie(Collection<String> collection) {
for (String s : collection) {
add(s);
}
}

// ...
}

• I think the parameterless constructor should be kept so one can also create a instance without a String/Collection<String> and later on call one of the add() methods Aug 8 '14 at 5:31
• If there is a real and legitimate use case, then sure, you'll have no choice but add it. Otherwise don't speculate: if you don't need it right now then omit it. Aug 8 '14 at 7:24