Sets and Maps

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

    // 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

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

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.