Suggestion: Operator `in` for slices
schveiguy at gmail.com
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