• Tim M (2/2) Jan 06 2009 Do the associative arrays work using the real key or a hash of it and if...
• dsimcha (11/13) Jan 06 2009 The builtin AAs in DMD are implemented as hash tables, although IIRC thi...

"Tim M" <a b.com> writes:

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.

dsimcha <dsimcha yahoo.com> writes:

== Quote from Tim M (a 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.