Suggestion: Operator `in` for slices

Paul Backus 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 
wrote:
> 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:

https://github.com/dlang/druntime/blob/v2.098.1/src/rt/aaA.d#L17-L27

So, we can safely put this discussion to rest, I think.


More information about the Digitalmars-d mailing list