基于值从HashMap中删除条目

Question

我写了下面的代码（+演示），用于基于值从HashMap中删除条目。它能正常工作，但我感觉我在与借用检查器进行斗争，因为我使用了：

• clone() 来避免对同一组键的两个引用
• 额外的 let tmp = 绑定来增加临时值的生存期

---

Note to translator: Please translate the above paragraph to Chinese.

use std::collections::HashMap;

fn strip_empties(x: &mut HashMap<String, i8>) {
    let tmp = x.clone();
    let empties = tmp
         .iter()
         .filter(|&(_, &v)| v == 0)
         .map(|(k, _)| k);

    for k in empties { x.remove(k); }
}

fn main() {
    let mut x: HashMap<String, i8> = HashMap::new();
    x.insert("a".to_string(), 1);
    x.insert("b".to_string(), 0);
    strip_empties(&mut x);

    println!("Now down to {:?}" , x);
}

有更简洁、更符合习惯的方法来完成这个任务吗？

- Bosh

Answer 1

其他答案已经过时。从 Rust 1.27 开始，您可以使用 HashMap::retain 来仅保留您感兴趣的元素。您可以使用闭包指定要保留的元素。

x.retain(|_, v| *v != 0);

- Johannes

---

展示如何解决OP代码中的问题的示例会对使这个回答更好起很大作用。 - Shepmaster

元问题：是否有一种方法可以将更新的答案推到顶部？例如，可能将其更改为接受的答案？ - mallwright

Answer 2

为什么要突变HashMap？只需创建一个新的（万岁不可变性）：

fn strip_empties(x: HashMap<String, i8>) -> HashMap<String, i8> {
    return x.into_iter()
        .filter(|&(_, v)| v != 0)
        .collect();
}

Playpen

---

编辑：为何这是可行的。

当然您需要考虑您的使用情况。如果您有一个大的HashMap或者需要过滤许多/少量元素，最佳实现方式可能会有所不同。我们来比较一下这些实现方法。

use std::collections::HashMap;

fn strip_empties_mutable(x: &mut HashMap<String, i8>) {
    let empties: Vec<_> = x
        .iter()
        .filter(|&(_, &v)| v == 0)
        .map(|(k, _)| k.clone())
        .collect();
    for empty in empties { x.remove(&empty); }
}

fn strip_empties_immutable(x: HashMap<String, i8>) -> HashMap<String, i8> {
    return x.into_iter()
        .filter(|&(_, v)| v != 0)
        .collect();
}

fn build_hashmap() -> HashMap<String, i8> {
    let mut map = HashMap::new();
    for chr in "abcdefghijklmnopqrstuvmxyz".chars() {
        map.insert(chr.to_string(), chr as i8 % 2);
    }
    return map;
}

#[cfg(mutable)]
fn main() {
    let mut map = build_hashmap();
    strip_empties_mutable(&mut map);
    println!("Now down to {:?}" , map);
}

#[cfg(immutable)]
fn main() {
    let mut map = build_hashmap();
    map = strip_empties_immutable(map);
    println!("Now down to {:?}" , map);
}

将此内容保存为hashmap.rs并运行：

rustc --cfg mutable -O -o mutable hashmap.rs
rustc --cfg immutable -O -o immutable hashmap.rs

如果我们查看不同的运行时（例如使用perf stat -r 1000 ./XXX），我们并没有看到显著的差异。

但是让我们来看看分配的数量：

valgrind --tool=callgrind --callgrind-out-file=callgrind_mutable ./mutable
valgrind --tool=callgrind --callgrind-out-file=callgrind_immutable ./immutable
callgrind_annotate callgrind_mutable | grep 'je_.*alloc'
callgrind_annotate callgrind_immutable | grep 'je_.*alloc'

• callgrind_mutable:

  7,000  ???:je_arena_malloc_small [$HOME/hashmap/mutable]
  6,457  ???:je_arena_dalloc_bin_locked [$HOME/hashmap/mutable]
  4,800  ???:je_mallocx [$HOME/hashmap/mutable]
  3,903  ???:je_sdallocx [$HOME/hashmap/mutable]
  2,520  ???:je_arena_dalloc_small [$HOME/hashmap/mutable]
    502  ???:je_rallocx [$HOME/hashmap/mutable]
    304  ???:je_arena_ralloc [$HOME/hashmap/mutable]
  

• callgrind_immutable:

  5,114  ???:je_arena_malloc_small [$HOME/hashmap/immutable]
  4,725  ???:je_arena_dalloc_bin_locked [$HOME/hashmap/immutable]
  3,669  ???:je_mallocx [$HOME/hashmap/immutable]
  2,980  ???:je_sdallocx [$HOME/hashmap/immutable]
  1,845  ???:je_arena_dalloc_small [$HOME/hashmap/immutable]
    158  ???:je_rallocx [$HOME/hashmap/immutable]
  

这并不令人惊讶，因为可变方法中的clone()调用也会分配内存。当然，可变版本可能会产生具有更大容量的HashMap。

- user4316209

---

虽然在纸面上看起来很不错，但这将涉及到对HashMap条目的大量释放和分配。这就是为什么突变可能更可取的原因。 - sellibitze

我认为这只涉及到一次分配和释放内存（针对整个后备表）。 - huon

@Bosh 在这种情况下，源HashMap被销毁了。但是，如果使用另一个变量，它可以保留其原始形式。因此，它是不可变的，因为原始HashMap没有被改变。 - user4316209

@lummax：我的理解是，即使您使用另一个变量，例如 let mut stripped_map = strip_empties_immutable(map);，原始的 map 变量也将无法再使用，因为 into_iter 的行为（它会消耗掉这个东西）。是这样吗？ - Bosh

@Bosh：当然可以。into_iter()是消耗性的（strip_empties()也是消耗性的）。但这很容易改成引用。这是关于是否可以构建一个新的Hashmap。 - user4316209

Answer 3

在迭代 hashmap 期间无法删除值（既不能通过 remove，也不能通过 Entry api），这是因为借用限制的问题。因此，你的想法（收集要删除的键）非常接近正确的解决方案。

你只需收集键的副本即可，无需克隆整个哈希表：

fn strip_empties(x: &mut HashMap<String, i8>) {
    let empties: Vec<_> = x
         .iter()
         .filter(|&(_, &v)| v == 0)
         .map(|(k, _)| k.clone())
         .collect();
    for empty in empties { x.remove(&empty); }
}

- swizard

---

这引出了一个有趣的问题，为什么HashMap没有返回Entry(或(Key, Entry)元组)的迭代器。我看不出为什么这不可能。有人知道这是否只是一个“好吧，还没有人去实现它”的情况吗？ - fjh

HashMap 的 iter 函数（如上所示）确实会创建一个 Key, Entry 元组的迭代器。我可能误解了你的问题... - Bosh

不同的“Entry”。fjh谈论的是std::collections::hash_map :: Entry，我有同样的问题。我认为Bosh只是通用地使用单词Entry表示映射中的值。 - Clayton Rabenda