---

Hash maps are a data structure which map keys to values. This is to say that when input a key a hash map is able to retrieve the value associated with that key. A hash map is similar conceptually to a dictionary of words. In fact in some programming languages a hash map is even referred to as a dictionary! For each word in a dictionary one can look up the definition associated with the word. There are also no duplicate words in a dictionary. A hash map is similar to a virtual dictionary. Except for a few differences. The ‘words’ are referred to as ‘keys and the ’definitions’ are referred to as ‘values’. The keys/values are not limited to text and can be any data type representable in memory. Also a key with multiple corresponding values is not allowed in a hash map. It is a one to one mapping. There is however a way to get around this limitation by defining your values as another data structure (such as a list or even another hash map itself). Two key things to keep in mind with hash maps are that the keys must be unique (the values do not have to be) and that a hash maps performance characteristics are very good. Hash maps are often used because they have a good combination of ease of use and performance.

Advantages/Disadvantages of Hash Maps:

Advantages:

• fast performance for adding/removing a key-value pair
• flexible and easy to use, a great go to data structure for various problems
• essential for implementing certain types of algorithms (in particular they can be useful for optimization)
• a data structure that allows you to easily associate keys and values
• checking if a hash map contains a key is much faster then something like an array or list

Disadvantages:

• Complicated to implement (need to understand things like hashing and hash collisions)
• Uses quite a bit more memory then something like an array because both the keys and values have to be stored
• Keys must be unique

Data Structures