Maps & Sets

The previous chapter explored lists as fundamental storage containers and showed how they can be used to back more complex abstractions. This chapter introduces keyed structuring as a way to efficiently locate arbitrary values without requiring indexes or positions within the underlying storage structure.

This chapter introduces the map and set ADTs, and examines both unsorted and sorted representations. The unsorted representations use hashing to map keys directly to array indexes and provide O(1) expected lookup performance. Sorted representations generally provide a sorted traversal ordering and enable efficient order statistics with a slightly slower O(log(n)) expected lookup performance over their unsorted counterparts.

Key-Value Relationships

Consider the following pseudocode that illustrates three Person objects. Each Person object contains a name, age, and favorite food.

Person{name: Brain, age: 37, food: tapioca}
Person{name: Dichael, age: 22, food: ice cream}
Person{name: Bobson, age: 36, food: hamburgers}

To work with the collection of Person objects it is possible to store objects in either a linked list with publicly-exposed positions or an array-based index-addressable list. Both positions and indexes are grouped here as handles that provide position-based addressing in a simple lookup table. In the simplified lookup table, each positional handle represents a key to the information it accesses. In an array-based list, using the array indices constitutes a direct addressing scheme.

Positional handles carry very little semantic information, with the most useful being a way to identify the insertion ordering of an object. For example, in an indexed list, it is trivial to encode insertion ordering via the indexes themselves. Inserting each of the pseudocode objects into an array, index 0 refers to Brain, 1 to Dichael, and 2 refers to Bobson.

┌───────┬─────────────────────────────────────────────────┐
│ Index │ Person object                                   │
├───────┼─────────────────────────────────────────────────┤
│   0   │ Person{name: Brain, age: 37, food: tapioca}     │
│   1   │ Person{name: Dichael, age: 22, food: ice cream} │
│   2   │ Person{name: Bobson, age: 36, food: hamburgers} │
└───────┴─────────────────────────────────────────────────┘

As a result, performing lookup operations such as figuring out how old Bobson is or Dichael’s favorite food require some match operation for every object in the list. In fact, naive implementations require either O(n) operations to identify the first match, or Ω(n) operations to ensure that all matches are identified. Additionally, direct addressing or positional handle-based object structuring is fragile under structural mutations. This can create algorithmic soundness and, depending on the implementation, memory safety issues when existing positional handles cease to identify the same object. For example, if you remove the first entry then the same index identifies a different person.

┌───────┬─────────────────────────────────────────────────┐
│ Index │ Person object                                   │
├───────┼─────────────────────────────────────────────────┤
│   0   │ Person{name: Dichael, age: 22, food: ice cream} │
│   1   │ Person{name: Bobson, age: 36, food: hamburgers} │
└───────┴─────────────────────────────────────────────────┘
NOTE: Index 0 now identifies Dichael, not Brain!

Keyed structuring provides a way to directly associate an arbitrarily-typed key with an arbitrarily-complex value, regardless of structural or positional ordering. Continuing the person object example, it is natural to designate the person’s name as the key and store only a Value object containing the related person details.

┌─────────┬──────────────────────────────────┐
│ Key     │ Value object                     │
├─────────┼──────────────────────────────────┤
│ Brain   │ Value{age: 37, food: tapioca}    │
│ Dichael │ Value{age: 22, food: ice cream}  │
│ Bobson  │ Value{age: 36, food: hamburgers} │
└─────────┴──────────────────────────────────┘

The Map ADT

Maps, sometimes called dictionaries (or simply “dicts” in some programming languages), are ADTs that store arbitrarily typed key-value pairs called entries. Entries are used to associate a key with a value to provide efficient key-based lookup operations.

Typically, map implementations require keys and values to remain homogenous according to their respective type declaration; that is, for a given map, all keys must have the same type and all values must have the same type. However, this is generally a language-level implementation and not a strict ADT requirement. For example, Python’s dict allows heterogeneous key-value associations.

dict = {
    "Bobson": 36,
    36: "hamburgers",
    "active": True
}

But because Rust is statically typed, each element type must be declared and conform to its declared type. Additionally, for reasons discussed later, the keys in this hash map must be hashable. In the following illustration, it is possible to collapse the Key and Val types into a single MapType, but that would mean both keys and values would have to be hashable, which is not a requirement for the hash map type, so the discriminants are simply mirrored.

#![allow(unused)]
use std::collections::HashMap;

#[derive(Hash, PartialEq, Eq)]
enum Key<'a> {
    Name(&'a str),
    Food(&'a str),
    Age(u8),
    Active,
}

enum Val<'a> {
    Name(&'a str),
    Food(&'a str),
    Age(u8),
    Bool(bool),
}

fn map_example() {

    // Example 1: A hash-based map with keys as
    // strings and values as integers
    let mut map = HashMap::<String, i32>::new();

    // Example 2: Another hash-based map approximating the
    // dict type in the Python example above where the
    // types and values are part of an explicit enumeration
    let dict = HashMap::from([
        (Key::Name("Bobson"), Val::Age(36)),
        (Key::Age(36), Val::Food("hamburgers")),
        (Key::Active, Val::Bool(true))
    ]);

}

Like all collections in this module, notice that maps share some fundamental collection operations with previously covered list types with operations such as insert, remove, and iterate over members of the data structure in various ways.

• size() Returns the number of entries in the map
• is_empty() Returns a Boolean that indicates whether the map is empty
• insert(k, v) / try_put(k, v) Adds entry (k, v) to the map without allowing duplicate keys
• put(k, v) Adds entry (k, v) to the map, overwriting any value v associated with an existing key k, and returns the old value
• get(k) Returns the value v associa}ted with key k
• contains(k) Returns a Boolean indicating the presence of key k in the map
• remove(k) Removes the entry (k, v) associated with key k
• keys() Returns an iterator that yields references to all keys in the map; Optionally, a keys_mut() may be distinguished to return mutable references, though many map implementations place structural integrity on the immutability of the keys
• values() Returns an iterator that yields references to all values in the map; Optionally, a values_mut() operation may return mutable references
• entries() Returns an iterator that yields references to all (k, v) entries in the map

As with other ADTs in this module, operations that return iterators may alternatively return iterable collections if you’ve got your heart set on that. Notice that the map ADT does not specify any sorted properties or operations. Creaing and maintaining sorted structures is covered in more depth in later pages. Once again, there are far more fundamental matters to discuss before discussing sorted structures.

Note

The term “map” is overloaded in computer science. Map data structures are not the same thing as mapping functions, commonly known as “apply-to-all” functions in functional programming. While both deal with collections, maps as data structures involve key-value associations, while map functions in functional programming languages involve transforming the values of a collection according to some predicate. This section only covers data structures. In Rust, implementing Iterator for your collection provides automatic access to you to use the

The Set ADT

The set ADT represents a mathematical set-theoretic type. At their most basic, sets represent a collection of discrete elements, sometimes called members. In mathematics, sets are foundational objects: a set S is a collection of discrete elements, often defined via a predicate P as S={x such that P(x)}, where (comparative) ordering and multiplicity (repeated elements/values) are irrelevant.

In programming, sets prioritize uniqueness and are typically optimized for efficient membership checks, element insertion, and element deletion operations. Many programming language libraries implement sets as a restricted map where the entry’s key is the element itself, and the value simply indicates the element’s presence.

The set type contains the following fundamental operations:

• add(e) Adds the element e to the set
• remove(e) Removes the element e from the set
• contains(e) Returns a Boolean if the set contains element e

Additionally, the following opertations are not essential to the set ADT, but are common in set APIs:

• iter() Returns an iterator over all the elements of the set
• self.union(other) Returns iterator over unique elements between self and other
• self.extend(other) Mutates self such that self contains all unique values of both self and other
• self.intersection(other) Returns an iterator over values that appear in both self and other
• self.retain_all(other) (sometimes as self.intersect(other)) Mutates self such that self only keeps elements that are also in other; The term “intersect” may be too close in name to the non-mutating “intersection” operation
• self.subtract(other) Mutates self such that self only contains elements that are not in other
• self.difference(other) A non-mutating subtraction operation that returns a new set with only elements that are not in other
• self.retain(|predicate|) A filter operation that mutates self to only contain values that adhere to the given predicate (lambda)

Keying Schemes

Keying schemes refer to the various ways that data is identified in the structure. For example, the section on comparative ordering illustrated three different ways to identify a Student object based on how its keying scheme was implemented.

Keying schemes generally exist outside of map/set representations, but are still important to the structure’s use. For example, instead of using a simple key like the Student.name, a more robust keying scheme may utilize computational hashing (discussed in depth on the next page) to create keys with a higher chance of uniqueness. Additionally, it is very common to use a UUID, ULID, or similar as a map key. UUIDs and ULIDs both increase the chance of uniqueness, but only ULIDs and UUIDv7s can be comparatively ordered (sorted, by creation time). These kinds of keying schemes provide a greater chance of key uniqueness while still providing some security, as well as the potential to induce a total ordering.

┌────────────────────────────┬────────────────────────────────────────────────┐
│ Key                        │ Value object                                   │
├────────────────────────────┼────────────────────────────────────────────────┤
│ 01M1XC8FJ2417FKQ9BYE8ESSA7 │ Value{name: Brain, age: 37, food: tapioca}     │
│ 01M1XC92SQJMNRVBJ2CKQQNHS7 │ Value{name: Dichael, age: 22, food: ice cream} │
│ 01M1XC9DJHQYJBG3ZCW51E4AET │ Value{name: Bobson, age: 36, food: hamburgers} │
│ 01M1XCNKTEWD0YHDDPCQ73Y9AH │ Value{name: Bobson, age: 23, food: dumplings}  │
└────────────────────────────┴────────────────────────────────────────────────┘
NOTE: A more robust keying scheme allows multiple entries for the same name

Both keys and values may rely on further abstraction layers. The next page discusses boundaries for the key type K, but for now just know that keys should generally contain enough information to distinguish them.

Multimaps & mutlisets

Maps are useful for associating arbitrary keys with arbitrary values, and sets typically get used to compute membership and distribution by a key’s presence. As a result, basic maps and sets

A multimap is like a map, except that a single key can be associated with multiple different values. Multisets, also called bags, are sets that allow duplicates. The biggest takeaway here is how you define sameness/otherness. For example, are you counting the number of references to a single object, or are you counting multiple separate instances of bitwise equivalence? In multisets it is probably most common to list occurences and thus implement these structures with Entry<K, N> types where K is the element andN is the number of occurences. Multimaps are similar, except N is typically a list of values associated with key K. This might look more like Entry<K, V>.

// Base multimap struct
pub struct Entires<K, V> {
    key: K,
    vec: Vec<V>,
}

Multiset ADT

In addition to all the regular map operations, multisets contain the following specialized operations:

• count(k) Returns the number of times key k appears in the set.
• remove(k, n) Removes n number of occurences of key k in the set.
• size() Returns the total number of elements in the set, including duplicates.

Multimap ADT

In addition to all the regular map operations, multimaps contain the following specialized operations:

• remove_all(k) Returns an iterator over all key:value pairs for key k.
• key_set(k) Returns an iterator over non-duplicative keys k in the map.
• values(k) Returns an iterator over all the values for key k.

Map & Set Representations

Because maps are just sets with an independent key to each value, they are easily represented by the same basic designs. The next two pages discuss popular representations for unsorted and sorted set and map structures, commonly referred to as dictionaries.

The most common unsorted map/set representation (by a wide margin) is the hash table. A map ADT represented with a hash table is commonly called a hash map, and a set ADT represented with a hash table is commonly called a hash set.

It is possible to represent sorted maps naively using techniques already covered, but the most efficient and common representations for sorted maps rely on techniques and concepts covered in the next chapter on hierarchical structures.