Complex Data Structures: Course OverviewCourse Overview

Learn Hash Maps

Learn about hash maps, the efficient key-value storage used in many different programming languages, and then implement one yourself!

Start

Key Concepts

Review core concepts you need to learn to master this subject

hash maps

Hash map underlying data structure

Hash function

hash map only one value

hash maps

# `states` is a Hash Map with state abbreviation keys and state name values.

states = {
  'TN': "Tennessee",
  'CA': "California",
  'NY': "New York",
  'FL': "Florida"
}

west_coast_state = states['CA']

Hash maps are a common data structure used to store key-value pairs for efficient retrieval. A value stored in a hash map is retrieved using the key under which it was stored.

Hash map underlying data structure

# `states` is a Hash Map with state abbreviation keys and state name values.

states = {
  'TN': "Tennessee",
  'CA': "California",
  'NY': "New York",
  'FL': "Florida"
}

west_coast_state = states['CA']

Hash maps are built on top of an underlying array data structure using an indexing system.

Each index in the array can store one key-value pair. If the hash map is implemented using chaining for collision resolution, each index can store another data structure such as a linked list, which stores all values for multiple keys that hash to the same index.

Hash function

# `states` is a Hash Map with state abbreviation keys and state name values.

states = {
  'TN': "Tennessee",
  'CA': "California",
  'NY': "New York",
  'FL': "Florida"
}

west_coast_state = states['CA']

Hash map data structures use a hash function, which turns a key into an index within an underlying array. The hash function can be used to access an index when inserting a value or retrieving a value from a hash map.

hash map only one value

# `states` is a Hash Map with state abbreviation keys and state name values.

states = {
  'TN': "Tennessee",
  'CA': "California",
  'NY': "New York",
  'FL': "Florida"
}

west_coast_state = states['CA']

Each Hash Map key can be paired with only one value. However, different keys can be paired with the same value.

Hash Maps: Conceptual

Lesson 1 of 2

1
A data structure’s main utility is allowing for data to be represented in a way that resembles the way people will use that data. In some cases, the primary function of that data is that it will be…
2
Being a map means relating two pieces of information, but a map also has one further requirement. Let’s consider the following table: | Musician | State of Birth | — | — | |Miles Davi…
3
In the case of a map between two things, we don’t really care about the exact sequence of the data. We only care that a given input, when fed into the map, gives the accurate output. Developing a…
4
A hash function takes a string (or some other type of data) as input and returns an array index as output. In order for it to return an array index, our hash map implementation needs to know the si…
5
You might be thinking at this point that we’ve glossed over a very important aspect of a hash table here. We’ve mentioned that a hash function is necessary, and described some features of what a ha…
6
Now that we have all of the main ingredients for a hash map, let’s put them all together. First, we need some sort of associated data that we’re hoping to preserve. Second, we need an array of a fi…
7
Remember hash functions are designed to compress data from a large number of possible keys to a much smaller range. Because of this compression, it’s likely that our hash function might produce the…
8
A hash map with a linked list separate chaining strategy follows a similar flow to the hash maps that have been described so far. The user wants to assign a value to a key in the map. The hash map …
9
A hash collision resolution strategy like separate chaining involves assigning two keys with the same hash to different parts of the underlying data structure. How do we know which values relate ba…
10
Another popular hash collision strategy is called open addressing. In open addressing we stick to the array as our underlying data structure, but we continue looking for a new index to save our d…
11
There are more sophisticated ways to find the next address after a hash collision, although anything too calculation-intensive would negatively affect a hash table’s performance. Linear probing sys…
12
We’ve learned together what a hash map is and how to create one. Let’s go over the concepts presented in this lesson. A hash map is: - Built on top of an array using a special indexing system. - A…

1
Hash maps are efficient key-value stores. They are capable of assigning and retrieving data in the fastest way possible for a data structure. This is because the underlying data structure that they…
2
The necessary ingredient in the hash map recipe is the hashing function. A hashing function takes a key and returns an index into the underlying array. Hash functions need to be fast to compute s…
3
Hashing functions return a wide range of integers. In order to transform these values into useful indices for our array we need a compression function. A compression function uses modular arithmeti…
4
A data structure that is unable to contain data is a sad sight indeed. We need to put together all the other steps we’ve taken: plug the key into the hash function, plug the hash code into the comp…
5
There is a natural expectation after placing an item into a bag that we will later be able to remove the item from that bag. Otherwise we have created a hole. Let’s implement retrieval for our hash…
6
Since we have the basic functionality of a hash map, let’s create a test instance of one for us to make sure everything works as expected.
7
Our hash and compression functions together can result in collisions. This is when two different keys resolve to the same array index. In our current implementation, all keys that resolve to the sa…
8
When we retrieve hash map values, we also need to be aware of the fact that two keys could point to the same array index.
9
Now we’re going to implement an open addressing system so our hash map can resolve collisions. In open addressing systems, we check the array at the address given by our hashing function. One of th…
10
Now lets use our open addressing scheme in the setter for our HashMap.
11
With everything in our setter taken care of, we want to make sure that when we retrieve our value we’re retrieving the correct value.
12
Now that we have all of the functionality of a Hash Map, it’s time to review what we’ve learned!