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