2) Data Structures Lesson

Hash Maps

8 min to complete · By Jon Fincher

Now that you have an idea of what a hash function is, you can use it to implement two new data structures -- the hash table and the hash map. These are closely related structures, with one key difference that you will see as you go along. You start with the more basic hash table.

What is a Hash Table

A hash table is a data structure that uses a hash function to generate an index for data being stored. The hash value is often an integer, which is used as an index into a fixed-size array.

The two primary problems to be solved when implementing a hash table are determining a good hash function and how hash collisions will be handled. Some languages provide hash functions and values, which can greatly simplify or even replace your hash functions. It is up to you to manage collisions, as there is a chance of losing data due to collisions.

Note that hash tables are different from the related structure, the hash map.

What is a Hash Map

A hash map, also called an associative array or dictionary, is a structure that stores two pieces of data: a key, and the value associated with that key. Hash maps use a hash function to generate an index based on the key and store both the key and the data value in a hash table. The user can retrieve the data by providing the key.

A simple example of a key-data value store is an old-fashioned phone book. In the phone book example, a person's name would be the "key" and their phone number would be the "data value".

Hash maps differ from hash tables in two key ways:

  1. Each key in a hash map is unique. You cannot store two pieces of data in a hash map using the same key. Think of the key as an index into an array -- you cannot store two pieces of data in the same array location.
  2. Because of this, adding an identical key-value pair into a hash map results in the old data being replaced by the new data.

Why Use a Hash Map

Hash maps are useful when you can identify a good key for each data value. For example, your email address is used to log on to the CodingNomads website, and this key is used to access your user data, including your full name, access to lessons, and progress through individual units.

Use cases for a Hash Map

As mentioned above, storing user data keyed by a user name or email address is a great application for a hash map.

Hash maps can be used to implement word-counting applications. Using the words as keys, the number of times each word appears can be stored as data.

Hash maps can also be used to implement a data structure called a sparse array or sparse matrix. A sparse array is one in which most of the elements are zero. Instead of creating a large array or matrix to store relatively few numbers, you can use the indexes of where the data is stored as the key in a hash map to store the data. This reduces memory pressure and can increase performance.

Benefits of a Hash Map

Hash maps often use memory more efficiently than other structures. They are also often quicker, as the time required to calculate the hash function is usually much faster than performing a linear or binary search over the data.

Big O Analysis

Big O data is dependent on the hash function being used. As mentioned above, many languages provide hash values or functions, which can bring the cost of computation down to $`O(1)`$ based on the length of the key.

Depending on how collisions are managed, overall performance may be as slow as $`O(n)`$, but $`n`$ will be much smaller. On average, $`n`$ can be re-calculated as the size of the dataset divided by the size of the array in which the hash table is stored.

Terminology

  • Hash table: A structure that uses hash functions to provide an index into an underlying storage structure, usually an array.
  • Hash map: A structure that stores a key-value pair in an underlying hash table structure. The key is used to reference the data and to provide the hash value for the hash table.
  • Key: A user-defined piece of data used to reference a larger set of data.
  • Dictionary: A Python term for a hash map.
  • Associative Array: A generic term for a hash map.
  • Sparse Matrix: Any array, single or multi-dimensional, in which most entries are zero.

Summary: Hash Maps

Hash maps and hash tables use hash functions to store and retrieve data efficiently. They are used to store large amounts of data, using a small part of the data as input to a hash function. The result of the hash function is used as the key to locate the actual data.