hashmap - HashMap 和 Vec 之间共享 str 的所有权

Question

我有 Java/C#/JavaScript 背景，我正在尝试实现 Dictionary这将为每个传递的字符串分配一个永远不会改变的 id。字典应该能够通过指定的 id 返回一个字符串。这允许在文件系统中更有效地存储一些具有大量重复字符串的数据，因为只存储字符串的 ID 而不是整个字符串。

我认为带有 HashMap 的结构和一个 Vec会做，但事实证明比这更复杂。

我从使用 &str 开始作为 HashMap 的键和 Vec 的项目就像下面的示例一样。 HashMap 的值作为 Vec 的索引.

pub struct Dictionary<'a> {
    values_map: HashMap<&'a str, u32>,
    keys_map: Vec<&'a str>
}

impl<'a> Dictionary<'a> {
    pub fn put_and_get_key(&mut self, value: &'a str) -> u32 {
        match self.values_map.get_mut(value) {
            None => {
                let id_usize = self.keys_map.len();
                let id = id_usize as u32;
                self.keys_map.push(value);
                self.values_map.insert(value, id);
                id
            },
            Some(&mut id) => id
        }
    }
}

这工作得很好，直到发现 str s 需要存储在某个地方，最好是在同一个 struct 中以及。我试图存储 Box<str>在Vec和 &'a str在HashMap .

pub struct Dictionary<'a> {
    values_map: HashMap<&'a str, u32>,
    keys_map: Vec<Box<str>>
}

借用检查器当然不允许这样做，因为它会允许 HashMap 中存在悬空指针。当从 Vec 中删除项目时(或者实际上有时当另一个项目被添加到 Vec 但这是题外话)。

我知道我要么需要写 unsafe代码或使用某种形式的共享所有权，其中最简单的一种似乎是 Rc . Rc<Box<str>>的用法看起来像是引入了双重间接寻址，但似乎没有简单的方法来构建 Rc<str>此刻。

pub struct Dictionary {
    values_map: HashMap<Rc<Box<str>>, u32>,
    keys_map: Vec<Rc<Box<str>>>
}

impl Dictionary {
    pub fn put_and_get_key(&mut self, value: &str) -> u32 {
        match self.values_map.get_mut(value) {
            None => {
                let id_usize = self.keys_map.len();
                let id = id_usize as u32;
                let value_to_store = Rc::new(value.to_owned().into_boxed_str());
                self.keys_map.push(value_to_store);
                self.values_map.insert(value_to_store, id);
                id
            },
            Some(&mut id) => id
        }
    }
}

关于所有权语义，一切似乎都很好，但上面的代码无法编译，因为 HashMap现在需要 Rc ，不是 &str :

error[E0277]: the trait bound `std::rc::Rc<Box<str>>: std::borrow::Borrow<str>` is not satisfied
  --> src/file_structure/sample_dictionary.rs:14:31
   |
14 |         match self.values_map.get_mut(value) {
   |                               ^^^^^^^ the trait `std::borrow::Borrow<str>` is not implemented for `std::rc::Rc<Box<str>>`
   |
   = help: the following implementations were found:
   = help:   <std::rc::Rc<T> as std::borrow::Borrow<T>>

问题:

1. 有没有办法构造一个Rc<str> ？
2. 还有哪些其他结构、方法或方式可以帮助解决这个问题。本质上，我需要一种有效存储两个 map 的方法 string-by-id和 id-by-string并能够通过 &str 检索 ID ，即没有任何过多的分配。

Answer 1

Is there a way to construct an Rc<str>?

很烦人，据我所知不是这样。 Rc::new需要 Sized争论，我不确定这是一个实际的限制，还是只是被遗忘了的东西。

Which other structures, methods or approaches could help to resolve this problem?

如果您查看 get 的签名你会注意到:

fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
    where K: Borrow<Q>, Q: Hash + Eq

因此，您可以按 &str 进行搜索如果K工具 Borrow<str> .

String工具 Borrow<str> , 所以最简单的解决方案就是简单地使用 String作为 key 。当然这意味着你实际上有两个 String而不是一个...但它很简单。当然，String比 Box<str> 更易于使用(尽管它多使用了 8 个字节)。

如果您想削减此成本，您可以改用自定义结构:

#[derive(Clone, Debug)]
struct RcStr(Rc<String>);

然后执行Borrow<str>为了它。然后，您将为每个键分配 2 个分配(1 个用于 Rc，1 个用于 String)。取决于你的大小String ，它可能会消耗更少或更多的内存。

---

如果您想更进一步(为什么不呢？)，这里有一些想法:

• 在单个堆分配中实现您自己的引用计数字符串，
• 对插入在 Dictionary 中的切片使用单个竞技场,
• ...