Так, требуемый функционал реализован. А теперь поговорим немного о том, как же эти самые хеши считать. В C++ задача хэширования возложена на специализации структуры
std::hash. Для тех типов, которые умеют хэшироваться, соответствующая специализация имеет реализацию
operator(), которая позволяет вызвать
std::hash как функцию. К чему это я? В С++ хэш стандартной библиотеки имеет по одной конкретной хэш-функции на тип. В Rust же ситуация... Несколько сложнее.
В стандартной библиотеке есть трейт
std::hash::Hash (и derive-макрос для него), который определяет единственный (необходимый) метод
hash. Так что же, хэш однозначно определяется типом? Не совсем. Метод
hash — обобщённый, и принимает аргументами
&self и мутабельную ссылку на значение, реализующее трейт
std::hash::Hasher. Этот трейт, в свою очередь, предоставляет набор методов навроде
write_u32 для хэширования примитивов и
write для хэширования слайса байт, а также метод
finish, который возвращает значение типа
u64 — вычисленный хэш. Таким образом, хэширование типа выражено в терминах методов
Hasher — и в этом смысле хэш-функция зависит от типа, ибо это внутри реализации
Hash решается, в каком порядке поля будут хэшированы — но конкретная реализация хэш-функции зависит от типа, реализующего
Hasher. На практике это означает, что вместо того, чтобы довольствоваться некоторой стандартной хэш-функцией по умолчанию (которой для примитивных численных типов, согласно стандарту C++, вполне может быть функция идентичности), программист может выбрать хэш-функцию, которая наилучшим образом подходит для имеющихся данных — и при этом избежать выписывания этой хэш-функции для всех необходимых типов вручную (привет, 0xd34df00d).
Однако в случае хэш-мапы возникает новая задача: для подсчёта хэша нового элемента нам нужен новый, свежий хэшер. Но откуда его взять? Эта задача в стандартной библиотеке Rust делегирована
третьему трейту:
std::hash::BuildHasher. Его единственный метод
build_hasher должен возвращать значение типа
BuildHasher::Hasher, причём эти значения должны вести себя одинаково. Фактически, это фабрика хэшеров. Как и
HashMap из стандартной библиотеки, так и
hashbrown::HashMap параметризованы тремя типами, и этот третий тип — тот самый тип, реализующий
BuildHasher. Так как значение этого типа у каждого экземпляра хэш-мапы может быть своим — и его даже можно предоставить явно при помощи
with_hasher/
with_capacity_and_hasher — это означает, что фактически конкретный экземпляр каждой хэш-мапы потенциально использует свою хэш-функцию (и, кстати, стандартная библиотека для фабрики хэшеров по умолчанию —
std::collections::hash_map::RandomState — именно так в конструкторе и делает, что весьма огорчает некоторых пёселей). Таким образом, чтобы подсчитать хэш ключа так же, как это делает сама мапа, нам нужно получить доступ к build hasher внутри самой мапы — и, к счастью, такой геттер
есть. Его можно написать и для
LockedHashMap, имея при этом в виду те же соображения, что и для типа значения для
find_with_hash:
fn hasher(&self) -> S
where
S: Clone,
{
self.lock_poisonless().hasher().clone()
}
Имея на руках значение типа, реализующего
BuildHasher, уже несложно подсчитать хэш произвольного значения:
fn hash_single<T: Hash, S: BuildHasher>(build_hasher: &S, val: &T) -> u64 {
let mut hasher = build_hasher.build_hasher();
val.hash(&mut hasher);
hasher.finish()
}
(или же использовать
BuildHasher::hash_one, когда его, чёрт побери стабилизируют) и скормить его мапе. В итоге код выглядит как-то так:
let hasher = locked_map.hasher();
// ...
let hash = hash_single(&hasher, &key);
let value = locked_map.find_with_hash(hash, &key);
if let Some(value) = value {
// ...
}
Вот, собственно, и всё. Кода на этот раз совсем немного, но если вдруг кому-то понадобится — вот
гист.
