...

...

...

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