Type sequence concatenation / associative array implementation

[Steven Schveighoffer]

On 2/12/20 5:47 PM, Paul Backus wrote:
> On Wednesday, 12 February 2020 at 20:58:49 UTC, Marcel wrote:
>> 2- How is the builtin associative array implemented? I think I read 
>> somewhere it's implemented like C++'s std::unordered_map but with BSTs 
>> instead of DLists for handling collisions: is this correct?
> 
> It's an open-addressed hash table. If you want to see all the details, 
> the source is here:
> 
> https://github.com/dlang/druntime/blob/v2.090.1/src/rt/aaA.d

For some background, collisions used to be handled via a BST, which 
required all AA keys to provide opCmp in addition to opEquals and toHash.

It was changed some time ago (maybe like 8 years ago? Can't remember) to 
be open addressed hash, thus removing the requirement for opCmp.

This is probably why you read something about the old implementation 
using BST.

-Steve