Dictionaries

Time Complexity			Space Complexity
Access	Search	Insert / Delete	O(n)
N/A	O(1)	O(1)

A “dictionary” in programming terms can be compared to an actual dictionary: some word (or ‘key’) is associated with some definition (or ‘value’). The difference is, with a dictionary in programming, these “keys” and “values” can be anything (any type). For instance, "pi" can be associated with 3.14, or the capital letter 'P' can be associated with "Pinocchio".

You might ask, what’s the use of this? Compared with the other data structures, dictionaries are extremely efficient. Instead of going through the entire dictionary to find something, like you might with an array, or using binary search with numbers, if you give a dictionary a “key” it gives you the “value” almost instantly (read: O(1) averge time), no matter how big the dictionary is (generally).

The reason this works involves a “hash function” and a “hash table”. But you can imagine there’s just some magical function that gives you the value from the key, and have a pretty good idea. It works sort of like the dewey decimal system, where given the index it’s generally known where the corresponding book is. But there’s more math involved.

This structure is often used to make algorithms more efficient by remembering associations, but you can see that in the “advanced” section. This example has the first three letters and the corresponding words in the phonetic alphabet adopted by NATO to make communication clearer and more definite.

Comments are included to show what task is being done at which line, and the same syntax should be used for most dictionaries.

C++

C#

Java

JavaScript

Python

Swift

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    // Declaration
    unordered_map<char, string> dict;

    // Add / change values
    dict['a'] = "Alpha";
    dict['b'] = "Bravo";
    dict['c'] = "Charlie";

    // Get specific values
    cout << "a is for " << dict['a'] << endl;

    // Get size
    cout << "number of things: " << dict.size() << endl;

    // Check if key is present
    cout << boolalpha;
    cout << "a: " << (dict.find('a') != dict.end()) << endl;
    cout << "d: " << (dict.find('d') != dict.end()) << endl;

    // Accessing all values
    for (auto entry : dict)   //c++ 11
      cout << entry.first << " " << entry.second << endl;
}

using System.Collections.Generic;
class Program {
  static void Main(string[] args) {
    // Declaration
    Dictionary<char, string> dict = new Dictionary<char, string>();

    // Add / change values
    dict['a'] = "Alpha";
    dict['b'] = "Bravo";
    dict['c'] = "Charlie";

    // Get specific values
    System.Console.WriteLine("a is for " + dict['a']);

    // Get size
    System.Console.WriteLine("size: " + dict.Count);

    // Check if key is present
    System.Console.WriteLine("a: " + dict.ContainsKey('a'));
    System.Console.WriteLine("d: " + dict.ContainsKey('d'));

    // Accessing all values
    foreach(KeyValuePair<char, string> entry in dict)
      System.Console.WriteLine(entry.Key + " " + entry.Value);
  }
}

import java.util.*;
public class dictionary {
  public static void main(String[] args) {
    // Declaration
    Map<Character, String> dict = new HashMap<Character, String>();

    // Add / change values
    dict.put('a', "Alpha");
    dict.put('b', "Bravo");
    dict.put('c', "Charlie");

    // Get specific values
    System.out.println(dict.get('a'));

    // Get size
    System.out.println("size: " + dict.size());

    // Check if key is present
    System.out.println("a: " + dict.containsKey('a'));
    System.out.println("d: " + dict.containsKey('d'));

    // Accessing all values
    for(Character key : dict.keySet())
      System.out.println(key + " " + dict.get(key));
  }
}

// Declaration
var dict = {};

// Add / change values
dict['a'] = "Alpha";
dict['b'] = "Bravo";
dict['c'] = "Charlie";

// Get specific values
console.log(dict['a']);

// Get size
console.log("size: " + Object.keys(dict).length);

// Check if key is present
console.log('a' in dict);
console.log('d' in dict);

// Accessing all values
Object.keys(dict).forEach( function(key){
    console.log(key, dict[key]);
});

# Declaration
dict = {}

# Add / change values
dict['a'] = "Alpha"
dict['b'] = "Bravo"
dict['c'] = "Charlie"

# Get specific values
print(dict['a'])
#or
print(dict.get('a'))

# Get size
print(len(dict))

# Check if key is present
print('a' in dict)
print('d' in dict)

# Accessing all values
for key in dict:
  print(key, dict[key])

// Declaration
var dict = [Character : String]()

// Add / change values
dict["a"] = "Alpha"
dict["b"] = "Bravo"
dict["c"] = "Charlie"

// Get specific values
print(dict["a"]!)

// Get size
print(dict.count)

// Check if key is present
print(dict["a"] != nil)
print(dict["d"] != nil)

// Accessing all values
for(key, value) in dict{
  print(key, value)
}

Notes

C++

C#

Java

JavaScript

Python

Swift

The import statement #include <unordered_map> should be used for a dictionary (referred to as an “unordered map” in C++).

It should be noted that almost any type (including custom types) can be used for the values of a dictionary, but using custom types for the keys requires your own hash function, which is a mess in itself. C++ defined types, however, are usually fine.

boolalpha is passed to cout to change 1 and 0 boolean outputs to true and false.

the .find() function results in the dict.end() pointer if there is no key, so that’s why they can be compared with != to check if the key is there.

In c++ 11, a dictionary (and most other data structures) can be iterated through with a “range-based for loop”. This loop automatically knows the type and covers the entire data structure in a concise way with the syntax

for (auto yourVar : yourStructure){

//do something with 'yourVar'

}

Note

There is one line marked as C++ 11 here, so add “-std=c++11” after “g++” when compiling if it doesn’t work.

If you’re stuck with an older version of C++, a dictionary can also be iterated through like this:

for (unordered_map<char, string>::iterator it = dict.begin(); it != dict.end(); it++){

cout << it->first << " " << it->second << endl;

}

This uses an “iterator” pointer, used in the standard library.

The import statement using System.Collections.Generic; should be used.

This uses a foreach loop, a loop in C# that goes through the variables in a container with the syntax

foreach(KeyValuePair<char, string> yourVar in dict)

// do something with yourVar.Key and yourVar.Value

The import statement import java.util.*; should be used.

dict.keySet() returns the keys of the dictionary.

A “range-based” for loop is used. This gives you each value in an array / container. It has the syntax

for(typeOfVar yourVar : someContainer)

//do stuff with "yourVar"

Conveniently, all JavaScript objects are dictionaries by default. This means they can be declared with curly brackets, e.g.:

var dict = {}

The syntax Object.keys(dictionary) returns the keys of the dictionary.

A “range-based” for loop is used. This gives you each value in an array / container. It has the syntax

someArray.foreach( function(yourVar){

//do stuff with "yourVar"

});

Where yourVar is each item and someArray is your array.

A “range-based” for loop is used. This gives you each value in an array / container. It has the syntax

for yourVar in someArray:

#do stuff with yourVar

Doing this with a dictionary gives keys as yourVar.

Swift has what are known as “optionals”. These are variables which may or may not exist. When accessing a dictionary, instead of returning something like a normal string, a “string optional” is returned, which is either a string or nil (undefined). These are represented as string? when debugging in the console, and are represented similarly for other “optional” types.

When using an “optional” and you know it’s defined, you can force it to the original type with the ! operator.

Often, the value of an optional is checked with the syntax

if let thing = someOptional {

//do stuff with thing

}

This is safer than other languages if you don’t know if a variable is defined.

Also, a “range-based” for loop is used. This gives you each value in an array / container. It has the syntax

for yourVar in someArray{

#do stuff with yourVar

}

When doing this with a dictionary, something like (key, value) should be used in place of yourVar. The words can be anything, however having two things in parenthesis gets you the keys and values.