Key Concepts

Review core concepts you need to learn to master this subject

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 Maps: Conceptual
Lesson 1 of 2
  1. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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…

What you'll create

Portfolio projects that showcase your new skills

Pro Logo

How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory

Pro Logo