Question about associative arrays

[dsimcha]

== Quote from Tim M (a at b.com)'s article
> Do the associative arrays work using the real key or a hash of it and if
> it's a hash then what does it do to prevent hash collisions.

The builtin AAs in DMD are implemented as hash tables, although IIRC this is not
guaranteed by the spec and other implementations may use, for example, red-black
trees.

In the current implementation, these work by using an array of pointers to (key,
value, next*) structs.  To find the slot in the array where a given key would be
located, a hash is computed.  If a given key is present, it is guaranteed to be
linked to the array index corresponding to its hash.  Then, the implementation
searches all elements linked to this array index until the key requested is found.

The bottom line is that hashes are used to find the array index to start looking
in, in O(1) time, and then the actual keys are used to resolve any collisions.