# 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

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.