>>>> 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.
>
>
> Why is it logarithmic? If I have a hash table with an array of size 100,
> and I insert 100000 elements into this table, then the best case scenario is
> that all the lists are of length 1000. So, the operation cost is not
> logarithmic but linear with a small constant: 0.01.

Ah, you misunderstood.  By "growing is not an option," I meant one
would therefore use a _different_ Dictionary implementation, such as
one based on a B-Tree, for example.  A dictionary whose
impelementation organizes or chains its associations into linked
lists...

 - Chris