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