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

Question

[Имя]

Есть такой код:

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) не возвращает мутабельную ссылку?

Comments

[mayton2019]

Не специалист в Rust. А что вообще происходит внутри match?
Декодирование строчки? Так это проще делают. Ну идея как-то так

entry.insert(match entry_enum {
    Entry::Occupied(_) => "Occupied",
    Entry::Vacant(_) => "Vacant"
});

Возможно это не скомпилируется но суть я так вижу.

[Имя]

mayton2019, в match изменяется полученная entry

[mayton2019]

Имя, какова ее роль в операции insert?

[Oben]

ИИ:

Сначала создается пустая хэш-таблица map с ключами типа i32 и значениями типа &str.
Затем вызывается метод entry(10) на хэш-таблице map. Этот метод возвращает объект типа Entry, который представляет собой взгляд на одну запись в хэш-таблице. Эта запись может быть либо занятой (Occupied), либо свободной (Vacant).
В вашем случае, если ключ 10 уже существует в хэш-таблице, то возвращается OccupiedEntry, иначе - VacantEntry.
В блоке match вы проверяете, какой тип возвращенного объекта (entry_enum). Если это OccupiedEntry, то вы вставляете новое значение "Occupied" вместо существующего значения. Если это VacantEntry, то вы вставляете новое значение "Vacant" для ключа 10.
Обратите внимание, что вам предоставляется мутабельная ссылка на объект entry, поэтому вы можете изменять его содержимое.
Теперь к вопросу о владении: entry_enum - это не отдельный объект, а просто взгляд на запись в хэш-таблице. Он не владеет данными, а предоставляет доступ к ним. Поэтому изменение значения через entry также изменяет хэш-таблицу.

Что касается String, то он устроен по-другому. String - это динамический буфер, который владеет своим содержимым. Две переменные типа String могут ссылаться на одну и ту же память, потому что они оба владеют этим буфером. В случае &str (который представляет собой срез строки), это не так, и поэтому вы не можете иметь две переменные, которые ссылались бы на одну и ту же память.

Наконец, map.entry(10) не возвращает мутабельную ссылку, потому что это просто взгляд на запись в хэш-таблице. Для получения мутабельной ссылки на значение, вы можете использовать методы or_insert или and_modify на объекте entry.

Answer 1

[Дмитрий Беляев]

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

Answer 2

[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 обеспечивает безопасность, предоставляя вам безопасный интерфейс для взаимодействия с внутренними данными.