CSE 212: Programming with Data Structures

Learning Activity: Maps

Overview

The map data structure is similar to the set in many ways. The main difference is that sets store values. Maps, on the other hand, store key-value pairs. The key is used to lookup or find the value.

Maps are one of the most used and most important data structures you will learn about in this course.

Making the Map from the Set

The map is most commonly viewed as a table. In the map below, the first column contains a unique value called the key. The second column contains a value (not necessarily unique) called the value. The keys form a set because all the keys are unique. A map is created in software by associating a value with each item in the key set. In the picture below, the table shows the key and value pairs. The keys are hashed into what looks like a set. The values are then stored with each key value.

Maps in C#

The performance of the map is the same for the set. Some programming languages call this a HashTable or a HashMap. In C#, it is called a Dictionary. The dictionary (like the set) is an object where you define your key data type and your value data type when you define your dictionary:

var dictionary = new Dictionary<string, double>();

or

var dictionary = new Dictionary<string, double>() { { "key1", 2.1 }, { "key2", 2.3 } };

Notice that you must specify the datatype of both the key and the value in angle brackets <> when you declare the Dictionary. For example, for example, Dictionary<string, double> defines a dictionary that has strings for keys and doubles for values.

Objects are Maps

Whenever you create a class in any programming language, you are creating a map. Each member variable or property on the class can be considered a key, with the value being stored in that variable. Consider the following code:

class PersonDataMapping
{
    public string FirstName { get; set; }
    public string LastName { get; set; }
    public double Age { get; set; }
}

The PersonDataMapping class maps the key of "FirstName" with the first name of the person. The lookup and access time is O(1) because the compiler knows the order and type of the variables and can jump to that part of the memory without caring how much additional data belongs to the PersonDataMapping class.

Complex Map Data

Mapping data using keys and values has been a standard among the Internet almost since the beginning. Consider the following example which is data that was received from a website about the location of the International Space Station. This data is called JSON (JavaScript Object Notation) data and is a common data format. JSON data is nothing more than a map of maps.

{
  "timestamp": 1584638006, 
  "message": "success", 
  "iss_position": {
    "longitude": -149.9053,
    "latitude": -35.9225
  }
}

If we wanted to create a mapping for this complex data, we can create custom classes to map the data appropriately:

class SpaceStation
{
    public long Timestamp { get; set; }
    public string Message { get; set; }
    public Location IssPosition { get; set; }
}

class Location
{
    public double Longitude { get; set; }
    public double Latitude { get; set; }
}

An instance of the SpaceStation class is essentially a map where the keys are fixed when the program is built. This does require that you know the format of the data (including all of the value data types) before creating the class.

Once we read the JSON data from the server, we could use a JsonSerializer.Deserialize() method to convert the raw JSON data into the class object.

var spaceStation = JsonSerializer.Deserialize<SpaceStation>(json);
var lon = spaceStation.IssPosition.Longitude;
var lat = spaceStation.IssPosition.Latitude;
Console.WriteLine($"Space Station at Lon: {lon} Lat: {lat}");

Notice how IssPosition is a key in the SpaceStation object. The value for this is another object Location. To get the Longitude key, we have to go through the IssPosition using the . notation twice.

Here is another example of data that was received about the number of people that are in space.

JSON:

{
  "people": [
    { "craft": "ISS", "name": "Andrew Morgan" }, 
    { "craft": "ISS", "name": "Oleg Skripochka" }, 
    { "craft": "ISS", "name": "Jessica Meir" }
  ], 
  "message": "success", 
  "number": 3
}  

C#:

class Space
{
    public Person[] People { get; set; }
    public string Message { get; set; }
    public int Number { get; set; }
}

class Person
{
    public string Craft { get; set; }
    public string Name { get; set; }
}

...
    
var space = JsonSerializer.Deserialize<Space>(json);
foreach (var person in space.People)
{
    Console.WriteLine(person.Name);
}

Notice that the "people" key has an array for a value (using the square brackets). To display the "name" of each person, we need to loop through each of the objects in the "people" list and display the value associated with the "name" key.

Generic Dictionaries

In addition to recognizing that classes and objects are a common use of Maps, you should also be aware that the the power of a generic Dictionary is that you can define these keys dynamically, during runtime to store any data that you need to. This is highlighted in the next section.

Building Summary Tables

A map is often described as a table. If we have a large set of data that we want to summarize, we can build a summary table using a map. The summary table could contain counts, sums, minimums, maximums, or other mathematical aggregations.

var letters = new[] {'A', 'A', 'B', 'G', 'C', 'G', 'G', 'D', 'B'};
var summaryTable = new Dictionary<char, int>();

foreach (var letter in letters)
{
  // If the letter is not in our summary table yet, add it
  if (!summaryTable.ContainsKey(letter))
  {
    // The key is the letter since we want to summarize how
    // many letters we have.  Since it the first time we 
    // have seen this letter, we will set the value to 1.
    summaryTable[letter] = 1;
  }

  // If the letter is in the table, then update the value
  else
  {
    // We want to increase the value by 1 since we have 
    // already seen this letter before
    summaryTable[letter] += 1;
  }
}

Console.WriteLine(string.Join(", ", summaryTable));
// [A, 2], [B, 2], [G, 3], [C, 1], [D, 1]

Activity Instructions

Complete the following short coding activity to practice using Sets.

Activity: Translator Class

Open the course repository and browse to the week03/learn folder.

Implement the AddWord and Translate functions in the Translator class using a dictionary. The AddWord function should allow the user to add word translations (e.g. english to german). The Translate function should return the translation of a word. If the translation is not available for a word, then "???" should be returned instead. You will need to call AddWord multiple times to build a translation dictionary for testing. You should assume that there is only one translation for every word (and vice versa).

Key Terms

JSON

JavaScript Object Notation. A format used frequently to share data between software. JSON data uses maps and lists. The syntax of JSON is the same as Python.

key

The keys in the map form a set. Each key is unique. Keys are used to lookup value from the map.

map

A data structure that is based on the set. In addition to storing the unique values in the set, the map also includes a value associated with each key. The map has the same O(1) behavior as the set.

value

The value associated with each key within a map. Frequently, these values are referred to as key-value pairs.

Submission

When you have finished all of the learning activities for the week, return to I-Learn and submit the associated quiz there.

Other Links:

• Return to: Week Overview | Course Home