Associative Arrays max length? 32bit/64bit

[Steven Schveighoffer via Digitalmars-d]

On Sat, 17 May 2014 16:18:07 -0400, FG <home at fgda.pl> wrote:

> On 2014-05-17 21:35, bearophile wrote:
>> FG:
>>
>>> and don't forget the extra memory needed to store the tree for fast  
>>> key look-up in the hash array.
>>
>> I think D now uses a linked list for the collision chains (so opCmp is  
>> useless, despite it's still required for the hashing protocol).
>
> Indeed, I just read  
> https://github.com/D-Programming-Language/dmd/blob/master/src/backend/aa.c

This is dmd's source, not druntime. This is the representation of AA's in  
the compiler, not in your code. The appropriate code for druntime is here:

https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d

> Key hash is divided modulo the number of buckets and each bucket points  
> to an ordered double-linked list. That list is walked left or right  
> depending on what value Typeinfo::compare returns for two keys. Hmm...  
> isn't opCmp used by that function? Why useless?

No, in that DMD file, the bucket is a tree, not a doubly-linked list.  
opCmp is not used in D's AA. The D implementation used to mirror DMD, but  
it does not any more.

It may be used for CTFE, I'm not sure.

-Steve