8
\$\begingroup\$

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);
    }
}
\$\endgroup\$
1

2 Answers 2

Reset to default
7
\$\begingroup\$

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);
    }
}

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<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);
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ 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). \$\endgroup\$
    – Ryan Dougherty
    Commented Aug 7, 2014 at 15:38
  • \$\begingroup\$ Ahhh, I thought (in my mind only) that there is a break out of the loop. Will remove this part. \$\endgroup\$
    – Heslacher
    Commented Aug 7, 2014 at 15:43
2
\$\begingroup\$

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);
        }
    }

    // ...
}
\$\endgroup\$
2
  • \$\begingroup\$ 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 \$\endgroup\$
    – Heslacher
    Commented Aug 8, 2014 at 5:31
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – janos
    Commented Aug 8, 2014 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.