www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Question about associative arrays

reply "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.
Jan 06 2009
parent 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.
Jan 06 2009