Associative Arrays max length? 32bit/64bit

FG via Digitalmars-d digitalmars-d at puremagic.com
Sat May 17 14:32:12 PDT 2014


On 2014-05-17 22:30, bearophile wrote:
> Sorry, I didn't know the linked list is sorted. It's scanned sequentially, because you can't use a binary search on a regular linked list. Perhaps a skiplist is better to avoid O(n^2) behavour in presence of attacks or degenerate cases (in past the AA used a tree there).

     if (nodes > buckets_length * 4) rehash();

Skiplist doesn't seem necessary. As seen above, there shouldn't be much of a problem with long lists accumulating in some selected buckets, as long as the hash function is a proper hash (i.e. for any set of x (especially consecutive ones like 0, 1, ... n) hash(x) values cover the range of size_t evenly).


More information about the Digitalmars-d mailing list