Очень упрощенно HashMap можно представить следующим образом:
pub struct HashMap<K, V> {
table: Table<(K, V)>,
}
struct Table<T> {
// битовая маска занятых ячеек в items
mask: u64,
items: Box<[std::mem::MaybeUninit<Item<T>>; 64]>,
len: usize,
}
struct Item<T> {
data: T,
next: Option<std::ptr::NonNull<Item<T>>>,
}
А Entry так:
pub enum Entry<'a, K, V> {
Vacant(VacantEntry<'a, K, V>),
Occupied(OccupiedEntry<'a, K, V>),
}
pub struct VacantEntry<'a, K, V> {
hash: u64,
key: K,
table: &'a mut Table<(K, V)>,
}
pub struct OccupiedEntry<'a, K, V> {
elem: Bucket<(K, V)>,
table: &'a mut Table<(K, V)>,
}
// указатель на Item.data
struct Bucket<T> {
ptr: std::ptr::NonNull<T>,
}
Как можно заметить у Entry есть лайфтайм, который связывает его с HashMap от которой он создан. А внутри есть мутабельная ссылка с этим лайфтаймом на таблицу с данными HashMap.
Метод entry упрощенно выглядит примерно так:
impl<K, V> HashMap<K, V> {
pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V>
where
K: Eq + std::hash::Hash,
{
use std::hash::Hasher as _;
let mut hasher = self.get_hasher();
key.hash(&mut hasher);
let hash = hasher.finish();
if let Some(elem) = self.table.find(hash, |(k, _)| key == *k) {
Entry::Occupied(OccupiedEntry {
elem,
table: &mut self.table,
})
} else {
Entry::Vacant(VacantEntry {
hash,
key,
table: &mut self.table,
})
}
}
fn get_hasher(&self) -> impl std::hash::Hasher {
todo!()
}
}
impl<T> Table<T> {
fn find(&self, hash: u64, is_match: impl FnMut(&T) -> bool) -> Option<Bucket<T>> {
todo!()
}
}
Как видим мутабельная ссылка всё же есть, только она завернута в структуру, так как одной этой ссылки не достаточно, так как в случае свободной Entry нам нужно хранить ещё и ключ, а заодно и хэш (чтоб не считать его снова), а в случае занятой - указатель на бакет (область памяти где храниться пара ключ и значение).
Простой