Wiem, że jest kilka pytań o prawie takim samym tytule jak mój, ale przyjrzałem się wszystkim i ich rozwiązania nie dotyczą mojego przypadku. Implementuję Trie w Java, a główna klasa Trie ma HashMap mapowanie TrieNode na LinkedList, przypominające mapowanie węzła nadrzędnego na jego dzieci i inne HashMap mapowanie LinkedList na TrieNode, aby uzyskać węzeł nadrzędny z dziećmi. Jednak w metodzie insert(String s) mapowanie HashMap LinkedList na TrieNode generuje zerowy wskaźnik, gdy próbuję użyć {{X13} } metoda. Przyjrzałem się temu problemowi za pomocą debuggera, ale w debugerze stwierdzono, że LinkedList jest obecny. Oto mój kod:

Główna klasa testowa:

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

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

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

}

Błąd pojawia się, gdy próbuję wstawić „abc”. W klasie Trie próbowałem wydrukować „Znaleziono”, jeśli HashMap zawierał klucz, gdy dany ciąg to „abc”, i o dziwo, tak się stało. Więc metoda HashMap keySet() zawiera poprawny klucz, ale zwraca wartość null, kiedy wywołuję metodę get()? Czy ktoś może dowiedzieć się, co się dzieje?

2
user12447991 21 marzec 2020, 00:40

2 odpowiedzi

Najlepsza odpowiedź

Używasz LinkedList jako klucza do HashMap i mutujesz powiedziane LinkedList: prawdopodobnie dlatego znajdujesz klucz używając keySet(), a nie {{X4 }}:

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

Jako przykład:

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

Powód jest dość prosty:

  • HashMap użyj hashCode(), aby znaleźć przedział, w którym należy umieścić wartość. Zmiana treści List jest podobna do zmiany hashCode().
  • HashMap następnie użyj equals(), aby znaleźć równoważny klucz. Zmiana zawartości listy daje ten sam rezultat.
4
NoDataFound 20 marzec 2020, 22:11

Musisz wprowadzić dwie zmiany w swoim kodzie:

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++;

Zapraszam do komentowania w przypadku jakichkolwiek wątpliwości / problemów.

0
Arvind Kumar Avinash 20 marzec 2020, 22:07