Simple fast hashing

1

This is adapted from a Reddit thread:

I use hash maps/sets often enough in Rust code, and I'm having troubles trying to avoid the slow&safe built-in hashing scheme.

Where I look for more hashing performance instead of safety, I'd like to replace code like this:

type Set = HashSet<(i32, i32)>;
let mut s = Set::new();

With something similar to this (about 40 extra bytes of simple source
code):

use std::hash::FastHasher;
type Set = HashSet<(i32, i32), FastHasher>;
let mut s = Set::new();

Is something with this level of simplicity & succinctness possible to archive with the future Rust standard library?

2

Have you looked at fnv? You can do something like:

use fnv::FnvHasher;
use std::collections::{HashMap, HashSet};
use std::hash::BuildHasherDefault;

type FnvHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FnvHasher>>;
type FnvHashSet<V> = HashSet<V, BuildHasherDefault<FnvHasher>>;
1 Like
3

Depends on what you mean by "standard library". Due to the stability policy things won't generally be added to std until they have achieved a very high degree of consensus, and there is a lot of design space for a general-purpose hashing library. If I were doing it, I'd use FNV (seems to behave well in practice) with a revised Hash interface that avoids the sentinel on strings when it would be pointless, with a mechanism to estimate the hashing quality and switch to SipHash when chains exceed a length cutoff. Also, in many cases it makes sense to avoid hashing entirely for map sizes under 4 or so; I've written programs in the past where certain map variables are overwhelmingly often size 0-1. Ask nine other Rustaceans and you'll have at least ten opinions. So, this is a job for rust-lang-nursery and/or crates.io; once somebody's general single-threaded map structure reaches critical mass, we could see a push for promoting it to std.

1 Like
4

Or even upgrade existing code like so:

use fnv::FnvHasher;
use std::collections::{HashMap as StdHashMap, HashSet as StdHashSet};
use std::hash::BuildHasherDefault;

type HashMap<K, V> = StdHashMap<K, V, BuildHasherDefault<FnvHasher>>;
type HashSet<V> = StdHashSet<V, BuildHasherDefault<FnvHasher>>;
1 Like