Suggestion: Operator `in` for slices

Steven Schveighoffer schveiguy at
Tue Dec 21 17:02:22 UTC 2021

On 12/19/21 2:34 PM, 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).

Please see existing research, this is not a new concept.


More information about the Digitalmars-d mailing list