Реализация в Rust - хэш-таблица часть 1

Posted on:10 июля 2023 г. at 09:07

Example Dynamic OG Image link Давайте внедрим структуру данных хэш-таблицы в Rust. Хэш-таблицы невероятно важны в структурах данных благодаря их эффективности и универсальности. Реализуя её с нуля, мы сможем получить представление о лежащих в его основе алгоритмах и структурах данных. Мало того, у нас также будет шанс улучшить наши навыки Rust.

Говоря об алгоритме, мы собираемся реализовать исследование линейной адресации хэш-таблицы. Есть и другие варианты, но я думаю, что с этого, проще начать.

Я возьму подход сверху вниз, где мы начинаем с абстракций более высокого уровня и идем к абстракциям и реализациям более низкого уровня. Начнем с самой высокой абстракции: API. Мы, пока не хотим поддерживать весь API стандартной библиотеки Rust std::collections::HashMap. Для начала давайте построим его до основных функциональных возможностей.

use std::borrow::Borrow;
use std::hash::Hash;

pub struct HashMap<Key, Val> {
    // todo
}

impl<Key: Eq + Hash, Val> HashMap<Key, Val> {
    pub fn new() -> Self {
        todo!()
    }

    pub fn len(&self) -> usize {
        todo!()
    }

    pub fn insert(&mut self, key: Key, val: Val) -> Option<Val> {
        todo!()
    }

    pub fn get<Q>(&self, key: &Q) -> Option<&Val>
    where
        Key: Borrow<Q>,
        Q: Eq + Hash,
    {
        todo!()
    }

    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut Val>
    where
        Key: Borrow<Q>,
        Q: Eq + Hash,
    {
        todo!()
    }

    pub fn remove<Q>(&mut self, key: &Q) -> Option<Val>
    where
        Key: Borrow<Q>,
        Q: Eq + Hash,
    {
        todo!()
    }
}

Если вы уже знакомы с алгоритмом хеш-таблицы, не стесняйтесь идти вперед и попробуйте реализовать его самостоятельно. Методы имеют ту же самое название, что и в стандартной библиотеке HashMap. В двух словах API Borrow позволяет, например, передавать &str или &String в хэш-таблицу типа String.

Хеш-таблица — это, по сути, массив элементов, индекс которого является хеш-значением ключа по модулю размера массива. Мы, естественно, будем использовать Vec<T> для этого массива, но что за тип T? Давайте назовем его Entry и подумаем о том, что Entry должен реализовывать. Мы знаем, что occupied может быть как пустым, так и содержать данные. Когда передаем данные, они должны содержать как Key, так и Val. Для поддержки метода remove() нам нужно третье состояние: Tombstone. Это состояние представляет собой запись, которая когда-то была занята, но в настоящее время пуста. Мы поговорим о том, зачем нам нужно такое различие, позже, а пока вот наша вспомогательная структура:

enum Entry<Key, Val> {
    Vacant,
    Tombstone,
    Occupied { key: Key, val: Val },
}

Нам нужны два свойства usize для хэш-таблицы - одно для отслеживания занятых записей и другое для отслеживания свободных записей. Первое свойство - это то, что мы возвращаем для метода len(). Второе свойство позволяет нам решить, когда изменять размер массива. С помощью этого мы можем добавить некоторые детали реализации в наш скелет:

--- before
+++ after
@@ -1,17 +1,29 @@
 use std::borrow::Borrow;
 use std::hash::Hash;

+enum Entry<Key, Val> {
+    Vacant,
+    Tombstone,
+    Occupied { key: Key, val: Val },
+}
+
 pub struct HashMap<Key, Val> {
-    // todo
+    xs: Vec<Entry<Key, Val>>,
+    n_occupied: usize,
+    n_vacant: usize,
 }

 impl<Key: Eq + Hash, Val> HashMap<Key, Val> {
     pub fn new() -> Self {
-        todo!()
+        Self {
+            xs: Vec::new(),
+            n_occupied: 0,
+            n_vacant: 0,
+        }
     }

     pub fn len(&self) -> usize {
-        todo!()
+        self.n_occupied
     }

Теперь пришло время написать какой-нибудь вспомогательный метод - нам нужен метод, который вычисляет значение хэш из ключа и применяет размер массива по модулю для получения индекса.

--- before
+++ after
@@ -1,5 +1,6 @@
 use std::borrow::Borrow;
-use std::hash::Hash;
+use std::collections::hash_map::DefaultHasher;
+use std::hash::{Hash, Hasher};

 enum Entry<Key, Val> {
     Vacant,
@@ -14,6 +15,16 @@ pub struct HashMap<Key, Val> {
 }

 impl<Key: Eq + Hash, Val> HashMap<Key, Val> {
+    fn get_index<Q>(&self, key: &Q) -> usize
+    where
+        Key: Borrow<Q>,
+        Q: Eq + Hash,
+    {
+        let mut hasher = DefaultHasher::new();
+        key.hash(&mut hasher);
+        hasher.finish() as usize % self.xs.len()
+    }
+
     pub fn new() -> Self {
         Self {
             xs: Vec::new(),

Теперь реализуем метод get(). Все, что нам нужно сделать, это выполнить итерацию по записям, начинающимся с индекса, и сравнить ключи, до тех пор, пока не будет найдено совпадение или пока мы не столкнемся с вакантной записью. Во время поиска мы просто игнорируем и пропускаем записи с tombstone.

--- before
+++ after
     pub fn get<Q>(&self, key: &Q) -> Option<&Val>
     where
         Key: Borrow<Q>,
         Q: Eq + Hash,
     {
-        todo!()
+        if self.len() == 0 {
+            return None;
+        }
+        let mut idx = self.get_index(key);
+        loop {
+            match &self.xs[idx] {
+                Entry::Vacant => {
+                    break None;
+                }
+                Entry::Occupied { key: k, val } if k.borrow() == key => {
+                    break Some(val);
+                }
+                _ => {
+                    idx = (idx + 1) % self.xs.len();
+                }
+            }
+        }
     }

     pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut Val>

Отлично, это было не совсем плохо. Теперь мы можем сделать то же самое с методом get_mut()? Если вы просто обновите неизменяемые объекты до изменяемых, вы получите несколько ошибок компилятора (Rust playground). Исправление требует немного более долгих изменений. Для этого я продолжу в следующей истории.