Is D associative array thread safe, and will it relocate memory when add or delete a value?

[Steven Schveighoffer]

On Wed, 07 Dec 2011 04:00:34 -0500, Jonathan M Davis <jmdavisProg at gmx.com>  
wrote:

> On Wednesday, December 07, 2011 09:10:16 Martin Nowak wrote:
>> On Wed, 07 Dec 2011 08:59:32 +0100, raojm <raojm at 91ne.com> wrote:
>> > Is D associative array  thread safe, and  will it relocate memory when
>> > add or delete a value?
>> >
>> > Where I can find the implemention.
>>
>> No it's not, and yes it has to relocate memory.
>> It's working as a hashtable not a binary tree, so all
>> pointers will be invalidated by adding/removing.
>> https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d
>
> Yeah. AFAIK, it's impossible to have a hash table which doesn't risk
> reallocating something when adding a value to it, unless you limit how  
> many
> elements it can hold or somesuch, which would make it considerably less
> useful. Typically, when a hash table gets full enough, it rehashes  
> itself,
> which definitely involves allocating more memory, and possible  
> reallocating a
> large portion of what it's already allocated. So, there's no way that an  
> AA
> can avoid the risk of reallocating when elements are added to it, pretty  
> much
> regardless of its implementation. It's an attribute of the data  
> structure.

dcollections' HashMap does not invalidate cursors when adding data, even  
when a rehash is done.  The rehash routine specifically is written to make  
this possible.

However, it does invalidate ranges.

Note that for any hash implementation, the only thing that needs to be  
reallocated is the bucket array.  In many implementations, this is not  
where the data is stored.

-Steve