>> This discussion has limited its context to comparing *in-memory*
>> Dictionary implementations, where open-addressing has an advantage.
>> Using Magma reveals another context where chained Dictionary's can have
>> some advantages:  When they're large, persistent, and shared in a multi-user
>> system -- e.g., when grow rehashing is not an option.
>
>
> B-trees were designed for that use case.
> If growing is not an option, then your dictionary's performance will degrade
> as its size increases, won't it?

Yes, but only logarithmically.  But I was not making a
performance-based comparison, only a possibility-based one.

>> Not only do chained Dictionary's make that scenario possible, they improve
>> the concurrency -- different users can add/change/remove from the Dictionary
>> as long as they occur at different keys.  With regular
>> Dictionary's, concurrency guarantees a commit conflict.
>
> If you created a new, larger dictionary on grow and lazily copied the
> entries from the smaller to the larger upon access, then I think you could
> use open addressing hash tables.

That's an interesting idea, but what if it grows beyond "the larger"
again while still many entries in the smaller?  Add a third which is
doubled in size again?  That sounds like it starts to intrude into the
efficiency of open-addressing (both computation and space), but the
idea still sparks some interesting design thoughts in my head..

> Also, I don't see the concurrency issue with open addressing, because as
> long as different users modify different chains, the case of concurrency is
> the same as what you described, isn't it?

Magma has a class called "MagmaPreallocatedDictionary" which does
exactly this.  It's like a regular Dictionary, except for its internal
'array', it utilizes a MagmaArray, which is just like an Array except
large and persistent and can grow in place (so able to maintain its
identity).

However, this alone was not enough to implement your proposal because
of the 'tally'.  Clients would each be trying to propose their
specific value for that variable = conflict.  Thankfully, Magma has
yet another special class called MagmaCounter which fits that role
beautifully.  Designed for multi-user systems, a MagmaCounter provides
a concurrent counter.  Instances start at a #value of 0, after which
any number of sessions may simultaneously increment or decrement (even
by more than 1), but no one can actually hard set its value.

Best,
  Chris