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

Как работает получение объекта 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 можно представить следующим образом: <pre><code class="rust">pub struct HashMap&lt;K, V&gt; {
    table: Table&lt;(K, V)&gt;,
}

struct Table&lt;T&gt; {
    // битовая маска занятых ячеек в items
    mask: u64,
    items: Box&lt;[std::mem::MaybeUninit&lt;Item&lt;T&gt;&gt;; 64]&gt;,
    len: usize,
}

struct Item&lt;T&gt; {
    data: T,
    next: Option&lt;std::ptr::NonNull&lt;Item&lt;T&gt;&gt;&gt;,
}</code></pre> <br/> <br/> А Entry так: <pre><code class="rust">pub enum Entry&lt;'a, K, V&gt; {
    Vacant(VacantEntry&lt;'a, K, V&gt;),
    Occupied(OccupiedEntry&lt;'a, K, V&gt;),
}

pub struct VacantEntry&lt;'a, K, V&gt; {
    hash: u64,
    key: K,
    table: &amp;'a mut Table&lt;(K, V)&gt;,
}

pub struct OccupiedEntry&lt;'a, K, V&gt; {
    elem: Bucket&lt;(K, V)&gt;,
    table: &amp;'a mut Table&lt;(K, V)&gt;,
}

// указатель на Item.data
struct Bucket&lt;T&gt; {
    ptr: std::ptr::NonNull&lt;T&gt;,
}</code></pre> <br/> <br/> Как можно заметить у Entry есть лайфтайм, который связывает его с HashMap от которой он создан. А внутри есть мутабельная ссылка с этим лайфтаймом на таблицу с данными HashMap. <br/> Метод entry упрощенно выглядит примерно так: <pre><code class="rust">impl&lt;K, V&gt; HashMap&lt;K, V&gt; {
    pub fn entry&lt;'a&gt;(&amp;'a mut self, key: K) -&gt; Entry&lt;'a, K, V&gt;
    where
        K: Eq + std::hash::Hash,
    {
        use std::hash::Hasher as _;
        let mut hasher = self.get_hasher();
        key.hash(&amp;mut hasher);
        let hash = hasher.finish();

        if let Some(elem) = self.table.find(hash, |(k, _)| key == *k) {
            Entry::Occupied(OccupiedEntry {
                elem,
                table: &amp;mut self.table,
            })
        } else {
            Entry::Vacant(VacantEntry {
                hash,
                key,
                table: &amp;mut self.table,
            })
        }
    }

    fn get_hasher(&amp;self) -&gt; impl std::hash::Hasher {
        todo!()
    }
}

impl&lt;T&gt; Table&lt;T&gt; {
    fn find(&amp;self, hash: u64, is_match: impl FnMut(&amp;T) -&gt; bool) -&gt; Option&lt;Bucket&lt;T&gt;&gt; {
        todo!()
    }
}</code></pre> <br/> Как видим мутабельная ссылка всё же есть, только она завернута в структуру, так как одной этой ссылки не достаточно, так как в случае свободной Entry нам нужно хранить ещё и ключ, а заодно и хэш (чтоб не считать его снова), а в случае занятой - указатель на бакет (область памяти где храниться пара ключ и значение).
Похожие вопросы