Suggestion: Operator `in` for slices

[Steven Schveighoffer]

On 12/19/21 6:45 AM, Ola Fosheim Grøstad wrote:
> Now, if AA was implemented as a hashtable with a constant upper-bound on 
> the linked lists (say 100) then we could say that "in" would be O(1).

D AAs do not use linked lists any more. It uses open addressing. But 
having a bound on how many collisions can happen is ineffective against 
a bad hash function (say, one that always returns 0).

The expectation of the hash table is that the hash function is good. 
Without a good hash function, the complexity goes to crap.

> 
> We could also claim that inserts would be O(1) amortized (ignore 
> rehashing, assuming a distribution that is relatively flat).

That is what we claim (and what hash algorithms in general claim). 
amortized O(1) lookups and inserts.

-Steve