I used ListDictionary (under the Systm.Collections.Specialized namespace) a little while back. I eventually came to grips with the documentation but something just kept eating away at me in its description.
"Implements IDictionary using a singly linked list. Recommended for collections that typically contain 10 items or less."
"This is a simple implementation of IDictionary using a singly linked list. It is smaller and faster than a Hashtable if the number of elements is 10 or less...Items in a ListDictionary are not in any guaranteed order; code should not depend on the current order. The ListDictionary is implemented for fast keyed retrieval; the actual internal order of items is implementation-dependent and could change in future versions of the product."
The first quote was fine. An arbitrary cutoff number was specified to stress the point about keeping your collection size relatively small. So then 15 should be on the small side as well? After you read the second quote, it almost sounds like it HAS to be 10 or less to be faster than a Hashtable. However, based on my understanding of a singly linked-list, there is no constraint that states that there is a severe drop off in performance when you exceed a size of 10 and go to 11. There does not appear to be an analogous discrete cutoff/constraint to performance as there is for primitive arrays and allocation of space. (i.e. if you developed an object in a framework that was implemented as an array of size 10. If you added an 11th element, it would have to handle this by reallocating a size greater than that. NOTE: this is not a good example/practice of how a framework would be implemented - read "Framework Design Guidelines" by Krzysztof Cwalina & Brad Abrams for a good reference on Framework Design).
Knowing that there were no fundamental explanations, a few rough benchmark tests were performed (rough - hence, there are no graphs to show the results) to compare ListDictionary and Hashtable. Also, it would be interesting to see what happens for small numbers and to determine whether there is a discrete cutoff at a size of 10. Basically, only one operation (add) was measured. As you know a linked list addition operation is O(n) vs. a hashtable's O(1). However, there could be cryptographic hash functions that are slow. Once performing the tests (creating 100,000 data structures and calling the add operations n times), you quickly realize that there is no cutoff value of 10. Even when n = 20, you generally see ~10% advantage of using a ListDictionary over a Hashtable. It is when you reach n = 23 that it becomes too close to call. At a size of 30, a Hashtable is ahead and subsequently at 100, that would be considered a "large" size. (Again, these were very rough tests. To conduct a more accurate test, you need to set this up no differently than an experiment.)
Lastly, the latter part of the second quote from MSDN docs throws you a little off guard. So the ListDictionary is not in guaranteed order? But it stated earlier that it was implemented as a unidirectional linked-list. Then it goes on to state that the implementation could change in future version of the product. So referring back to .NET 1.1 docs (MSDN site vs. MSDN2), the implementation was identical to .NET 2.0 with the same warning about future versions. I suppose their rationale is that it implements IDictionary and thus you should not be depending on the order of addition (just like other data structures like Hashtable). Perhaps this really was their intention (as opposed to purely giving ppl a heads up that it will change for .NET vNext) and only the wording of the document was somewhat misleading.
CONCLUSION:
In any case, if you want the best of both worlds, you can use a class called HybridDictionary. It uses a ListDictionary for small collections and switches to a Hashtable for large collections.
"If the initial size of the collection is greater than the optimal size for a ListDictionary, the collection is stored in a Hashtable to avoid the overhead of copying elements from the ListDictionary to a Hashtable."
Using Reflector to examine System.Collections.Specialized.HybridDictionary, you will be able to see that once you have added (this.list.Count + 1) >= 9, a private ChangeOver method is called to switch the data structure from a ListDictionary to a HashTable.
If anyone has any concrete explanations to the topics discussed in this blog entry regarding ListDictionary, I would love to hear them (esp the rationale if it is believed that there is a discrete cutoff at 10). People doing internet searches on this topic will find that there is not much discussion regarding this.