Давайте внедрим структуру данных хэш-таблицы в Rust. Хэш-таблицы невероятно важны в структурах данных благодаря их эффективности и универсальности. Реализуя её с нуля, мы сможем получить представление о лежащих в его основе алгоритмах и структурах данных. Мало того, у нас также будет шанс улучшить наши навыки Rust.
Говоря об алгоритме, мы собираемся реализовать исследование линейной адресации хэш-таблицы. Есть и другие варианты, но я думаю, что с этого, проще начать.
Я возьму подход сверху вниз, где мы начинаем с абстракций более высокого уровня и идем к абстракциям и реализациям более низкого уровня. Начнем с самой высокой абстракции: API. Мы, пока не хотим поддерживать весь API стандартной библиотеки Rust` std::collections::HashMap`. Для начала давайте построим его до основных функциональных возможностей.
Если вы уже знакомы с алгоритмом хеш-таблицы, не стесняйтесь идти вперед и попробуйте реализовать его самостоятельно. Методы имеют ту же самое название, что и в стандартной библиотеке `HashMap`. В двух словах API Borrow позволяет, например, передавать `&str` или `&String` в хэш-таблицу типа String.
Хеш-таблица — это, по сути, массив элементов, индекс которого является хеш-значением ключа по модулю размера массива. Мы, естественно, будем использовать `Vec<T>` для этого массива, но что за тип `T`? Давайте назовем его Entry и подумаем о том, что Entry должен реализовывать. Мы знаем, что `occupied` может быть как пустым, так и содержать данные. Когда передаем данные, они должны содержать как `Key`, так и `Val`. Для поддержки метода `remove()` нам нужно третье состояние: `Tombstone`. Это состояние представляет собой запись, которая когда-то была занята, но в настоящее время пуста. Мы поговорим о том, зачем нам нужно такое различие, позже, а пока вот наша вспомогательная структура:
Нам нужны два свойства `usize` для хэш-таблицы - одно для отслеживания занятых записей и другое для отслеживания свободных записей. Первое свойство - это то, что мы возвращаем для метода `len()`. Второе свойство позволяет нам решить, когда изменять размер массива. С помощью этого мы можем добавить некоторые детали реализации в наш скелет:
Теперь пришло время написать какой-нибудь вспомогательный метод - нам нужен метод, который вычисляет значение хэш из ключа и применяет размер массива по модулю для получения индекса.
Теперь реализуем метод `get()`. Все, что нам нужно сделать, это выполнить итерацию по записям, начинающимся с индекса, и сравнить ключи, до тех пор, пока не будет найдено совпадение или пока мы не столкнемся с вакантной записью. Во время поиска мы просто игнорируем и пропускаем записи с `tombstone`.
Отлично, это было не совсем плохо. Теперь мы можем сделать то же самое с методом `get_mut()`? Если вы просто обновите неизменяемые объекты до изменяемых, вы получите несколько ошибок компилятора (Rust playground). Исправление требует немного более долгих изменений. Для этого я продолжу в следующей истории.
Статья на rusty-code.ru
