Что происходит в этом коде?

Как работает получение объекта enum_entry, содержащего изменяемые entry, когда используется метод map.entry(10)? Почему enum_entry значительно отличается от обычных мутабельных ссылок и как именно это реализовано в коде?
  • 18 апреля 2024 г. 21:40
Ответы на вопрос 2
В данном коде создается объект HashMap<Integer, String>, который содержит пары ключ-значение, где ключами являются целочисленные значения, а значениями - строки.

Путем использования метода map.entrySet() получаем набор объектов типа Map.Entry, содержащих пары ключ-значение из данного HashMap. Затем выбираем объект enum_entry с ключом равным 10 с помощью метода map.entry(10). 

enum_entry в данном случае представляет объект типа MutableObject, который содержит изменяемую ссылку на значение (в данном случае строку), связанное с ключом 10 в HashMap. Это отличается от обычных ссылок на значения, так как MutableObject позволяет изменять значение, на которое указывает ссылка, не изменяя саму ссылку.

Реализация MutableObject в данном коде основана на оболочке, которая хранит ссылку на объект и позволяет изменять его значение через метод setValue(). Таким образом, при обновлении значения в MutableObject, это изменение сразу же отражается и в HashMap, так как MutableObject хранит ссылку на объект в HashMap.

Итак, использование MutableObject позволяет создать изменяемую ссылку на значение в HashMap, что позволяет удобно обновлять значения в коллекции, не изменяя саму коллекцию.
Очень упрощенно 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 нам нужно хранить ещё и ключ, а заодно и хэш (чтоб не считать его снова), а в случае занятой - указатель на бакет (область памяти где храниться пара ключ и значение).
Похожие вопросы