Suggestion: Operator `in` for slices

Steven Schveighoffer schveiguy at
Sun Dec 19 18:36:12 UTC 2021

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.


More information about the Digitalmars-d mailing list