Recently, I’ve been learning a lot about different data structures to use in programs. Many of the common, most applicable, include linked lists, stacks, queues, double linked lists, and symbol tables. In this post I will give a brief overview of symbol tables, also known as dictionaries or hash maps, and provide some instances where symbol tables can greatly improve the quality of your code. When implemented correctly, this simple data type can improve efficiency, code readability, and run time.
What are dictionaries and symbol tables?
In a nutshell, a dictionary is a data type where a key and a value are matched. In order to access a value, you provide a key. To store a value, you map a key to a value. To cycle through all values in the array, you again must use keys. The easiest analogy for understanding how a dictionary works is to use just that: a dictionary.
In both cases described above, both the key and the value can take on any data type. For example, the analogy of a dictionary describes Strings mapped to Strings; however, that’s not always the case. For example, the best data structure for storing birthdays, is a String (the person’s name) mapped to a date type (the person’s birthday). For a frequency table of letters, the letter can be either a character, integer, or String and its values take on the form of integers.
Source: arshajii at stackoverflow.com
General Use Cases and Benefits
I’ve found more and more use cases in the past couple of weeks for dictionaries. It’s often very useful when you have to store a potentially uncapped number of items that aren’t easily mapped to an index of an array. Unlike searching for items within traditional arrays which take linear time, dictionary calls are of constant time.
Sometimes, items either simply cannot be matched to an integer index or prove too complicated to map to an ordered list of integers. Instead, it can be much easier to call values based off of their keys.
Here are a variety of instances where they can used:
- Retrieving data that doesn’t have an order
- Storing data that is faster with a reference key instead of an index
- Matching two different data types - connecting a enum value to an object type
- Pairing opposites so that you can use one to reference the other (“[“ matches to “]”)