Pre-RFC: bless the `type FastHashMap` pattern

[Centril]

Deterministic hashing has perfectly valid usecases (see: rustc and reproducible builds)

And for const fn / CTFE down the line which cannot (for obvious reasons) permit non-determinism in them.

[josh]

Deterministic hashing has perfectly valid usecases (see: rustc and reproducible builds).

Note that for such use cases, you want to sort the hash table when serializing it or enumerating its contents. Even if the hash table doesn’t depend on runtime randomness, you have no guarantee that the algorithm will remain the same in the future.

[kestred]

like NaiveHashMap .

This option has the added … (benefit, I think) that users of chrono (e.g. NaiveDate), will already be familiar with the “potentially incorrect” / “situation-ally useful” trade-off in naming. (Chrono currently being the 51st crate by most downloads); I like it for that and that there aren’t any other connotations that came to mind for me.

Plain “naive” is the more common English spelling, but if you think that’s troublesome, we can keep looking…

Supporting notes on the topic of spelling “naive”:

1. All of the Oxford, Mirriam Webster, and Cambridge dictionaries contain both spellings.
2. For obvious historical reasons Naive is more common in code.

[graydon]

Yeah, I would at least experiment with trying to make it adapt to attack before deciding on this. It’s not even statistical collision resistance you’re going to be missing, just attack resistance. If you can catch an attack early (i.e. if you can define “imbalance” rigorously enough) and switch to SIP or something, then you might as well start with xxhash as it’s a speed champ and has perfectly good statistical properties on non-hostile inputs.

As for determinism, it seems to me that a with_seed operation that you can provide a constant seed to ought to do?

[josh]

(At the risk of bikeshedding, isn’t seahash faster than xxhash?)

[graydon]

Hah, learn something every day (two things actually, counting that license!)

I just wanted to nip the “FNV” thing in the bud

[Centril]

As for determinism, it seems to me that a with_seed operation that you can provide a constant seed to ought to do?

This should work including for CTFE; the actual RandomState::build_hasher is possible to make into a const fn; the only source of randomness that cannot be const fn is RandomState::new() and that should be replaceable in your with_seed operation fairly easily.

[nestordemeure]

What about PredictibleHashMap ? It highlights the property that makes it both faster and vulnerable to attack without seeming too attractive for people who have not read the documentation that explains the issue in details.

[zslayton]

Setting aside the choice of adjective for a moment, I’d like to suggest creating a submodule to house the new flavors of each constructor. That way, instead of:

HashMap::new()
HashMap::with_capacity()
HashMap::fast()

You could have:

HashMap::new() 
HashMap::with_capacity(16)
HashMap::fast::new()
HashMap::fast::with_capacity(16)

[cuviper]

HashMap is a type, not a module – it can’t contain submodules.

[zslayton]

Oops – I was thinking of std::collections::hash_map, not HashMap. However, then the constructor wouldn’t be associated with the type itself, which is no good. My mistake.

[Pratyush]

If we’re still looking for names, I’d like to suggest DetHashMap, for deterministic. In the context of non-cryptographic hash functions, determinism usually implies vulnerability to collisions. The docs for HashMap and DetHashMap can clarify that DetHashMap is usually faster.

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.