ListDictionary and HybridDictionary using C Sharp 4.0
ListDictionary uses a singly linked list to store the underlying data. It doesn’t provide
sorting, although it does preserve the original entry order of the items.
ListDictionary is extremely slow with large lists. Its only real “claim to fame” is its
efficiency with very small lists (fewer than 10 items).
HybridDictionary is a ListDictionary that automatically converts to a Hashtable
upon reaching a certain size, to address ListDictionary’s problems with performance.
The idea is to get a low memory footprint when the dictionary is small, and
good performance when the dictionary is large. However, given the overhead in
converting from one to the other—and the fact that a Dictionary is not excessively
heavy or slow in either scenario—you wouldn’t suffer unreasonably by using a
Dictionary to begin with.
Both classes come only in nongeneric form.
Sorted Dictionaries
The Framework provides two dictionary classes internally structured such that their
content is always sorted by key:
• SortedDictionary<TKey,TValue>
• SortedList<TKey,TValue>*
(In this section, we will abbreviate <TKey,TValue> to <,>.)
SortedDictionary<,> uses a red/black tree: a data structure designed to perform
consistently well in any insertion or retrieval scenario.
SortedList<,> is implemented internally with an ordered array pair, providing fast
retrieval (via a binary-chop search) but poor insertion performance (because existing
values have to be shifted to make room for a new entry).
SortedDictionary<,> is much faster than SortedList<,> at inserting elements in a
random sequence (particularly with large lists). SortedList<,>, however, has an extra
ability: to access items by index as well as by key. With a sorted list, you can go
directly to the nth element in the sorting sequence (via the indexer on the Keys/
Values properties). To do the same with a SortedDictionary<,>, you must manually
enumerate over n items. (Alternatively, you could write a class that combines a sorted
dictionary with a list class.)
None of the three collections allows duplicate keys (as is the case with all
dictionaries).
The following example uses reflection to load all the methods defined in
System.Object into a sorted list keyed by name, and then enumerates their keys
and values:
// MethodInfo is in the System.Reflection namespace
* There’s also a functionally identical nongeneric version of this called SortedList.
var sorted = new SortedList <string, MethodInfo>();
foreach (MethodInfo m in typeof (object).GetMethods())
sorted [m.Name] = m;
foreach (string name in sorted.Keys)
Console.WriteLine (name);
foreach (MethodInfo m in sorted.Values)
Console.WriteLine (m.Name + " returns a " + m.ReturnType);
Here’s the result of the first enumeration:
Equals
GetHashCode
GetType
ReferenceEquals
ToString
Here’s the result of the second enumeration:
Equals returns a System.Boolean
GetHashCode returns a System.Int32
GetType returns a System.Type
ReferenceEquals returns a System.Boolean
ToString returns a System.String
Notice that we populated the dictionary through its indexer. If we instead used the
Add method, it would throw an exception because the object class upon which we’re
reflecting overloads the Equals method, and you can’t add the same key twice to a
dictionary. By using the indexer, the later entry overwrites the earlier entry, preventing
this error.
You can store multiple members of the same key by making each
value element a list:
SortedList <string, List<MethodInfo>>
Extending our example, the following retrieves the MethodInfo whose key is "GetHash
Code", just as with an ordinary dictionary:
Console.WriteLine (sorted ["GetHashCode"]); // Int32 GetHashCode()
So far, everything we’ve done would also work with a SortedDictionary<,>. The
following two lines, however, which retrieve the last key and value, work only with
a sorted list:
Console.WriteLine (sorted.Keys [sorted.Count - 1]); // ToString
Console.WriteLine (sorted.Values[sorted.Count - 1].IsVirtual); // True
