std::collections::HashMap, which are known to be not the fastest, as they are meant to be general purpose, and thus need to be cryptographically secure
Not cryptographically secure, but “hash DoS” secure.
Definition: allow both well-behaved and malicious clients to interact with your hashmap (inserts, lookups, possibly removals). The actions of malicious clients MUST NOT be able to catastrophically impair the performance of well-behaved clients.
This means taking a worse average case in exchange for a better worst case.
Thanks for the clarification. I’ve taken “cryptographically secure” from the fxhash documentation, which explicitly states that it isn’t that, but haven’t looked deeper into what that means.
There’s “it should be intractable to produce an input that hashes to a desired value, or to produce multiple inputs that has to the same value” (cryptographic security to preimage and collision attacks), which are properties of a hash function, and there’s “someone shouldn’t be able to craft a set of inputs that has a drastic effect on the amount of CPU/storage that we use to process them” (e.g. by mounting a collision attack which puts everything into the same bucket), which is a property of a hash-based data structure.
In theory you can get the desired property of data structures by using a cryptographically-secure hash function, but in practice that isn’t done much. Instead you use a less-secure hash function that’s orders of magnitude faster, together with some other cleverness in the data structure implementation, such as automatically rekeying to a new random seed when an imbalance is detected, or using probing/insertion algorithms which have strong worst-case guarantees even at the cost of a somewhat worse average case.
Not cryptographically secure, but “hash DoS” secure.
Definition: allow both well-behaved and malicious clients to interact with your hashmap (inserts, lookups, possibly removals). The actions of malicious clients MUST NOT be able to catastrophically impair the performance of well-behaved clients.
This means taking a worse average case in exchange for a better worst case.
Thanks for the clarification. I’ve taken “cryptographically secure” from the fxhash documentation, which explicitly states that it isn’t that, but haven’t looked deeper into what that means.
There’s “it should be intractable to produce an input that hashes to a desired value, or to produce multiple inputs that has to the same value” (cryptographic security to preimage and collision attacks), which are properties of a hash function, and there’s “someone shouldn’t be able to craft a set of inputs that has a drastic effect on the amount of CPU/storage that we use to process them” (e.g. by mounting a collision attack which puts everything into the same bucket), which is a property of a hash-based data structure.
In theory you can get the desired property of data structures by using a cryptographically-secure hash function, but in practice that isn’t done much. Instead you use a less-secure hash function that’s orders of magnitude faster, together with some other cleverness in the data structure implementation, such as automatically rekeying to a new random seed when an imbalance is detected, or using probing/insertion algorithms which have strong worst-case guarantees even at the cost of a somewhat worse average case.