# Sets and Maps

The next ADTs we're going to work with are two very common ADTs called the Set and the Map.

You're familiar with both.  Python has [the `set` datatype](https://docs.python.org/3/tutorial/datastructures.html#sets), which perhaps you've used.  For Maps, it has [dictionaries](https://docs.python.org/3/tutorial/datastructures.html#dictionaries), which you've definitely used many times.

Underneath the hood, Sets and Maps tend to be implemented in very similar ways, so we present them together.

## Set and Map functionality

Sets have the following functions:

- `add(e)`: adds element `e` to the set.
- `remove(e)`: removes `e` from the Set.
- `contains(e)`: returns `True` or `False`, indicating whether or not `e` has been added to the Set.

Maps are meant to work with (key, value) pairs. The data is accessible by `key`, and each key has some probably-longer value. Dictionary (a la Python) is a good name, as in physical dictionaries, the key is the word (easily found using alphabetical order), and the dictionary is the associated value.

Maps have the following functions:

- `insert(k,v)`: inserts key `k` with associated value `v`.
- `get(k)`: returns the value associated with key `k`.
- `remove(k)`: removes the key, value pair associated with key `k`.

## Implementation using arrays and linked lists

Unless the set/map is going to be small, it is not common to implement these using arrays or linked lists.  Nevertheless, it is good practice to think through how they would be implemented and what the runtimes would be if they were.

In sets and maps, $n$ refers to the number of elements or key-value pairs in the set/map.

### Arrays

When we implement these with an array, we could choose to have the array be sorted or unsorted. In a **sorted array**, the smallest/alphabetically-first/first-for-some-reason key is at index 0, and the largest is at the end. In a set, the array would contain only the elements. In a map, an index of the array would contain both the key and associated value, and would be ordered by the key.

When we `add` or `insert`, we would have to first find where the data should go in the array in order to maintain the sorted nature, and then insert the data there, scooting the other data over to make room. Finding where it goes would take $O(\log(n))$ time, as we can use binary search. Scooting everything over would take $O(n)$ time, so the total runtime is $O(\log(n)) + O(n) = O(n)$.

When we run `contains` or `get`, we need to find where the element/key is in the array. Again, we can use binary search. For a set, we just return True/False based on whether it is there, and in a map, we return the value associated with the key we searched for. $O(\log(n))$ time.

In an **unsorted array**, we don't worry about keeping the array sorted.  When we `add`/`insert`, we can just throw it on the back of the array, so it would now take an *amortized* $O(1)$ time (see why?).

When we run `contains`/`get`, on the other hand, we can no longer do binary search, so it would be an $O(n)$ linear search.

You'll notice we skipped `remove` on both of these. Removal *tends to be* much less common than the other functions. In that light, the most common approach to removal is to just find the element/key, and mark them as removed, without actually removing them. If you get too many, you do a single $O(n)$ pass and clean everything up.

What this means is that we can think of `remove` as being a special case of `contains`/`get`, which just requires finding the element/key and doing some minor $O(1)$ work when you get there to mark them as removed.

|                    | Sorted Array | Unsorted Array   |
|--------------------|--------------|------------------|
| add(e)/insert(k,v) | $O(n)$       | amortized $O(1)$ |
| contains(e)/get(k) | $O(\log(n))$ | $O(n)$           |

### Linked Lists

When we implement these with a linked list, again we could choose to have the linked list be sorted or unsorted. In a **sorted linked list**, the smallest/alphabetically-first/first-for-some-reason key is at the head, and the largest is at the tail.

When we `add` or `insert`, we would have to iterate/recur along the linked list until we found the proper place to insert the data in order to maintain the sorted nature, which would take $O(n)$ time. The actual insertion would then take $O(1)$ time. So, in total, this take $O(n)$ time.

When we run `contains` or `get`, we need to find where the element/key is in the linked list. In linked lists, we cannot do binary search, so this is still $O(n)$.

In an unsorted linked list, adding/inserting is a straightforward $O(1)$, as we can just throw it on the front or back. contains/get is $O(n)$.

|                    | Sorted Linked List | Unsorted LinkedList |
|--------------------|--------------------|---------------------|
| add(e)/insert(k,v) | $O(n)$             | $O(1)$              |
| contains(e)/get(k) | $O(n)$             | $O(n)$              |