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