Давайте продолжим с того места, на котором мы остановились в предыдущей статье. Мы хотим реализовать метод `get_mut()`. Это должно работать так же, как метод get(), но компилятор не позволит нам просто обновлять неизменяемые и изменяемые варианты. Решение состоит в том, чтобы закольцевать записи через итератор, а не перебирать по индексу как делали программисты старой школы. Так как нам нужно начинать с заданного индекса и циклически проходить через весь массив, заканчивая `index — 1`, это само по себе немного сложно, но может быть сделано с помощью метода `Iterator::split_at_mut()`. Смотрите мой предыдущую статью для более подробной информации. Теперь можно окончательно реализовать метод `get_mut()`:
Мы никогда не должны доходить до последней строки метода `get_mut()`, по замыслу. Итерация всегда должна завершаться. Мы гарантируем это, изменив размер нашего массива во время выполнения метода `insert()` позже.
У нас осталось всего два метода: `insert()` и `remove()`. Теперь пришло время обсудить роль варианта `Tombstone` нашего перечисления `Entry`. Наше решение хэш-коллизии состоит в том, чтобы начать с индекса и исследовать цепочку заполненных записей до тех пор, пока мы не найдем совпадающий ключ или пока не достигнем пустой записи, отмечая конец цепочки ключей хэш-коллизии. Если мы найдем соответствующий ключ в середине цепочки и удалим его, пометив её как `Vacant`, то разорвем цепочку на две части. В следующий раз, когда мы будем искать по той же цепочке, мы не сможем искать вторую половину цепочки, так как мы достигнем `Vacant` записи в середине.
Вот почему мы не можем просто удалить запись и пометить ее как `Vacant`. Вариант `Tombstone` дает нам понять, что там ничего нет, но нам все равно нужно продолжить проверять. При этом мы можем реализовать метод `remove()` — если мы найдем запись с совпадающим ключом, мы пометим ее `Tomtsbone` и уменьшим наш счетчик. В противном случае не делаем ни чего. Это звучит просто, но реализация немного сложна в Rust. Давайте сначала реализуем вспомогательный метод, который принимает значение из `Entry`.
С помощью этого можно реализовать метод `remove()`.
У нас остается один последний метод: `insert()`. На высоком уровне этот метод сначала проверяет фактор заполнения и при необходимости изменяет размер массива. После всего этого он вставит в таблицу пару ключ-значение. Давайте создадим вспомогательный метод `insert_helper()`, который выполняет часть вставки, не проверяя фактор заполнения на изменение размера. Нам также нужны методы расчета фактор заполнения и изменения размера.
Метод `load_factor()` прост, но есть один случай — поскольку мы инициализировали хеш-таблицу пустым массивом, мы хотим позаботиться об этом случае явно. Что касается метода `resize()`, мы хотим удвоить размер массива, если только текущий размер не слишком мал. Самая простая реализация — создать новый экземпляр хеш-таблицы и просто вставить каждый элемент из текущей хеш-таблицы, а потом поменять их местами.
Хорошо, у нас остался метод `insert_helper()`. Концептуально это не слишком сложно. Мы проверяем записи и ищем соответствующий ключ. Если значение найдено, перезаписываем его. Если нет, вставляем запись. Не забудьте соответствующим образом обновить счетчики.
Вот и все! Теперь мы завершили реализацию хэш-таблицы в Rust. Вот полный код на Rust playground. Это был долгий путь, но мы многому научились.
В следующей статье я напишу некоторые тестовые и эталонные функции, чтобы измерить, насколько быстро или медленна наша реализация со стандартной библиотекой `std::collections::HashMap`.
Статья на rusty-code.ru