HashTable, ListDictionary, and HybridDictionary

HashTable is ideal for creating lookup tables because it can very quickly find the value of an item from a large collection of items based on the item’s key. However, it may become an overkill if the collection is relatively small, say about 10 items or less, because of the overhead of HashTable. In this case, ListDictionary is a better choice than HashTable. ListDictionary is a simple implementation of IDictionary with a singly linked list. It is smaller and faster than a HashTable if the number of elements is small (<=10). When the number of elements increases, however, ListDictionary will impede performance, and HashTable becomes a better choice. But what if you don’t know the number of elements in advance? It’s when HybridDictionary comes in.

HybridDictionary works like this:

When the size of the collection is smaller than the optimal size for a ListDictionary, HybridDictionary will use ListDictionary for its implementation; but if the size of the collection is greater than the optimal size , HybridDictionary will switch to HashTable automatically for its implementation. What is the optimal size of a collection? Although MSDN says ListDictionary is recommended for a collection with 10 items or less, the optimal size is NOT 10 in HybridDictionary class. By using Reflector you will find the optimal size is actually 8! When the size of a collection is greater than or equal to 9, HybridDictionary will first call “ChangeOver” method to copy items from ListDictionary to HashTable, and then will destroy the ListDictionary instance and start using HashTable for the rest items. Here is the “Add” method in the HybridDictionary class:

Public Sub Add(ByVal key As Object, ByVal value As Object)
  If (Not Me.hashtable Is Nothing) Then
     Me.hashtable.Add(key, value)
  ElseIf (Me.list Is Nothing) Then
     Me.list = New ListDictionary(IIf(Me.caseInsensitive, _
                                        HybridDictionary.Comparer, Nothing))
     Me.list.Add(key, value)
  ElseIf ((Me.list.Count + 1) >= 9) Then
     Me.ChangeOver
     Me.hashtable.Add(key, value)
  Else
     Me.list.Add(key, value)
  End If
End Sub

Here is the “ChangeOver” method:

Private Sub ChangeOver()
  Dim enumerator As IDictionaryEnumerator = Me.list.GetEnumerator
  If Me.caseInsensitive Then
     Me.hashtable = New Hashtable(13, HybridDictionary.HashCodeProvider, _
                                               HybridDictionary.Comparer)
  Else
     Me.hashtable = New Hashtable(13)
  End If
  Do While enumerator.MoveNext
     Me.hashtable.Add(enumerator.Key, enumerator.Value)
  Loop
  Me.list = Nothing
End Sub

So the rule of thumb is to use ListDictionary if the size of the collection is less than 10, to use HashTable if the size is greater than 10, and to use HybridDictionary if the size is unknown or might change later on.