HashMap.get() method returning null even though the element is present in the HashMap

Question

I know there are a few questions with almost the exact same title as mine, but I looked into all of them and their solutions don't apply to my case. I am implementing a Trie in Java, and the main Trie class has a HashMap mapping TrieNode's to LinkedList's, resembling mapping a parent node to it's children, and another HashMap mapping a LinkedList to a TrieNode, to get the parent node with the children. However, in the insert(String s) method, the HashMap mapping LinkedList's to TrieNode's is producing a null pointer when I'm trying to use the get() method. I looked into this issue using the debugger, but in the debugger it said the LinkedList is present. Here is my code:

The main testing class:

public static void main(String[] args) {
    Trie trie = new Trie();
    trie.insert("abcd");
    trie.insert("abce");
    trie.insert("abc"); // When I insert "abc", it gives the error.
}

The Trie class:

public class Trie {

    public HashMap<TrieNode, LinkedList<TrieNode>> children;
    public HashMap<LinkedList<TrieNode>, TrieNode> nodes;

    public Trie() {
        TrieNode root = new TrieNode(' ');
        LinkedList<TrieNode> list = new LinkedList<>();

        children = new HashMap<>();
        children.put(root, list);

        nodes = new HashMap<>();
        nodes.put(list, root);
    }

    public void insert(String word) {
        TrieNode parent = new TrieNode(' ');
        TrieNode curr = null;
        LinkedList<TrieNode> children = this.children.get(parent);
        char[] chars = word.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            curr = new TrieNode(chars[i]);

            if (children.contains(curr)) {
                children = this.children.get(curr);
            } else {
                LinkedList<TrieNode> newList = new LinkedList<>();

                this.children.get(parent).add(curr);
                this.children.put(curr, newList);
                nodes.put(newList, curr);
                children = this.children.get(curr);
            }

            parent = new TrieNode(chars[i]);
        }

        if (word.equals("abc")) {
            for (LinkedList<TrieNode> currList : nodes.keySet()) {
                if (currList.equals(children)) {
                    System.out.println("Found");
                }
            }

            // I did further investigation on why it produces null on when the string "abc" is passed, and strangely enough, in my output it printed "Found".
        }

        nodes.get(children).count++; // This is where the null pointer exception occurs.
    }
}

The TrieNode class:

public class TrieNode {

    public char val;
    public int count;

    public TrieNode(char val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return val + "";
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        TrieNode trieNode = (TrieNode) o;
        return val == trieNode.val;
    }

    @Override
    public int hashCode() {
        return Objects.hash(val);
    }

}

The error occurs when I try inserting "abc". In the Trie class, I tried printing "Found" if the HashMap contained the key when the given string is "abc", and strangely enough, it did. So the HashMap's keySet() method contains the correct key, but it returns null when I call the get() method? Can someone find out what is going on?

Answer 1

You are using a LinkedList as a key to HashMap, and you are mutating said LinkedList: that's probably why you are finding the key using keySet() and not using Map.get(Object):

this.children.get(parent).add(curr);

As an example:

Map<List<String>, String> map = new HashMap<>();
List<String> list = new ArrayList<>();
map.put(list, "a"); 
System.out.println("map.get(" + list + "): " + map.get(list));
list.add("b");
System.out.println("map.get(" + list + "): " + map.get(list)); // may be null

The reason is quite simple:

• HashMap use the hashCode() to find the bucket were to put the value. Changing content of List is akin to changing hashCode().
• HashMap then use the equals() to find the equivalent key. Changing content of list produce the same result.