Lecture overview -- Keyboard shortcut: 'u'  Previous page: Sample use of class <b><kbd>Dictionary<K,V></kbd></b> -- Keyboard shortcut: 'p'  Next page: Time complexity overview: Dictionary classes  -- Keyboard shortcut: 'n'  Lecture notes - all slides and notes together  slide -- Keyboard shortcut: 't'  Textbook -- Keyboard shortcut: 'v'  Help page about these notes  Alphabetic index  Course home  Page 28 : 36
Object-oriented Programming in C#
Collection Classes
Notes about Dictionary Classes


  • Class Dictionary<K,V>

    • Based on a hash table

    • Requires that the keys in type K can be compared by an Equals operation

    • Key values should not be mutated

    • The efficiency of class dictionary relies on a good hash function for the key type K

      • Consider overriding the method GetHashCode in class K

    • A dictionary is enumerated in terms of the struct KeyValuePair<K,V>

  • Class SortedDictionary<K,V>

    • Based on a binary search tree

    • Requires an IComparer for keys of type K - for ordering purposes

      • Provided when a sorted dictionary is constructed

  • Class SortedList<K,V>

    • Based on a sorted collection of key/value pairs

      • A resizeable array

    • Requires an IComparer for keys, just like SortedDictionary<K,V>.

    • Requires less memory than SortedDictionary<K,V>.