Давайте продолжим с того места, на котором мы остановились в предыдущей статье. Мы хотим реализовать метод get_mut(). Это должно работать так же, как метод get(), но компилятор не позволит нам просто обновлять неизменяемые и изменяемые варианты. Решение состоит в том, чтобы закольцевать записи через итератор, а не перебирать по индексу как делали программисты старой школы. Так как нам нужно начинать с заданного индекса и циклически проходить через весь массив, заканчивая index — 1, это само по себе немного сложно, но может быть сделано с помощью метода Iterator::split_at_mut(). Смотрите мой предыдущую статью для более подробной информации. Теперь можно окончательно реализовать метод get_mut():
--- before
+++ after
@@ -15,6 +15,11 @@ pub struct HashMap<Key, Val> {
}
impl<Key: Eq + Hash, Val> HashMap<Key, Val> {
+ fn iter_mut_starting_at(&mut self, idx: usize) -> impl Iterator<Item = &mut Entry<Key, Val>> {
+ let (s1, s2) = self.xs.split_at_mut(idx);
+ s2.iter_mut().chain(s1.iter_mut())
+ }
+
fn get_index<Q>(&self, key: &Q) -> usize
where
Key: Borrow<Q>,
@@ -70,7 +75,22 @@ impl<Key: Eq + Hash, Val> HashMap<Key, Val> {
Key: Borrow<Q>,
Q: Eq + Hash,
{
- todo!()
+ if self.len() == 0 {
+ return None;
+ }
+ let idx = self.get_index(key);
+ for entry in self.iter_mut_starting_at(idx) {
+ match entry {
+ Entry::Vacant => {
+ return None;
+ }
+ Entry::Occupied { key: k, val } if (k as &Key).borrow() == key => {
+ return Some(val);
+ }
+ _ => {}
+ }
+ }
+ panic!("fatal: unreachable");
}
pub fn remove<Q>(&mut self, key: &Q) -> Option<Val>Мы никогда не должны доходить до последней строки метода get_mut(), по замыслу. Итерация всегда должна завершаться. Мы гарантируем это, изменив размер нашего массива во время выполнения метода insert() позже.
У нас осталось всего два метода: insert() и remove(). Теперь пришло время обсудить роль варианта Tombstone нашего перечисления Entry. Наше решение хэш-коллизии состоит в том, чтобы начать с индекса и исследовать цепочку заполненных записей до тех пор, пока мы не найдем совпадающий ключ или пока не достигнем пустой записи, отмечая конец цепочки ключей хэш-коллизии. Если мы найдем соответствующий ключ в середине цепочки и удалим его, пометив её как Vacant, то разорвем цепочку на две части. В следующий раз, когда мы будем искать по той же цепочке, мы не сможем искать вторую половину цепочки, так как мы достигнем Vacant записи в середине.
Вот почему мы не можем просто удалить запись и пометить ее как Vacant. Вариант Tombstone дает нам понять, что там ничего нет, но нам все равно нужно продолжить проверять. При этом мы можем реализовать метод remove() — если мы найдем запись с совпадающим ключом, мы пометим ее Tomtsbone и уменьшим наш счетчик. В противном случае не делаем ни чего. Это звучит просто, но реализация немного сложна в Rust. Давайте сначала реализуем вспомогательный метод, который принимает значение из Entry.
--- before
+++ after
@@ -1,6 +1,7 @@
use std::borrow::Borrow;
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
+use std::mem::swap;
enum Entry<Key, Val> {
Vacant,
@@ -8,6 +9,23 @@ enum Entry<Key, Val> {
Occupied { key: Key, val: Val },
}
+impl<Key, Val> Entry<Key, Val> {
+ fn take(&mut self) -> Option<Val> {
+ match self {
+ Self::Occupied { key, val } => {
+ let mut occupied = Self::Tombstone;
+ swap(self, &mut occupied);
+ if let Self::Occupied { key, val } = occupied {
+ Some(val)
+ } else {
+ panic!("fatal: unreachable");
+ }
+ }
+ _ => None,
+ }
+ }
+}
+С помощью этого можно реализовать метод remove().
--- before
+++ after
pub fn remove<Q>(&mut self, key: &Q) -> Option<Val>
where
Key: Borrow<Q>,
Q: Eq + Hash,
{
- todo!()
+ if self.len() == 0 {
+ return None;
+ }
+ let idx = self.get_index(key);
+ let mut result = None;
+ for entry in self.iter_mut_starting_at(idx) {
+ match entry {
+ Entry::Occupied { key: k, .. } if (k as &Key).borrow() == key => {
+ result = entry.take();
+ break;
+ }
+ Entry::Vacant => {
+ result = None;
+ break;
+ }
+ _ => {}
+ }
+ }
+ result.map(|val| {
+ self.n_occupied -= 1;
+ val
+ })
}
}У нас остается один последний метод: insert(). На высоком уровне этот метод сначала проверяет фактор заполнения и при необходимости изменяет размер массива. После всего этого он вставит в таблицу пару ключ-значение. Давайте создадим вспомогательный метод insert_helper(), который выполняет часть вставки, не проверяя фактор заполнения на изменение размера. Нам также нужны методы расчета фактор заполнения и изменения размера.
--- before
+++ after
@@ -33,6 +33,18 @@ pub struct HashMap<Key, Val> {
}
impl<Key: Eq + Hash, Val> HashMap<Key, Val> {
+ fn load_factor(&self) -> f64 {
+ todo!()
+ }
+
+ fn resize(&mut self) {
+ todo!()
+ }
+
+ fn insert_helper(&mut self, key: Key, val: Val) -> Option<Val> {
+ todo!()
+ }
+
fn iter_mut_starting_at(&mut self, idx: usize) -> impl Iterator<Item = &mut Entry<Key, Val>> {
let (s1, s2) = self.xs.split_at_mut(idx);
s2.iter_mut().chain(s1.iter_mut())
@@ -61,7 +73,11 @@ impl<Key: Eq + Hash, Val> HashMap<Key, Val> {
}
pub fn insert(&mut self, key: Key, val: Val) -> Option<Val> {
- todo!()
+ if self.load_factor() >= 0.75 {
+ self.resize();
+ }
+
+ self.insert_helper(key, val)
}
pub fn get<Q>(&self, key: &Q) -> Option<&Val>Метод load_factor() прост, но есть один случай — поскольку мы инициализировали хеш-таблицу пустым массивом, мы хотим позаботиться об этом случае явно. Что касается метода resize(), мы хотим удвоить размер массива, если только текущий размер не слишком мал. Самая простая реализация — создать новый экземпляр хеш-таблицы и просто вставить каждый элемент из текущей хеш-таблицы, а потом поменять их местами.
--- before
+++ after
@@ -1,7 +1,8 @@
use std::borrow::Borrow;
+use std::cmp::max;
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
-use std::mem::swap;
+use std::mem::{swap, take};
enum Entry<Key, Val> {
Vacant,
@@ -34,11 +35,27 @@ pub struct HashMap<Key, Val> {
impl<Key: Eq + Hash, Val> HashMap<Key, Val> {
fn load_factor(&self) -> f64 {
- todo!()
+ if self.xs.is_empty() {
+ 1.0
+ } else {
+ 1.0 - self.n_vacant as f64 / self.xs.len() as f64
+ }
}
fn resize(&mut self) {
- todo!()
+ let new_size = max(64, self.xs.len() * 2);
+ let mut new_table = Self {
+ xs: (0..new_size).map(|_| Entry::Vacant).collect(),
+ n_occupied: 0,
+ n_vacant: new_size,
+ };
+ for entry in take(&mut self.xs) {
+ if let Entry::Occupied { key, val } = entry {
+ new_table.insert_helper(key, val);
+ }
+ }
+
+ swap(self, &mut new_table);
}
fn insert_helper(&mut self, key: Key, val: Val) -> Option<Val> {Хорошо, у нас остался метод insert_helper(). Концептуально это не слишком сложно. Мы проверяем записи и ищем соответствующий ключ. Если значение найдено, перезаписываем его. Если нет, вставляем запись. Не забудьте соответствующим образом обновить счетчики.
--- before
+++ after
@@ -11,6 +11,16 @@ enum Entry<Key, Val> {
}
impl<Key, Val> Entry<Key, Val> {
+ fn replace(&mut self, mut x: Val) -> Option<Val> {
+ match self {
+ Self::Occupied { key, val } => {
+ swap(&mut x, val);
+ Some(x)
+ }
+ _ => None,
+ }
+ }
+
fn take(&mut self) -> Option<Val> {
match self {
Self::Occupied { key, val } => {
@@ -59,7 +69,26 @@ impl<Key: Eq + Hash, Val> HashMap<Key, Val> {
}
fn insert_helper(&mut self, key: Key, val: Val) -> Option<Val> {
- todo!()
+ let idx = self.get_index(&key);
+ let mut result = None;
+ for entry in self.iter_mut_starting_at(idx) {
+ match entry {
+ Entry::Occupied { key: k, .. } if (k as &Key).borrow() == &key => {
+ result = entry.replace(val);
+ break;
+ }
+ Entry::Vacant => {
+ *entry = Entry::Occupied { key, val };
+ break;
+ }
+ _ => {}
+ }
+ }
+ if result.is_none() {
+ self.n_occupied += 1;
+ self.n_vacant -= 1;
+ }
+ result
}
fn iter_mut_starting_at(&mut self, idx: usize) -> impl Iterator<Item = &mut Entry<Key, Val>> {Вот и все! Теперь мы завершили реализацию хэш-таблицы в Rust. Вот полный код на Rust playground. Это был долгий путь, но мы многому научились.
В следующей статье я напишу некоторые тестовые и эталонные функции, чтобы измерить, насколько быстро или медленна наша реализация со стандартной библиотекой std::collections::HashMap.