Метод HashMap.get (), возвращающий ноль, даже если элемент присутствует в HashMap

Question

Я знаю, что есть несколько вопросов с почти таким же названием, как у меня, но я рассмотрел все из них, и их решения не применимы к моему делу. Я реализую Trie в Java, и основной Trie класс имеет HashMap сопоставление TrieNode с LinkedList, напоминающее сопоставление родительского узла его дочерним элементам, а другой HashMap отображение LinkedList на TrieNode, чтобы получить родительский узел с дочерними элементами. Однако в методе insert(String s) отображение HashMap LinkedList на TrieNode создает пустой указатель, когда я пытаюсь использовать метод get(). Я изучил эту проблему с помощью отладчика, но в отладчике было указано, что LinkedList присутствует. Вот мой код:

Основной класс тестирования:

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.
}

Класс Trie:

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.
    }
}

Класс TrieNode:

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

}

Ошибка возникает при попытке вставить «ab c». В классе Trie я попытался напечатать «Found», если HashMap содержал ключ, когда заданная строка «ab c», и, как ни странно, это так. Таким образом, метод HashMap keySet() содержит правильный ключ, но он возвращает ноль, когда я вызываю метод get()? Может кто-нибудь узнать, что происходит?

Answer 1

Вы используете LinkedList в качестве ключа для HashMap, и вы мутантно говорите LinkedList: возможно, поэтому вы находите ключ, используя keySet(), а не Map.get(Object):

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

В качестве примера:

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

Причина довольно проста:

• HashMap используйте hashCode(), чтобы найти корзину, в которую нужно поместить значение , Изменение содержания List сродни изменению hashCode().
• HashMap, затем используйте equals(), чтобы найти эквивалентный ключ. Изменение содержимого списка приводит к тому же результату.

Answer 2

Вам необходимо внести два изменения в свой код:

A.

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

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

    root = new TrieNode(' '); // Create a new object
    list = new LinkedList<>(); // Create a new object
    nodes = new HashMap<>();
    nodes.put(list, root);
}

B.

if (nodes != null && nodes.get(children) != null) // Check for null
    nodes.get(children).count++;

Не стесняйтесь комментировать в случае каких-либо сомнений / проблем.