What we want to accomplish
Say I have made a fast hashing function and I want to create a FastHashMap type alias that people can use as a drop-in replacement for std::collection::HashMap. The natural (and desireable) syntax for this would be:
pub type FastHashMap<K, V> = HashMap<K, V, FastHasher>;
(see for instance nohash_hasher::IntMap - Rust and fxhash::FxHashMap - Rust)
The problem
Consider this:
fn main() {
let my_map = FastHashMap::with_capacity(32);
expects_my_hash_map(my_map);
}
fn expects_my_hash_map(_map: FastHashMap<i32, f32>) {}
This fails with the following error message:
1 error[E0599]: no function or associated item named `with_capacity` found for struct `HashMap<i32, f32, FastHasher>` in the current scope
--> src/main.rs:29:29
|
29 | let my_map = FastHashMap::with_capacity(32);
| ^^^^^^^^^^^^^ function or associated item not found in `HashMap<i32, f32, FastHasher>`
|
= note: the function or associated item was found for
- `HashMap<K, V>`
This is because HashMap::new and with_capacity are defined so:
impl<K, V> HashMap<K, V, RandomState> {
pub fn new() -> HashMap<K, V, RandomState> {
Default::default()
}
pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState> {
HashMap::with_capacity_and_hasher(capacity, Default::default())
}
}
This means that new/with_capacity is incompatible with other BuildHasher:s. In other words, our FastHashMap cannot be used as a drop-in replacement like we would hope.
See also:
- Add `AHashMap` and `AHashSet` by koute · Pull Request #23 · tkaitchuck/aHash · GitHub
- Does `AHashMap` really need to be a newtype? · Issue #103 · tkaitchuck/aHash · GitHub
Solution that doesn't work
Consider this hypothetical change to std:
impl<K, V, S=RandomState> HashMap<K, V, S>
where S: Default
{
pub fn new() -> HashMap<K, V, S> {
Default::default()
}
pub fn with_capacity(capacity: usize) -> HashMap<K, V, S> {
HashMap::with_capacity_and_hasher(capacity, Default::default())
}
}
This is not legal rust:
error: defaults for type parameters are only allowed in `struct`, `enum`, `type`, or `trait` definitions
= note: `#[deny(invalid_type_param_default)]` on by default
= warning: this was previously accepted by the compiler but is being phased out; it will become a hard error in a future release!
= note: for more information, see issue #36887 <https://github.com/rust-lang/rust/issues/36887>
Solution that does work
Consider this extension trait:
trait HashMapExt {
fn new() -> Self;
fn with_capacity(x: usize) -> Self;
}
impl<K, V, S> HashMapExt for HashMap<K, V, S>
where
K: Hash + Eq,
S: BuildHasher + Default,
{
fn new() -> Self {
HashMap::with_hasher(S::default())
}
fn with_capacity(capacity: usize) -> Self {
HashMap::with_capacity_and_hasher(capacity, S::default())
}
}
By importing this trait into your code, now the original problem is solved:
fn main() {
let std_map = HashMap::with_capacity(32);
expects_std_hash_map(std_map);
let my_map = FastHashMap::with_capacity(32);
expects_my_hash_map(my_map);
}
fn expects_std_hash_map(_map: HashMap<i32, f32>) {}
fn expects_my_hash_map(_map: FastHashMap<i32, f32>) {}
HashMapExt could be made part of the std prelude. It would not break any existing code, but would enable making it easier to make drop-in replacements for std::collection::HashMap that work with new and with_capacity.
In that case it doesn't work because it can't infer a default, and you'd have to be explicit about what type of hasher you want.