Firstly, I suspect that your requirement "when receiving a key that is not on the card, by default in this key" is not required!
Consider indispensable access let foo = default_hash_map[bar] + 123; . If you are not going to use values with internal volatility with the map, this may not be relevant if default_hash_map[bar] actually creates a key or simply returns a link to a single default value .
Now, if you really need to create new records during access, then there is a way to do this. The borrower check restriction, which allows you to add new records with variable access, is here to stop you from creating dangling pointers that will occur whenever you change the map while holding links there. But if you used a structure with stable links, where stable means that the links are not invalid when entering new entries into the structure, then the problem that checks are trying to prevent will disappear.
In C ++, I would think of using deque , which is guaranteed by the standard, so as not to strip its links when you add new entries to it. Unfortunately, Rust deques are different (although you can probably find boxes for arena distributors with properties similar to C ++ deque), and so I use Box for this example. The values in the box are separately on the heap and do not move when new entries are added to the HashMap .
Now your regular access template is likely to modify the new entries and then access the existing map entries. Thus, creating new entries in Index::index is an exception and should not slow down the rest of the map. Therefore, it makes sense to pay the boxing price only for access to Index::index . To do this, we can use the second structure, which stores only the values in the Index::index box.
Knowing that HashMap<K, Box<V>> can be inserted without canceling the existing V referees, allows us to use it as a temporary buffer, maintaining the Index::index -created values until we get the opportunity to synchronize them with the main HashMap .
use std::borrow::Borrow; use std::cell::UnsafeCell; use std::collections::HashMap; use std::hash::Hash; use std::ops::Index; use std::ops::IndexMut; struct DefaultHashMap<K, V>(HashMap<K, V>, UnsafeCell<HashMap<K, Box<V>>>, V); impl<K, V> DefaultHashMap<K, V> where K: Eq + Hash { fn sync(&mut self) { let buf_map = unsafe { &mut *self.1.get() }; for (k, v) in buf_map.drain() { self.0.insert(k, *v); } } } impl<'a, K, V, Q: ?Sized> Index<&'a Q> for DefaultHashMap<K, V> where K: Eq + Hash + Clone, K: Borrow<Q>, K: From<&'a Q>, Q: Eq + Hash, V: Clone { type Output = V; fn index(&self, key: &'a Q) -> &V { if let Some(v) = self.0.get(key) { v } else { let buf_map: &mut HashMap<K, Box<V>> = unsafe { &mut *self.1.get() }; if !buf_map.contains_key(key) { buf_map.insert(K::from(key), Box::new(self.2.clone())); } &*buf_map.get(key).unwrap() } } } impl<'a, K, V, Q: ?Sized> IndexMut<&'a Q> for DefaultHashMap<K, V> where K: Eq + Hash + Clone, K: Borrow<Q>, K: From<&'a Q>, Q: Eq + Hash, V: Clone { fn index_mut(&mut self, key: &'a Q) -> &mut V { self.sync(); if self.0.contains_key(key) { self.0.get_mut(key).unwrap() } else { self.0.insert(K::from(key), self.2.clone()); self.0.get_mut(key).unwrap() } } } fn main() { { let mut dhm = DefaultHashMap::<String, String>(HashMap::new(), UnsafeCell::new(HashMap::new()), "bar".into()); for i in 0..10000 { dhm[&format!("{}", i % 1000)[..]].push('x') } println!("{:?}", dhm.0); } { let mut dhm = DefaultHashMap::<String, String>(HashMap::new(), UnsafeCell::new(HashMap::new()), "bar".into()); for i in 0..10000 { let key = format!("{}", i % 1000); assert!(dhm[&key].len() >= 3); dhm[&key[..]].push('x'); } println!("{:?}", dhm.0); } {
( playground )
Please note that boxing only stabilizes the insertion of new records. To remove pasted records, you still need a modified ( &mut self ) access to DefaultHashMap .