Suggestion: Operator `in` for slices
snarwin at gmail.com
Wed Dec 22 14:27:32 UTC 2021
On Sunday, 19 December 2021 at 19:34:18 UTC, Ola Fosheim Grøstad
> On Sunday, 19 December 2021 at 18:36:12 UTC, Steven
> Schveighoffer wrote:
>> That is what we claim (and what hash algorithms in general
>> claim). amortized O(1) lookups and inserts.
> Yes, if you don't shrink.
> You need to prove that the claim holds for all possible
> orderings of inserts, deletions and lookups.
> So you need to prove that you always do O(N) operations between
> rehashing, so you get O(N) operations of complexity O(1) + one
> rehash of complexity O(N) = O(N).
To guarantee amortized O(1) deletion, it is sufficient to ensure
that `shrink_threshold * growth_factor < growth_threshold`. And
if you look at the source code for D's built-in AAs, you will see
that this is, in fact, ensured:
So, we can safely put this discussion to rest, I think.
More information about the Digitalmars-d