top of page
This site was designed with the
.com
website builder. Create your website today.Start Now

Sets and Maps

Tutoring > Data Structures > Sets and Maps

There are data structures suited to different purposes. Searching a set may take a long time because sets are unordered. However, inserting into or deleting from a set takes little time as we don't have to worry about the order.

What is a set?

A set is an unordered collection of values with no duplicate values.

A set is an Abstract Data Type (ADT).

Operations on sets:

  • Adding a value.

  • Deleting a value.

  • Searching for a value.

 

A set can be represented like this: {3, 5, 7, 8}

Maps

A map is a collection of (key, value pairs) such that each possible key appears at most once in the collection(two values cannot have the same key).                       {K,V}

Also known as: associative array, dictionary, symbol table.

Operations on maps:

  • Adding a new (key, value) pair to the collection.

  • Reassign a value - replace one of the values in a (key, value) pair.

  • Remove/delete a (key, value) pair.

  • Lookup a value associated with a given key.

Sets in mathematics

A set in mathematics is defined as a collection of distinct objects.

The picture above shows an intersection between two sets, A and B.

For example, if

set A = {1, 4, 2, 66} and

set B = {1, 3, 2, 44} we can say that the intersection of A and B is {1, 2}

because 1 and 2 appear in both A and B.

 

There is also union which joins sets together.

set C = {1,2} and 

set D = {2,3} so C union D would give us {1, 2, 3} since we cannot have duplicates in a set so 2 is only represented once. 

 

Operations on sets and maps

As mentioned, it takes little time to insert or delete a value into a set as there is no order to it. If we wanted to search for a value in a set, this might take a long time. Our only option is linear search as there is no order so in the worst case the time complexity is O(n), that is, for n elements, we would have to search n times to find our element.

One solution is to sort the set into a Binary Search Tree (BST).

 

Searching a map for an element is much more efficient as we can search for the key. A good example of this is when you want to find something in a dictionary. A linear search would be analogous to starting at the beginning and reading through until you got to the desired value. 

Instead, we look for the key (in the dictionary case, the letter that the word begins with), and this reduces the time taken to find it.

bottom of page