Pre-RFC: bless the `type FastHashMap` pattern

81

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

82

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.

1 Like
83

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.

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.
7 Likes
84

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?

2 Likes
85

(At the risk of bikeshedding, isnā€™t seahash faster than xxhash?)

86

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

I just wanted to nip the ā€œFNVā€ thing in the bud :slight_smile:

87

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.

88

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.

1 Like
89

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)
90

HashMap is a type, not a module ā€“ it canā€™t contain submodules.

91

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.

92

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.

1 Like
93

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