~/victorpierre.dev $ ls learning/programming/data-structures/sets-and-maps/

Sets and Maps

Browse the notes, references, and topic maps collected under this part of the learning archive.

Sets

A set is a collection of distinct elements. It is used to store unique values. Sets are used to solve problems that involve finding unique elements, such as finding unique characters in a string or unique elements in an array.

  flowchart LR
    A[Start] --> B{Element Exists?}
    B -->|Yes| C[Do Nothing]
    B -->|No| D[Add Element]
    C --> E[End]
    D --> E

set.go

    // Initialize a set using a map where keys are elements and values are empty structs
    set := make(map[string]struct{})

    // Function to add an element to the set if it doesn't already exist
    addElement := func(element string) {
        // Check if the element exists in the set
        if _, exists := set[element]; !exists {
            // If the element doesn't exist, add it to the set
            set[element] = struct{}{}
            fmt.Println("Added:", element)
        } else {
            // If the element exists, do nothing
            fmt.Println("Element already exists:", element)
        }
    }

    // Example elements to add
    elements := []string{"apple", "banana", "apple", "orange"}

    // Attempt to add each element to the set
    for _, element := range elements {
        addElement(element)
    }

Common Operations and Their Big O Notation

Operation	Average Case	Worst Case	Comments
Insert	O(1)	O(n)	Adding elements. Worst case occurs when resizing is needed.
Search	O(1)	O(n)	Checking the presence of an element.
Delete	O(1)	O(n)	Removing an element.
Traversal	O(n)	O(n)	Going through all elements.

Advantages

Fast lookups, insertions, and deletions.
Ensures element uniqueness.

Disadvantages

No ordering of elements.
Higher memory overhead compared to arrays.

Applications

Removing duplicates from a collection.
Checking membership efficiently.
Implementing certain algorithms that require uniqueness.

Maps

A map is a collection of key-value pairs. It is used to store elements in the form of pairs. Maps are used to solve problems that involve finding a value associated with a key, such as finding the population of a city or the capital of a country.

In some programming languages, maps are also known as dictionaries, associative arrays, or hashmaps.

  graph TD;
    subgraph Map

    A["Canada"] --> A1["Ottawa"]
    B["Norway"] --> B1["Oslo"]
    C["France"] --> C1["Paris"]
    E["Japan"] --> E1["Tokyo"]
    F["Morocco"] --> F1["Rabat"]
    D["United Kingdom"] --> D1["London"]
    end

capitals := map[string]string{
    "Canada":         "Ottawa",
    "Norway":         "Oslo",
    "France":         "Paris",
    "Japan":          "Tokyo",
    "Morocco":        "Rabat",
    "United Kingdom": "London",
}

Common Operations and Their Big O Notation

Operation	Average Case	Worst Case	Comments
Insert	O(1)	O(n)	Inserting key-value pairs.
Search	O(1)	O(n)	Finding a value by key.
Delete	O(1)	O(n)	Removing a key-value pair.
Traversal	O(n)	O(n)	Traversing all key-value pairs.

Advantages

Quick lookups, insertions, and deletions using keys.
Key-value association is useful in many applications.

Disadvantages

Like sets, maps generally use more memory.
Unordered in their basic form (though some languages offer ordered variants like TreeMap in Java).

Applications

Counting the frequency of elements.
Storing associations (e.g., username and user details).
Caching data for quick access.