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 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
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
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
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.
- 1A 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…
- 2Being 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…
- 3In 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…
- 4A 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…
- 5You 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…
- 6Now 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…
- 7Remember 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…
- 8A 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 …
- 9A 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…
- 10Another 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…
- 11There 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…
- 12We’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…
- 1Hash 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…
- 2The 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…
- 3Hashing 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…
- 4A 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…
- 5There 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…
- 6Since 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.
- 7Our 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…
- 8When we retrieve hash map values, we also need to be aware of the fact that two keys could point to the same array index.
- 9Now 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…
- 10Now lets use our open addressing scheme in the setter for our HashMap.
- 11With everything in our setter taken care of, we want to make sure that when we retrieve our value we’re retrieving the correct value.
- 12Now that we have all of the functionality of a Hash Map, it’s time to review what we’ve learned!
What you'll create
Portfolio projects that showcase your new skills
How you'll master it
Stress-test your knowledge with quizzes that help commit syntax to memory
Learn Hash Maps
Start