时间戳

首页 > 解决方案 > 基于向量元素创建 HashMap 的最节省内存和最快的方法

rust - 基于向量元素创建 HashMap 的最节省内存和最快的方法

问题描述

假设我们将数百万个项目（从数据库表、JSON 文件等）读入Vec<Item>：

#[derive(Clone)]
struct Item {
    id: u64,
    name: String,
    //...
}
let items: Vec<Item> = load_items();

很多时候，为了有效地处理这些数据，我们需要额外的数据结构，例如 HashMap，其中一个项目的字段作为键，项目本身作为值。在我看来，最简单的方法是这样的：

let map_by_name: HashMap<String, Item> = items.iter().map(|x| (x.name.clone(), x.clone())).collect();

这很简单。但是在这里我们克隆了所有数据，这在性能和内存使用方面显然不是最佳的。

在基于 GC 的语言（Java、.NET、Python、JS 等）中，不存在这个特殊问题 - 最简单、最自然的实现不涉及克隆，而只是在向量中存储对对象的附加引用。

在 Rust，AFAIK 中，我们不能移动或引用向量元素。那么什么是最有效的选择呢？想到以下想法：

  1. 使用Rc：
let items: Vec<Rc<Item>> = load_items();
let map_by_name: HashMap<String, Rc<Item>> = items.iter().map(|x| (x.name.clone(), Rc::clone(&x))).collect();
  1. 在 HashMap 值中，我们只将元素的索引存储在向量中：
let map_by_name: HashMap<String, usize> = items.iter().enumerate().map(|(i, x)| (x.name.clone(), i)).collect();

我的理解是否正确，第二种方法通常比第一种更有效，但如果我们需要将地图传递给其他函数，它可能不太方便，因为它总是需要我们传递向量？

另外，我是否缺少第三种方法？

PS：在上面的示例中，我使用克隆String作为密钥。很明显，如果这对特定情况有意义，我们也可以使用&strgetting via ，但我想特别关注更大的问题——物品本身。x.name.as_ref()

标签： rust

解决方案

存储索引（您的第二个示例）不一定更有效/更快，因为 anRc<T>只是指向 a 的指针RcInner<T>，它包含引用计数器和T. 事实上，an与-indexRc<T>的大小相同。usize查找时间基本相同，因为对from的索引Vec和取消引用基本上是内存获取。然而，在创建查找映射时会有更多开销，因为需要增加引用计数器，而索引方法只是假设项目将位于最初找到它们的位置。TRc<T>Rc<T>Rc<Item>

最后一点是告诉我选择哪种方法：如果 theVec<Item>和 theHashMap<Key, usize>可以紧密耦合 - 例如，在同一个结构或同一个函数中，它们无法逃脱 - 那么使用起来可能更方便索引。

但是，如果查找映射四处浮动，则始终存在映射中保存的索引随着Vec更改而失控的危险（例如，稍后有人可能会在Vec收集索引后放入对排序进行排序的代码，破坏联轴器）。如果查找映射暴露给 API 的调用者，我会Rc<Item>保证查找映射只包含有效的引用。

推荐阅读