java - 使用尝试在 HashMap 中递归查找单词

Question

我的方法应该将关联的键/值对添加到特里树中，如果该键已经在特里树中，则应该更新该值。然而我不太确定我做错了什么，这是我第一次使用尝试。 所以我目前正在研究我的 put 方法，我有以下内容:

public void put(TrieMapNode current, String curKey, String value){
if(current.getChildren().containsKey(curKey))
      value = current.get(key);
      curKey =value;

  put(current.getChildren().get(curKey), curKey, value);

}

任何帮助将不胜感激，谢谢!

Answer 1

在您当前的实现中，您不会从 trie 的优点中受益。这是因为在根节点，遇到的每个字符串都有一个子节点。
这不是构建 trie 的方式。 trie 的每个节点每个字符最多可以有一个子节点(形成字符串的元素)。
所以你的方法应该看起来更像下面这样:

public void put(TrieMapNode current, String key, String value, int depth){
if (depth == key.length()){
   current.value = value;
} else {
    char curChar = key.charAt(depth);
    if(!current.getChildren().containsKey(curChar)){
        TrieMapNode newNode = new TrieMapNode();
        current.getChildren().put(curChar, newNode);
    }
    put(current.getChildren().get(curChar), curKey, value, depth + 1);
}

您犯的主要错误是在特里树中插入/更新时将 key 视为一个整体。这将导致根节点对于映射中的每个键都有一个子节点(因此有大量子节点)，但深度非常有限(根节点、其子节点，仅此而已)。

在我向您建议的实现中，一个节点的每个可能的字符都有一个子节点(一个有界的数字，26、52，无论如何都是一个很小且有界的数字)。
而且它的深度不限于1，因为正如您在else block 中看到的那样，如果我们要查找的节点不存在，我们就会创建一个节点(当您开始时，您只有一个根节点，因此您需要计划创建新节点的情况)，并且我们还会对当前节点的子节点递归调用put。因此该值将存储在等于其键长度的深度。