How to use sets in D?

[H. S. Teoh]

On Thu, Feb 10, 2022 at 12:53:08AM +0000, Siarhei Siamashka via Digitalmars-d-learn wrote:
> On Wednesday, 9 February 2022 at 21:05:47 UTC, Siarhei Siamashka wrote:
> > Is the current implementation of associative arrays in D language
> > resistant to Denial of Service hash collision attacks?
> 
> Answering to myself. No, it isn't. Here's a simple example:
[...]
> ulong[] generate_bad_array(ulong n)
> {
>     return iota(n).map!(x => (x << 46)).array;
> }
[...]
> == adversarially constructed array ==
> n=100000, unique_elements=100000, assoc time: 22626 ms, rbtree time: 15 ms
> ```

Nice investigation!  This should be filed as a bug.

I remember browsing through various hash functions in druntime before
(built-in AA's use per-type hash functions), and many of them were
trivial, which would imply that it's trivial to construct adversarial
input that triggers a large number of collisions for various basic
types.


T

-- 
Give me some fresh salted fish, please.