Как работает этот код?

Есть такой код:
let mut map: HashMap<i32, &str> = HashMap::new();
let entry_enum: Entry<i32, &str> = map.entry(10);
match entry_enum {
    Entry::Occupied(mut entry) => {
        entry.insert("Occupied");
    },
    Entry::Vacant(mut entry) => {
        entry.insert("Vacant");
    }
}

map.entry(10) даёт мне во владение enum, варианты которого содержат изменяемые entry, разве полученное мной enum_entry это не отдельный объект, которым я владею? Если это так, то почему его изменение приводит к изменению хэш-таблицы?
Я понимаю если бы мне давалась мутабельная ссылка на Entry, но я же получаю отдельный объект. Как это работает?
Я попробовал пройтись по исходникам и кажется будто бы под капотом OccupiedEntry и VacantEntry хранят указатель на данные, но вроде как String устроен так-же, но я при этом не могу иметь две переменные типа String которые будут ссылаться на одну и ту же память(разве что через unsafe какой-нибудь, не уж то и тут под капотом такой же трюк?).

В любом случае, почему map.entry(10) не возвращает мутабельную ссылку?
  • Вопрос задан
  • 2038 просмотров
Решения вопроса 1
bingo347
@bingo347
Crazy on performance...
Очень упрощенно 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 нам нужно хранить ещё и ключ, а заодно и хэш (чтоб не считать его снова), а в случае занятой - указатель на бакет (область памяти где храниться пара ключ и значение).
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
@Shaman_RSHU
Ваш вопрос касается внутреннего устройства HashMap в Rust и особенностей работы с переменными и ссылками в Rust. Давайте разберемся, как работает HashMap и почему изменение Entry приводит к изменению хэш-таблицы.
HashMap в Rust хранит пары ключ-значение. Когда вы вызываете map.entry(key), вы получаете Entry, который представляет собой перечисление (enum) с двумя вариантами: Occupied и Vacant. Этот Entry является оберткой над внутренним состоянием HashMap, позволяющей вам безопасно взаимодействовать с элементами хэш-таблицы.
Когда вы вызываете map.entry(key), вы получаете Entry, который является отдельным объектом. Однако, важно понимать, что Entry не является отдельным объектом, который вы владеете в полном смысле владения в Rust. Вместо этого, Entry предоставляет вам доступ к внутренним данным HashMap через безопасный интерфейс.
Изменение Entry и изменение HashMap
Когда вы вставляете значение в Entry с помощью entry.insert(value), вы фактически изменяете внутреннее состояние HashMap. Это происходит потому, что Entry предоставляет вам доступ к внутренним данным HashMap для изменения. Внутренние данные HashMap хранятся в куче, и Entry обеспечивает безопасный доступ к ним.

map.entry(10) возвращает Entry, который предоставляет вам доступ к внутренним данным HashMap для изменения. Это не мутабельная ссылка, потому что Entry не является просто ссылкой на данные. Вместо этого, Entry является оберткой, которая предоставляет безопасный интерфейс для взаимодействия с данными.

Ваше понимание того, что Entry является отдельным объектом, который вы владеете, не совсем точно. Entry предоставляет вам доступ к внутренним данным HashMap для изменения, но не является отдельным объектом, который вы владеете. Изменение Entry приводит к изменению HashMap, потому что Entry обеспечивает безопасный доступ к внутренним данным HashMap.

В Rust, когда вы работаете с переменными и ссылками, важно понимать, что владение и заимствование являются ключевыми концепциями, которые обеспечивают безопасность памяти. В случае с HashMap и Entry, Rust обеспечивает безопасность, предоставляя вам безопасный интерфейс для взаимодействия с внутренними данными.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы