• 二叉树
  • 前中后序遍历
  • 最大宽度
  • 判断完全、平衡、搜索、满二叉树
• Rust的HashMap特性

反序列化

前序遍历的字符串为：”1_2_4_N_N_5_N_N_3_6_N_N_7_N_N”， 创建一棵二叉树

type TreeLink = Option<Rc<RefCell<TreeNode>>>;

fn create_bitree_cursive(node_values: &mut VecDeque<&str>) -> TreeLink {
    let val = node_values.pop_front().unwrap();
    if val == "N" {
        return None;
    }

    let mut node: TreeNode = TreeNode::new(val.parse::<i32>().unwrap());
    node.borrow_mut().left = create_bitree_cursive(node_values);
    node.borrow_mut().right = create_bitree_cursive(node_values);
    Some(Rc::new(RefCell::new(node)))
}

/* 前序遍历的方式创建二叉树 */
fn create_bitree(s: &str) -> TreeLink {
    let mut node_values: VecDeque<&str> = s.split('_').collect();
    create_bitree_cursive(&mut node_values)
}

二叉树

• 递归序
  • 递归过程中每个节点都会顺序的出入3次
• 前序
  • 先进入头，再进左子树，再进右子树
• 中序
  • 先左、再中、再右
• 后序
  • 先左、再右、再头
  • 先右、再左、再头

前序遍历

递归方式

fn preorder_cursive(root: TreeLink, res: &mut Vec<i32>) {
    if root.is_none() {
        return;
    }

    if let Some(node) = root {
        res.push(node.borrow().elem);
        preorder_cursive(node.borrow().left.clone(), res);
        preorder_cursive(node.borrow().right.clone(), res);
    }
}

fn preorder_traversal(root: TreeLink) {
    let mut res: Vec<i32> = Vec::new();
    preorder_cursive(root, &mut res);
    println!("res: {:?}", res);
}

非递归方式

• 算法
  • 每次栈弹出一个节点
  • 打印这个节点
  • 先右、再左节点入栈
  • 循环

• 实现代码

    fn preorder_traversal2(root: &TreeLink) -> Vec<i32> {
        if root.is_none() {
            return vec![];
        }
  
        let mut stack: Vec<Rc<RefCell<TreeNode>>> = vec![];
        let mut res: Vec<i32> = vec![];
  
        stack.push(root.clone().unwrap());
        while let Some(cur) = stack.pop() {
            res.push(cur.borrow().elem);
            if let Some(node) = cur.borrow().right.clone() {
                stack.push(node);
            }
            if let Some(node) = cur.borrow().left.clone() {
                stack.push(node)
            }
        }
        res
    }
  

中序遍历

• 算法
  • 每棵左子树进栈
  • 依次弹出
  • 再将弹出的节点的右侧左子树进栈

• 代码实现

    fn inorder_uncursive(root: &TreeLink) -> Vec<i32> {
        let mut res: Vec<i32> = vec![];
        if root.is_none() {
            return res;
        }
  
        let mut stack: Vec<Rc<RefCell<TreeNode>>> = vec![];
        let mut head = root.clone();
        while !stack.is_empty() || head.is_some() {
            if let Some(node) = head {
                stack.push(node.clone());
                head = node.borrow().left.clone();
            } else {
                if let Some(node) = stack.pop() {
                    res.push(node.borrow().elem);
                    head = node.borrow().right.clone();
                }
            }
        }
  
        res
    }
  

后序遍历

• 算法流程
  • 头节点入栈
  • 栈弹出节点
  • 先左再右/先右再左
  • 循环

• 先左后右的代码实现

    fn posorder1_uncursive(root: &TreeLink) -> Vec<i32> {
        let mut res: Vec<i32> = vec![];
        if root.is_none() {
            return res;
        }
        // 这里使用TreeLink的类型，代码更简单，但算法不直观 
        let mut stack: Vec<TreeLink> = vec![];
        let mut support: Vec<TreeLink> = vec![];
        stack.push(root.clone());
        while !stack.is_empty() {
            if let Some(Some(node)) = stack.pop() {
                support.push(Some(node.clone()));
                stack.push(node.borrow().left.clone());
                stack.push(node.borrow().right.clone());
            }
        }
        while !support.is_empty() {
            if let Some(Some(node)) = support.pop() {
                res.push(node.borrow().elem)
            }
        }
  
        res
    }
  

• 先右后左的代码实现

    fn posorder_uncursive2(root: &TreeLink) -> Vec<i32> {
        let mut res: Vec<i32> = vec![];
        if root.is_none() {
            return res;
        }
        // 这里用Rc<RefCell<>>类型，代码繁琐
        let mut stack: Vec<Rc<RefCell<TreeNode>>> = vec![];
        let mut support: Vec<Rc<RefCell<TreeNode>>> = vec![];
        stack.push(root.clone().unwrap());
        while !stack.is_empty() {
            if let Some(node) = stack.pop() {
                support.push(node.clone());
                if let Some(left_node) = node.borrow().right.clone() {
                    stack.push(left_node);
                }
                if let Some(right_node) = node.borrow().left.clone() {
                    stack.push(right_node);
                }
            }
        }
        while let Some(node) = support.pop() {
            res.push(node.borrow().elem)
        }
  
        res
    }
  

宽度优先遍历

• 算法
  • 用队列
  • 先进头节点
  • 弹出节点就打印
  • 再把它的节点先左后右入队
  • 循环

• 算法实现

    fn width_traversial(root: &TreeLink) -> Vec<i32> {
        let mut res: Vec<i32> = vec![];
        let mut queue: VecDeque<TreeLink> = VecDeque::new();
  
        queue.push_back(root.clone());
        while !queue.is_empty() {
            if let Some(Some(node)) = queue.pop_front() {
                res.push(node.borrow().elem);
                queue.push_back(node.borrow().left.clone());
                queue.push_back(node.borrow().right.clone());
            }
        }
  
        res
    }
  

求二叉树的最大宽度

用HashMap

• 数据结构

    type TreeLink = Option<Box<TreeNode>>;
    #[derive(Debug, Hash, PartialEq, Eq)]
    struct TreeNode {
        elem: i32,
        left: TreeLink,
        right: TreeLink,
    }
  

  • 由于RefCell<T>不能实现Hash特性
  • 所以使用了Box<T>的方案
• 算法
  • 初始状态
    • 当前统计的层cur_level = 1
    • 最大宽度 max_level_nodes = 0
    • 当前层宽度 cur_level_nodes = 0
    • HashMap<节点, 此节点对应的层>
    • 队列queue<节点>
    • 将root节点入队列
    • 将root节点和它对应的层1入HashMap.insert(root, 1)
  • 队列弹出节点
  • 从HashMap中取得此节点对应的层
  • 如果当前层 == 节点对应层
    • 当前层宽度加上1
  • 如果当前层 != 节点对应层
    • 说明节点已经到下层
    • 当前层+=1
    • 统计最大宽度
    • 当前层宽度 = 1
  • 把节点的左、右非空节点入队列
  • 把节点的左、右非空节点对应的层入HashMap

• 算法实现

    fn max_width_hash(root: &TreeLink) -> i32 {
        let mut map: HashMap<Option<&Box<TreeNode>>, usize> = HashMap::new();
        let mut queue: VecDeque<Option<&Box<TreeNode>>> = VecDeque::new();
        let mut cur_level: usize = 1;
        let mut cur_level_nodes = 0;
        let mut max_level_nodes: i32 = 0;
        queue.push_back(root.as_ref());
        map.insert(root.as_ref(), 1);
  
        while let Some(link) = queue.pop_front() {
            let node_level = *map.get(&link).unwrap();
            if let Some(cur) = link {
                if node_level == cur_level {
                    cur_level_nodes += 1;
                } else {
                    max_level_nodes = max(max_level_nodes, cur_level_nodes);
                    cur_level_nodes = 1;
                    cur_level += 1;
                }
                if cur.left.is_some() {
                    map.insert(cur.left.as_ref(), cur_level + 1);
                    queue.push_back(cur.left.as_ref());
                }
                if cur.right.is_some() {
                    map.insert(cur.right.as_ref(), cur_level + 1);
                    queue.push_back(cur.right.as_ref());
                }
            }
        }
  
        max(max_level_nodes, cur_level_nodes)
    }
  

不用HashMap

• 算法
  • 队列弹出节点
  • 当前节点是不是本层最后一个节点
    • 不是：增加本层节点数
    • 是：更新最大宽度，更新下一层最后一个节点

• 算法实现

    fn max_width_unhash(root: &TreeLink) -> i32 {
        let mut queue: VecDeque<Option<&Box<TreeNode>>> = VecDeque::new();
        let mut max_level_nodes = 0;
        let mut cur_level_nodes = 0;
        let mut cur_end: &Box<TreeNode> = root.as_ref().unwrap();
        let mut next_end: &Box<TreeNode> = root.as_ref().unwrap();
        queue.push_back(root.as_ref());
  
        while let Some(Some(node)) = queue.pop_front() {
            cur_level_nodes += 1;
            if node.left.is_some() {
                queue.push_back(node.left.as_ref());
                next_end = node.left.as_ref().unwrap();
            }
            if node.right.is_some() {
                queue.push_back(node.right.as_ref());
                next_end = node.right.as_ref().unwrap();
            }
  
            if node == cur_end {
                max_level_nodes = max(max_level_nodes, cur_level_nodes);
                cur_level_nodes = 0;
                cur_end = next_end;
            }
        }
  
        max_level_nodes
    }
  
  

二叉树的属性判断

判断是否是搜索二叉树

• 搜索二叉树
  • 左节点 < root
  • 右节点 > root
• 算法流程
  • 中序遍历一定是升序

• 递归算法实现

    fn check_bts(root: Option<&Box<TreeNode>>) -> BtsInfo {
        if let Some(node) = root {
            let left = check_bts(node.left.as_ref());
            if !left.isbts || left.max_val >= node.elem {
                return BtsInfo::new(false);
            }
  
            let right = check_bts(node.right.as_ref());
            if !right.isbts || node.elem >= right.min_val {
                return BtsInfo::new(false);
            } else {
                let mut info = BtsInfo::new(true);
                info.min_val = min(node.elem, left.min_val);
                info.max_val = max(node.elem, right.max_val);
                return info;
            }
        } else {
            BtsInfo::new(true)
        }
    }
  
    fn is_bts(root: &TreeLink) -> bool {
        let info = check_bts(root.as_ref());
        info.isbts
    }
  

判断是否是完全二叉树

• 完全二叉树
  • 完整齐全的二叉树
  • 每一层都是全的
  • 最后一层也是先有左子再有右子
• 算法流程
  • 宽度优先遍历
  • 若出现无左有右则不是
  • 满足上面条件的情况下
    • 若出现左右子不全
    • 则后面的节点必须为叶子节点

• 算法实现

    fn is_cbt_uncursive(root: &TreeLink) -> bool {
        let mut queue: VecDeque<Option<&Box<TreeNode>>> = VecDeque::new();
        queue.push_back(root.as_ref());
        let mut must_leaf: bool = false;
  
        while let Some(Some(node)) = queue.pop_front() {
            if node.left.is_none() && node.right.is_some() {
                return false;
            }
            if node.left.is_some() && node.right.is_none() {
                must_leaf = true;
            }
            if must_leaf && !is_leaf(node) {
                return false;
            }
  
            queue.push_back(node.left.as_ref());
            queue.push_back(node.right.as_ref());
        }
  
        true
    }
  

判断是否是满二叉树

• 满二叉树
  • 树的最大深度deep和节点数N有关系：deep = 2^N - 1

• 递归算法实现

    fn fbts_cursive(root: Option<&Box<TreeNode>>) -> FbtsInfo {
        if let Some(node) = root {
            let left = fbts_cursive(node.left.as_ref());
            let right = fbts_cursive(node.right.as_ref());
  
            FbtsInfo {
                nodes: left.nodes + right.nodes + 1,
                deep: max(left.deep, right.deep) + 1,
            }
        } else {
            FbtsInfo { nodes: 0, deep: 0 }
        }
    }
  
    fn is_fbts_cursive(root: &TreeLink) -> bool {
        if root.is_none() {
            return true;
        }
        let info = fbts_cursive(root.as_ref());
        info.nodes == (1 << info.deep) - 1
    }
  

• 非递归算法实现

    fn is_fbts_uncursive(root: &TreeLink) -> bool {
        let mut queue: VecDeque<Option<&Box<TreeNode>>> = VecDeque::new();
        let mut cur_end: &Box<TreeNode> = root.as_ref().unwrap();
        let mut next_end: &Box<TreeNode> = root.as_ref().unwrap();
        let mut deep: u32 = 0;
        let mut total_nodes: i32 = 0;
        queue.push_back(root.as_ref());
  
        while let Some(Some(node)) = queue.pop_front() {
            total_nodes += 1;
            if node.left.is_some() {
                queue.push_back(node.left.as_ref());
                next_end = node.left.as_ref().unwrap();
            }
            if node.right.is_some() {
                queue.push_back(node.right.as_ref());
                next_end = node.right.as_ref().unwrap();
            }
  
            if node == cur_end {
                cur_end = next_end;
                deep += 1;
            }
        }
  
        total_nodes == (1 << deep) - 1
    }
  

判断是否是平衡二叉树

• 平衡二叉树
  • 左、右子树都是平衡的
  • 左子树与右子树的高度差不超过1

• 算法实现

    struct BlInfo {
        is_balance: bool,
        deep: i32,
    }
  
    fn balance_cursive(root: Option<&Box<TreeNode>>) -> BlInfo {
        if let Some(node) = root {
            let left = balance_cursive(node.left.as_ref());
            let right = balance_cursive(node.right.as_ref());
            BlInfo {
                deep: max(left.deep, right.deep) + 1,
                is_balance: left.is_balance && right.is_balance && (left.deep - right.deep).abs() < 2,
            }
        } else {
            BlInfo {
                deep: 0,
                is_balance: true,
            }
        }
    }
  
    fn is_balance(root: &TreeLink) -> bool {
        let info = balance_cursive(root.as_ref());
        info.is_balance
    }
  

寻找最近的公共祖先节点

• 算法1
  • 将二叉树中每个结点的祖先节点都放到HashMap中
  • 针对node1收集从它到根节点的父节点
  • 针对node2查看它的父节点是否有node1父节点的共同节点

• 算法1实现

    fn find_lca<'a>(
    root: &'a TreeLink,
    node1: TreeNodeLink,
    node2: TreeNodeLink,
    ) -> Option<&'a Box<TreeNode>> {
        let mut lca: TreeNodeLink = None;
        let mut fmap: HashMap<TreeNodeLink, TreeNodeLink> = HashMap::new();
        let mut set: HashSet<TreeNodeLink> = HashSet::new();
        fmap.insert(root.as_ref(), root.as_ref());
        // 创建所有节点的父节点集合{子节点:父节点}
        get_fmap(root.as_ref(), &mut fmap);
        // 将所有node1的父节点收集到set中
        let mut node = node1;
        while let Some(&Some(father)) = fmap.get(&node) {
            if father != root.as_ref().unwrap() {
                set.insert(Some(father.clone()));
                node = Some(father);
            } else {
                break;
            }
        }
  
        // 检查node2的所有父节点是不是在set中，是则找到共同最低父节点
        node = node2;
        while let Some(&Some(father)) = fmap.get(&node) {
            if father == root.as_ref().unwrap() {
                break;
            }
            if !set.contains(&Some(father)) {
                node = Some(father);
            } else {
                lca = Some(father);
                break;
            }
        }
  
        lca
    }
  

• 算法2递归实现

    fn find_lca_cursive<'a>(
        root: TreeNodeLink<'a>,
        node1: TreeNodeLink<'a>,
        node2: TreeNodeLink<'a>,
    ) -> TreeNodeLink<'a> {
        if root.is_none() || root == node1 || root == node2 {
            return root;
        }
        if let Some(node) = root {
            // 左子树有节点、右子树有节点
            let left = find_lca_cursive(node.left.as_ref(), node1, node2);
            let right = find_lca_cursive(node.right.as_ref(), node1, node2);
            match (left, right) {
                (Some(_), Some(_)) => return root,
                (Some(l), _) => return Some(l),
                (None, Some(r)) => return Some(r),
                (None, None) => return None,
            }
        }
        None
    }
  

寻找一个节点的后继节点

• 后继节点
  • 中序遍历中，排在一个节点后面的节点是后继节点
  • 排在一个节点的前面节点是前趋节点
  • 中序遍历： DBEAFCG->Null

• 如果节点的结构如下，能否缩短找后继节点的复杂度

    class Node {
        int elem;
        Node left;
        Node right;
        Node parent;
    }
  

• 算法流程
  • 如果节点x有右树
    • x的后继是右树的最左叶节点
  • 如果节点x无右树
    • 向上看是否是父节点的左孩子
    • 不是继续向上找
    • 是则后继就是这个父节点
  • 整棵树最后一个节点特殊

• 算法伪代码实现

    // 找最左侧节点
    fn left_leaf(root: TreeNodeLink) -> TreeNodeLink {
        if let Some(node) = root {
            while node.left.is_some() {
                node = node.left.as_ref().unwrap();
            }
            Some(node)
        } else {
            None
        }
    }
  
    fn node_successor(head: TreeNodeLink) -> TreeNodeLink {
        if let Some(node) = head {
            // 如果节点有右子树，后继节点为右子树最左侧节点
            if node.right.is_some() {
                return left_leaf(node.right.as_ref());
            }
  
            // 如果没有右子树，当前节点是父节点的右孩子，继续向上找
            let mut parent = node.parent;
            while parent.is_some && parent.left != node {
                node = parent;
                parent = node.parent;
            }
            // 当parent是空时，说明node是整棵树最右侧结点，没有后继节点
            return parent;
        } else {
            None
        }
    }
  

将长条纸对折N次，打印凹凸顺序

折纸就是一棵二叉树，所有凸节点的左节点为凸，右节点为凹

• 算法
  • 中序遍历

• 算法实现

    fn print_cursive(curlevel: i32, level: i32, down: bool) {
        if curlevel > level {
            return;
        }
        print_cursive(curlevel + 1, level, true);
        if down {
            print!("凹");
        } else {
            print!("凸");
        }
        print_cursive(curlevel + 1, level, false)
    }
  
    // 对折n次
    fn print_all_folds(n: i32) {
        print_cursive(1, n, true);
    }
  

HashMap

要求键值实现Eq和Hash特性，尽管这经常可以通过使用#[derive(PartialEq, Eq, Hash)]实现。如果你自己实现了这些，重要的是以下属性成立:

k1 == k2 => hash(k1) == hash(k2)

换句话说，如果两个键相等，它们的哈希值也必须相等

自定义的key类型需要Eq和Hash特性，Eq又需要PartialEq

ParitalEq和Eq

Eq完成的是相等和不相等的判断，ParitalEq可以实现A和B是否相等的判断，但不能与自己比较，因为NaN != NaN；而Eq则是表示可以和自己进行相等判断(有点类似异或交换的感觉，通过异或交换a、b的前提是他们在不同的内存空间中，否则就会失效)

通过#[driver(ParitalEq, Eq)]系统会自动实现相等性，它是把结构体中所有字段如果相等，则判定相等

Hash 特性

pub trait Hash {
    fn hash<H>(&self, state: &mut H)
    where H: Hasher;

    fn hash_slice<H>(data: &[Self], state: &mut H)
    where H: Hasher,
    { ... }
}

一个可散列的类型：

实现Hash的类型能够用Hasher的一个实例进行散列。

如何实现Hash特性

系统自动实现

如果所有字段都实现了Hash，你可以用#[derive(Hash)]来派生Hash。产生的哈希值将是在每个字段上调用哈希值的组合。

#[derive(Hash)]
struct Rustacean {
    name: String,
    country: String,
}

实现自己的Hash特性

use std::hash::{Hash, Hasher};

struct Person {
    id: u32,
    name: String,
    phone: u64,
}

impl Hash for Person {
    // 将state此值提供给给定的散列器 Hasher
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.id.hash(state);
        self.phone.hash(state);
    }
}

• fn hash<H>(&self, state: &mut H)
  • 将state此值提供给给定的散列计算器Hasher

  • 使用

    use std::collections::hash_map::DefaultHasher;
    use std::hash::{Hash, Hasher};
    
    let mut hasher = DefaultHasher::new();
    7920.hash(&mut hasher);
    println!("Hash is {:x}!", hasher.finish());
    

• fn hash_slice<H>(data: &[Self], state: &mut H)
  • 将Self这种类型的切片输入给定的散列器
  • 这个方法是作为一种便利，但它的实现也明确地没有被指定。
  • 它并不保证等同于对hash的重复调用，Hash的实现应该记住这一点
  • 如果切片在PartialEq的实现中没有被当作一个整体单元，就应该自己调用hash。
  • 例如
    • 一个VecDeque的实现可能会天真地调用as_slices
    • 然后在每个slice上进行hash_slice
    • 但这是错误的
    • 因为这两个slice可以通过调用make_contiguous来改变Key的值
    • 而不会影响PartialEq的结果
    • 由于这些切片没有被当作单一的单位
    • 而是一个更大的deque的一部分
    • 所以这个方法不能使用

  • 使用

    let mut hasher = DefaultHasher::new();
    let numbers = [6, 28, 496, 8128];
    Hash::hash_slice(&numbers, &mut hasher);
    println!("Hash is {:x}!", hasher.finish());
    

其中Hasher也是一个特性，它是一个用于散列任意字节流的特性。Hasher的实例通常代表在散列数据时改变的状态。

Hasher提供了一个相当基本的接口，用于检索生成的哈希值（用finish），以及将整数和字节切片写进实例（用write和write_u8等）。大多数情况下，Hasher实例是与Hash特性一起使用的。

Hasher主要有两个方法：

pub trait Hasher {
    // 返回到目前为止所写数据的哈希值
    fn finish(&self) -> u64;
    // 将一些数据写入哈希器
    fn write(&mut self, bytes: &[u8]);
}

Hasher Hash计算器的使用方法：

let mut hasher = DefaultHasher::new();
hasher.write_u32(1989);
hasher.write_u8(11);
hasher.write_u8(9);
hasher.write(b"Huh?");
println!("Hash is {:x}!", hasher.finish());

Cell

共享的可变容器。 rust内存安全基于以下规则：给定对象T，只能有以下之一：

• 对对象有几个不可变的引用（&T）（也被称为别名）。
• 对象有一个可变引用（&mut T）（也称为可变性）。

这是由Rust编译器强制执行的。然而，在有些情况下，这个规则不够灵活。有时需要对一个对象有多个引用，但又要对其进行突变。

可共享的可变容器的存在是为了允许以可控的方式进行修改，甚至在存在别名的情况下。Cell和RefCell都允许以单线程的方式来做这个。然而，Cell和RefCell都不是线程安全的（它们没有实现Sync）。如果你需要在多个线程之间进行别名和变异，可以使用Mutex、RwLock或原子类型。

Cell和RefCell类型的值可以通过共享引用（即常见的&T类型）进行变异，而大多数Rust类型只能通过唯一的（&mut T）引用进行变异。我们说Cell和RefCell提供了 "内部可变性"，而典型的Rust类型则表现为 "继承的可变性"。

Cell类型有两种风格。Cell和RefCell。Cell通过将值移入和移出Cell来实现内部可变性。要使用引用而不是值，必须使用RefCell类型，在变异之前获得一个写锁。Cell提供了检索和改变当前内部值的方法。

• 对于实现Copy的类型，get方法检索当前的内部值
• 对于实现Default的类型，take方法用Default::default()替换当前的内部值并返回替换后的值
• 对于所有的类型，替换方法替换当前的内部值并返回替换后的值，into_inner方法消耗Cell并返回内部值。此外，set方法替换了内部值，放弃了被替换的值

RefCell使用Rust的生命期来实现 "动态借用"，在这个过程中，人们可以要求对内部值进行临时的、独占的、可改变的访问。RefCell的借用是在 "运行时 "跟踪的，而不像Rust的本地引用类型那样，完全是在编译时静态跟踪的。因为RefCell的借用是动态的，所以有可能试图借用一个已经被可变借用的值；当这种情况发生时，会导致线程恐慌。

更常见的继承可变性，即一个人必须有唯一的访问权才能变异一个值，这是一个关键的语言元素，使Rust能够强烈地推理指针别名，静态地防止崩溃的错误。正因为如此，继承的可变性是首选，而内部可变性是最后的手段。由于Celll类型可以在不允许的地方进行变异，所以在某些情况下，内部变异可能是合适的，甚至是必须使用的，比如说

• 在不可变的东西的 “内部 “引入可变性
• 逻辑上不可变的方法的实现细节。
• 克隆的变异实现

在不可变的东西内部引入了可变性

许多共享的智能指针类型，包括Rc和Arc，提供了可以在多方之间克隆和共享的容器。因为所包含的值可能是多重aliased的，它们只能用&，而不是&mut来借用。如果没有Cell，就根本不可能对这些智能指针内的数据进行变异。

那么，在共享指针类型内放置一个RefCell来重新引入可变性是非常常见的。

use std::cell::{RefCell, RefMut};
use std::collections::HashMap;
use std::rc::Rc;

fn main() {
    let shared_map: Rc<RefCell<_>> = Rc::new(RefCell::new(HashMap::new()));
    // 创建一个新块来限制动态借用的范围
    {
        let mut map: RefMut<_> = shared_map.borrow_mut();
        map.insert("africa", 92388);
        map.insert("kyoto", 11837);
        map.insert("piccadilly", 11826);
        map.insert("marbles", 38);
    }

    // 如果前面没有新建代码块，这里就会出问题
    // 这就是使用`RefCell'的主要危害
    let total: i32 = shared_map.borrow().values().sum();
    println!("{}", total);
}

逻辑不可变方法的实现细节

偶尔，我们可能不希望在API中暴露出 “引擎盖 “下正在发生的变异。这可能是因为逻辑上的操作是不可变的，但是例如缓存迫使实现方法执行突变；或者是因为你必须使用突变来实现一个最初定义为取自&self的特征方法。