Pre-RFC: bless the `type FastHashMap` pattern

[glaebhoerl]

“self-evident”

Yes, my intent by this was just that without prior knowledge you can read the name and parse it into words whose independent meanings you understand. I don’t know what a better word for this is, do you?

“Legible” maybe?

[josh]

Rather than bikeshedding the name for a “faster but insecure” hash, could we revisit the question of whether we need one?

Suppose we have a hash table that switches from “fast but insecure hash” to “reasonably fast and secure hash” if and only if it detects collision attacks (based on the length of the longest chain compared to the number of elements in the table)? If we had that, under what circumstances would we ever need the one that stays “fast but insecure” forever? Bear in mind that the two would only differ in cases where the hash table algorithm is being attacked to produce collisions and the hash table is devolving into a linked list, in which case your performance is tanking anyway.

[tspiteri]

That may be a good compromise between fast and secure, but will it guarantee deterministic behaviour? The first paragraph of the original post does list non-deterministic behaviour as one of the two costs of the default hashing algorithm.

[cuviper]

Suppose we have a hash table that switches from “fast but insecure hash” to “reasonably fast and secure hash” if and only if it detects collision attacks (based on the length of the longest chain compared to the number of elements in the table)?

How feasible is this to implement? Presumably you want this to be the behavior for the default S = RandomState which produces DefaultHasher. I suppose you’d need some internal trait which no-ops this logic for most BuildHasher types, and specializes RandomState to upgrade to a secure hasher?

[josh]

It’s a pain to do in a way that’s compatible with the existing hash map types (with their pluggable hashing), though it should still be quite possible. I’d love to see a patch implementing that.

[Gankro]

It’s super easy to add adaptive hashing to the current system. You just toss a default-implemented try_upgrade(&mut self) -> Result<(), ()> { Err(()) } method on BuildHasher (or maybe Hasher? same diff design-wise) that HashMap calls when it “detects” degeneracy. If Ok() is yielded it rebuilds and rehashes everything.

Since all impls of try_upgrade will statically always yield Ok or Err, in practice this should be statically compiled out for any hashing implementation that doesn’t support the feature.

[Gankro]

Followup that became too long for a reasonable edit:

The real burden of adaptive hashing is proving out heuristics and benchmarking everything to make a convincing argument for its adoption. The current system, and the proposed FastHashMap type, has obvious characteristics, so it’s a simple change we can make to make writing performant/deterministic Rust code a little bit better out of the box.

Also regardless of adaptive hashing there is still a desire for non-deterministic/deterministic dichotomy. Deterministic hashing has perfectly valid usecases (see: rustc and reproducible builds). But having non-deterministic hashing by default avoids users accidentally relying on things that we don’t guarantee (see: JS was forced to guarantee objects behave like linked hashmaps for iteration because people were just dumping them into ordered drop downs).

edit: also for full information pczarn is interested in re-investigating an adaptive hashing impl

[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.