如何使用默认值为HashMap编写安全包装

我用默认值实现了HashMap的包装，我想知道它是否安全。

当调用get时，可以调整内部映射的大小，并且以前对值的引用（使用get获得）将指向无效地址。我试图用"计算机科学中的所有问题都可以通过另一种间接方法来解决"的想法来解决这个问题（巴特勒·兰普森）。我想知道这个技巧是否使这个代码安全。

use std::cell::UnsafeCell;
use std::collections::HashMap;
use std::hash::Hash;
pub struct DefaultHashMap<I: Hash + Eq, T: Clone> {
    default: T,
    map: UnsafeCell<HashMap<I, Box<T>>>,
}
impl<I: Hash + Eq, T: Clone> DefaultHashMap<I, T> {
    pub fn new(default: T) -> Self {
        DefaultHashMap {
            default: default,
            map: UnsafeCell::new(HashMap::new()),
        }
    }
    pub fn get_mut(&mut self, v: I) -> &mut T {
        let m = unsafe { &mut *self.map.get() };
        m.entry(v).or_insert_with(|| Box::new(self.default.clone()))
    }
    pub fn get(&self, v: I) -> &T {
        let m = unsafe { &mut *self.map.get() };
        m.entry(v).or_insert_with(|| Box::new(self.default.clone()))
    }
}
#[test]
fn test() {
    let mut m = DefaultHashMap::new(10usize);
    *m.get_mut(4) = 40;
    let a = m.get(4);
    for i in 1..1024 {
        m.get(i);
    }
    assert_eq!(a, m.get(4));
    assert_eq!(40, *m.get(4));
}

（游乐场）

由于您不能¹更改从get返回的值，因此当值丢失时，我只会返回对默认值的引用。但是，当您调用get_mut时，您可以将该值添加到映射中，并返回对新添加值的引用。

这样做的好处是不需要任何unsafe代码。

use std::{borrow::Borrow, collections::HashMap, hash::Hash};
pub struct DefaultHashMap<K, V> {
    default: V,
    map: HashMap<K, V>,
}
impl<K, V> DefaultHashMap<K, V>
where
    K: Hash + Eq,
    V: Clone,
{
    pub fn new(default: V) -> Self {
        DefaultHashMap {
            default,
            map: HashMap::new(),
        }
    }
    pub fn get_mut(&mut self, v: K) -> &mut V {
        let def = &self.default;
        self.map.entry(v).or_insert_with(|| def.clone())
    }
    pub fn get<B>(&self, v: B) -> &V
    where
        B: Borrow<K>,
    {
        self.map.get(v.borrow()).unwrap_or(&self.default)
    }
}
#[test]
fn test() {
    let mut m = DefaultHashMap::new(10usize);
    *m.get_mut(4) = 40;
    let a = m.get(4);
    for i in 1..1024 {
        m.get(i);
    }
    assert_eq!(a, m.get(4));
    assert_eq!(40, *m.get(4));
}

[1] ：从技术上讲，如果您的默认值包含内部可变性，这将具有不同的行为。在这种情况下，对默认值的修改将应用于整个集合。如果这是一个问题，您需要使用更接近原始解决方案。

我认为这里的借用规则涵盖了您。

在这里应用可变异或别名原理，如果您可以将多个路径保持为相同的值并同时对某些内容进行变异，就会出现不安全的情况。

然而，在您的情况下：

虽然内部HashMap甚至可以通过对DefaultHashMap的可别名引用进行变异，但没有人对HashMap本身有引用
虽然有对Box的引用，但这里不可能擦除Box，因此这里没有悬空指针
由于要注意保留借用关系（即&mut T只能通过&mut DefaultHashMap获得），因此不可能有&mut T和别名

因此，您的简短示例看起来是安全的，但要特别小心，不要意外地在&DefaultHashMap上引入一个允许修改现有值的方法，因为这将是一条通往悬挂指针的捷径。

就我个人而言，我会用Option<String>执行所有测试。

相关内容

最新更新

热门标签：