Блог*

Так, требуемый функционал реализован. А теперь поговорим немного о том, как же эти самые хеши считать. В 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 {
    // ...
}

Вот, собственно, и всё. Кода на этот раз совсем немного, но если вдруг кому-то понадобится — вот гист.

doc.rust-lang.org

Hash in std::hash - Rust

A hashable type.

1.19K viewsedited 14:43