[squeak-dev] [Pharo-dev] Why do we have SmallDictionary?

Chris Muller asqueaker at gmail.com
Mon Jul 2 02:24:09 UTC 2018

>>>> 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

 - Chris

More information about the Squeak-dev mailing list