如何按顺序遍历HashMap的键

Question

我希望能按顺序迭代一个 HashMap 的键。有没有更优雅的方法呢？我所能想到的最好的方式是：

use std::collections::HashMap;

fn main() {
    let mut m = HashMap::<String, String>::new();

    m.insert("a".to_string(), "1".to_string());
    m.insert("b".to_string(), "2".to_string());
    m.insert("c".to_string(), "3".to_string());
    m.insert("d".to_string(), "4".to_string());

    let mut its = m.iter().collect::<Vec<_>>();
    its.sort();

    for (k, v) in &its {
        println!("{}: {}", k, v);
    }
}

我希望能够做到像这样：

for (k, v) in m.iter_sorted() {
}
for (k, v) in m.iter_sorted_by(...) {
}

显然我可以编写一个特质来完成这个任务，但我的问题是是否已经存在类似的东西？

编辑：另外，由于人们指出BTreeMap已经排序了，所以我应该说明一下，即使这是正确的，它实际上也不如HashMap + sort()快（当然只要你只排序一次）。以下是随机u32->u32映射的一些基准测试结果：

此外，BTreeMap仅允许单个排序顺序。

- Timmmm

---

如果您真的想要一个 HashMap，这是从概念上讲您能够做到最好的。如果您可以使用 BTreeMap，那么迭代将自动按顺序进行。 - Sven Marnach

是的，我知道BTreeMap，也知道它在算法上是最优的。我只是想问一下编码人性化方面是否有更短、更优雅的写法。 - Timmmm

Answer 1

HashMap 不能保证遍历的顺序。实现一致顺序的最简单方法是使用基于 B-tree 的 BTreeMap ，数据会排序。

你应该明白任何实现都会以 O(n) 的内存为代价，特别是存储所有项的引用并且至少需要 O(n * log(n)) 时间来对数据进行排序。

如果你了解这样做的成本，可以使用来自 itertools crate 的 IterTools::sorted 方法。

use itertools::Itertools; // 0.8.2
use std::collections::HashMap;

fn main() {
    let mut m = HashMap::<String, String>::new();

    m.insert("a".to_string(), "1".to_string());
    m.insert("b".to_string(), "2".to_string());
    m.insert("c".to_string(), "3".to_string());
    m.insert("d".to_string(), "4".to_string());

    println!("{:#?}", m.iter().sorted())
}

Playground链接

- Inline

---

是的，我知道 BTreeMap - Itertools 就是我要找的答案，谢谢！ - Timmmm

另外，使用 O(N) 的内存也不太可能是一个问题，因为 O(N) 的内存已经用于存储实际数据。我还预计 BTreeMap 的内存开销与存储 N 个迭代器的开销相当。至于时间方面，多次排序肯定会更慢，但如果你只需要对数据进行一次排序，如果实现得当，我不会感到惊讶它甚至会更快（取决于它的实现方式），因为 BTreeMap 本质上就是插入排序。 - Timmmm

@Timmmm “插入排序”通常指的是使用O(n ²)算法对数组进行原地排序。在BTreeMap中插入_n_个元素是根本不同的，其时间复杂度为O(n log n)。如果您需要有序数据，我建议使用BTreeMap - 它肯定更简单，也可能更快。 - Sven Marnach

当然，我是指树排序！我不确定 BTreeMap 是否更快。从算法上讲，它们的复杂度相同，至少在 C++ 中，std::map 可能会非常慢，因为它涉及大量的分配。如果有时间，也许我会对其进行基准测试。 - Timmmm

@Timmmm 我也不确定它是否更快，但在没有基准测试的情况下，我会选择更简单的解决方案。 :) - Sven Marnach

刚刚做了一个简单的基准测试，使用10000个随机的u32键和值。 HashMap（使用.reserve()）加上sort花费1.16毫秒，BTreeMap花费1.47毫秒，所以我是正确的！不使用BTreeMap的另一个原因是它只允许单个排序顺序。 - Timmmm

Answer 2

根据@Inline所写的内容，更通用的解决方案使用HashMap，允许按值进行排序并更改值。(请注意，为了使按键和值排序的区别可见，HashMap的内容已进行调整。)

use itertools::Itertools;  // itertools = "0.10"
use std::collections::HashMap;

fn main() {
    let mut m = HashMap::<String, String>::new();

    m.insert("a".to_string(), "4".to_string());
    m.insert("b".to_string(), "3".to_string());
    m.insert("c".to_string(), "2".to_string());
    m.insert("d".to_string(), "1".to_string());

    // iterate (sorted by keys)
    for (k, v) in m.iter().sorted_by_key(|x| x.0) {
        println!("k={}, v={}", k, v);
    }
    println!();

    // iterate (sorted by values)
    for (k, v) in m.iter().sorted_by_key(|x| x.1) {
        println!("k={}, v={}", k, v);
    }
    println!();

    // iterate (sorted by keys), write to values
    for (k, v) in m.iter_mut().sorted_by_key(|x| x.0) {
        *v += "v"; // append 'v' to value
        println!("k={}, v={}", k, v);
    }
}

Playground link

- pt1

---

有人知道如何按值排序并将其写入值吗？ - pt1