插入任意嵌套的HashMap

Question

我想要一个允许我任意嵌套 HashMap 的数据结构。为此，我构建了以下结构：

struct Database {
    children: HashMap<String, Database>,
    data: String,
}

为了插入这个结构，我得到一个键列表和一个要插入的值。例如对于输入

let subkeys = vec!["key1", "key1.1", "key1.1.3"];
let value = "myvalue";

我希望数据库具有以下（伪）结构：

{
    "data" : "",
    "children": {
        "key1": {
            "data" : "",
            "children": {
                "key1.1": {
                    "data" : "",
                    "children" : {
                        "key1.1.3": {
                            "data": "myvalue",
                            "children" : {}
                        }
                    }  
                }
            }
        }
    }   
}

然后例如第二个插入请求

{
    "data" : "",
    "children": {
        "key1": {
            "data" : "",
            "children": {
                "key1.1": {
                    "data" : "",
                    "children" : {
                        "key1.1.3": {
                            "data": "myvalue",
                            "children" : {}
                        }
                    }  
                }
            }
        }
    }   
}

结构应该看起来（伪）像这样：

let subkeys = vec!["key1", "key1.1", "key1.1.2"];
let value = "myvalue2";

所以这是我尝试过的（不起作用） 游乐场的最小可重复示例

{
    "data" : "",
    "children": {
        "key1": {
            "data" : "",
            "children": {
                "key1.1": {
                    "data" : "",
                    "children" : {
                        "key1.1.3": {
                            "data": "myvalue",
                            "children" : {}
                        },
                        "key1.1.2": {
                            "data": "myvalue2",
                            "children" : {}
                        }
                    }  
                }
            }
        }
    }   
}

据我了解，这段代码存在问题：

1. &d.children在 the 之后被删除，match所以root“kind of”没有价值

2. 这root.insert似乎也是一个问题，因为它root是一个&引用，所以它引用的数据不能作为可变的被借用`

我需要做什么才能使我的代码正常工作并产生如上所示的结果。我可能需要改变我的一些东西吗struct Database？

Answer 1

首先，对您到目前为止所拥有的以及为什么它不起作用的一些评论。root需要是一个可变的引用。let mut root = &db.children;请注意可变变量 ( ) 和可变引用 ( )之间的区别let root = &mut db.children;。前者允许更改变量本身。后者允许更改引用背后的数据。在本例中，我们需要两者 ( let mut root = &mut db.children)，因为我们不仅会root在迭代节点时进行更改，而且每当需要插入新节点时也会修改引用后面的数据。

同样的事情也适用于d内部循环（它需要是一个可变变量），尽管我们将看到，变异d并不是我们真正想要的。

// if key doesnt exist add it with a ne empty hashmap
let d = Database{children: HashMap::new(), data: "".to_string()};

// set root to this new databse obejct
root = &mut d.children; 

root.insert(subkey.to_string(), d);

暂时忽略错误，这段代码应该做什么？d是一个新的Database，里面没有真实的数据。然后，我们将root其设置为这个新的（空）子集Database。最后，我们将新的插入Database到根目录中。但由于我们root在第二步中进行了更改，它不再是父级：我们将d作为其自身的子级插入！

相反，我们想交换后两个步骤的顺序。但是如果我们简单地交换这两行，就会得到错误

// if key doesnt exist add it with a ne empty hashmap
let d = Database{children: HashMap::new(), data: "".to_string()};

// set root to this new databse obejct
root = &mut d.children; 

root.insert(subkey.to_string(), d);

所以问题是，d当我们尝试设置它的子变量时，它不再是局部变量root。我们需要root成为刚刚插入的值的子代。此类事物的常用惯用语是APIentry。它允许我们尝试从 a 获取值HashMap，如果没有找到，则插入一些内容。最相关的是，此插入返回对现在驻留在该键上的任何值的可变引用。

现在该部分看起来像

// if key doesnt exist add it with a new empty hashmap
let d = Database{children: HashMap::new(), data: "".to_string()};

// insert the new database object and
// set root to the hashmap of children
root = &mut root.entry(subkey.to_string()).or_insert(d).children;

至此，我们已经有了一个明显有效的程序。通过添加一个#[derive(Debug)]to Database，我们可以看到数据库是什么样子的println!("{:#?}, db);。然而，如果我们尝试添加第二个值，一切都会崩溃。它们不是并排放置两个值，而是最终位于数据库的完全独立的分支中。这可以追溯到Some(child)匹配语句分支中注释掉的行。

我们希望设置root对 的可变引用，但即使只是取消注释该行而不进行任何更改，也会导致在其他地方借用时可变借用的child.children错误。root问题是我们现在正在使用借用root.get(&subkey.to_string())。之前，由于我们忽略了child并且另一个分支没有使用该借用的任何数据，因此借用可能会立即结束。现在它必须持续整个比赛时间。即使在这种情况下，这也可以防止我们可变借贷None。

幸运的是，由于我们使用的是entryAPI，所以我们根本不需要这个匹配语句！整个事情可以替换为

let d = Database {
    children: HashMap::new(),
    data: "".to_string(),
};

// insert the new database object and
// set root to the hashmap of children
root = &mut root.entry(subkey.to_string()).or_insert(d).children;

如果子项已存在于子项集中，root.entry(...).or_insert(...)则将指向该已存在的子项。

现在我们只需要清理代码即可。由于您多次使用它，因此我建议考虑将键路径插入到函数中的行为。HashMap<String, Database>我建议不要遵循整个路径，而是遵循其本身，因为这将允许您在最后Database修改其字段。data为此，我建议使用具有此签名的函数：

impl Database {
    fn insert_path(&mut self, path: &[&str]) -> &mut Database {
        todo!()
    }
}

接下来，由于我们只需要在数据库尚不存在时创建一个新的Database( ) ，因此我们可以仅在必要时使用's方法来创建新数据库。当有创建新数据库的函数时，这是最简单的，所以让我们添加到 的派生列表中。这使得我们的函数dEntryor_insert_with#[derive(Default)]Database

impl Database {
    fn insert_path(&mut self, path: &[&str]) -> &mut Self {
        let mut root = self;
        // iterate throught path
        for subkey in path.iter() {
            // insert the new database object if necessary and
            // set root to the hashmap of children
            root = root
                .children
                .entry(subkey.to_string())
                // insert (if necessary) using the Database::default method
                .or_insert_with(Database::default);
        }
        root
    }
}

这个时候我们应该跑去cargo clippy看看有没有什么建议。有一个关于使用to_stringon 的内容&&str。要解决这个问题，您有两种选择。一，使用其他方法之一将&strs 转换为Strings 而不是to_string。二、&&str在使用之前取消引用to_string. 第二个选项更简单。由于我们正在迭代&[&str]（Vec<&str>::iter在您的原始版本中），因此迭代中的项目是&&str. 去除额外参考层的惯用方法是使用模式来解构项目。

for &subkey in path {
   ^^^ this is new
    ... // subkey has type &str instead of &&str here
}

我的最后一条建议是将 的名称更改root为更通用的名称，例如node. 它只是一开始的根，所以此后的名称会产生误导。这是最终代码以及您的测试（游乐场）：

use std::collections::HashMap;

#[derive(Default, Debug)]
struct Database {
    children: HashMap<String, Database>,
    data: String,
}

impl Database {
    fn insert_path(&mut self, path: &[&str]) -> &mut Self {
        // node is a mutable reference to the current database
        let mut node = self;
        // iterate through the path
        for &subkey in path.iter() {
            // insert the new database object if necessary and
            // set node to (a mutable reference to) the child node
            node = node
                .children
                .entry(subkey.to_string())
                .or_insert_with(Database::default);
        }
        node
    }
}

fn main() {
    // make a databse object
    let mut db = Database {
        children: HashMap::new(),
        data: "root".to_string(),
    };

    // some example subkeys
    let subkeys = vec!["key1", "key1.1", "key1.1.3"];
    // and the value i want to insert
    let value = "myvalue";

    let node = db.insert_path(&subkeys);
    node.data = value.to_string();

    println!("{:#?}", db);

    let subkeys = vec!["key1", "key1.1", "key1.1.2"];
    let value = "myvalue2";

    let node = db.insert_path(&subkeys);
    node.data = value.to_string();

    println!("{:#?}", db);
}