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

Question

我HashMap使用默认值实现了换行,我想知道它是否安全.

当get被调用时,内部映射可以被调整大小和值(与先前获得的参考文献get)将被指向无效地址.我尝试使用"计算机科学中的所有问题都可以通过另一层次的间接解决"的想法来解决这个问题(Butler Lampson).我想知道这个技巧是否使这段代码安全.

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));
}

(游乐场)

Answer 1

因为你不能在¹突变从返回的值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]:从技术上讲,如果您的默认值包含内部可变性,则会有不同的行为.在这种情况下,对整个集合应用默认值的修改.如果这是一个问题,您需要使用更接近原始解决方案.