performance - HashMap和Vec之间的内存有效转换

我正在尝试将大HashMap<K, V>转换为Vec<(K, V)>。这样做的通常方法如下:

// initialize HashMap
let cap = 50000000;
let mut hm: HashMap<usize, usize> = HashMap::new();
for i in 0..cap {
    hm.insert(i, i);
}
// convert HashMap to Vec
let vec = hm.into_iter().collect::<Vec<(usize, usize)>>();

如果HashMap足够大，则此代码将无法正常工作-在对collect()的调用开始时，原始HashMap仍将保留在内存中，并且Vec将分配有从Iterator提取的较小尺寸提示的容量。即使我应该能够以很少的额外内存开销在这两种类型之间进行转换，这也会对真正的HashMap造成内存不足的 panic 。到目前为止，我已经提出了以下解决方案:

// create small vector
let mut vec: Vec<(usize, usize)> = Vec::with_capacity(100);
for i in hm.into_iter() {
    vec.push(i);
    // reserve few megabytes
    if vec.capacity() - vec.len() < 10 {
        vec.reserve_exact(1000000);
    }
}

有没有更好(更有效或更惯用)的方法来解决这个问题？如果愿意提高性能，我愿意使用unsafe代码。

编辑
正如指出的那样，into_iter在迭代期间不会取消分配，因此建议的解决方案无法按预期工作。除了将HashMap转储到文件然后将该文件读取为Vec之外，还有其他转换这些集合的方法吗？

最佳答案

预先分配所需的确切数量是节省内存和时间的解决方案。

假设您要创建一个包含100个项目的向量。如果要为50个项目分配空间，则在添加项目51时，存在两种可能性:

分配可以扩展到位，然后继续愉快地进行。

无法适当地扩展分配，因此进行了新的更大分配。所有数据都需要从先前的分配中复制；可能是O(n)运算。在此副本期间，两个分配均处于 Activity 状态，占用50 + 100插槽，比原始分配的大小适当时要多。

无法知道会发生哪种情况，因此您必须假设最坏的情况。

这是Iterator使用size_hint方法的原因之一:知道要分配多少项更为有效。

另一方面，HashMap可能将数据存储在一个较大的分配中，因为它效率更高。这意味着不可能(或可能不容易/有效)将一项移出然后减少分配。即使您可以执行此操作，在副本的开头也要分配整个HashMap和Vec。

我可以想到有两种可能会改善这种情况的可能性:

如果HashMap在内部将数据存储在Vec中，则可能会向HashMap添加一种方法，该方法可在经过最后一分钟的清理后返回该Vec。

完全避免存储HashMap和/或Vec。例如，如果您需要遍历数据，则无需先将collect转换为Vec；只是遍历它。