- HashSet 5:29
- Hashing 6:48
- GetHashCode and Equals Methods 4:03
- Hash Codes and Object Equality 5 questions
- Dictionary 11:29
- Dictionary 1 objective
- Dictionary Keys and Values 6:06
- Using Dictionaries 2 objectives
- The System.Collections.Generic Namespace 3:00
- The System.Collections Namespace 3:24
- Other Collection Types 4 questions
Preview
Video Player
00:00
00:00
HashSet
5:29Sets are unordered and fast for finding, retrieving, and removing items. System.Collections.Generic.HashSet
[MUSIC]
0:00
So far we've learned about arrays and
lists.
0:05
We saw that arrays and
lists have a lot in common.
0:09
When an item is added to an array or
0:12
list, it stays put relative to
the other items in the list.
0:14
The first item in states the first item
0:18
until we insert another
item in front of it.
0:21
The last item added to the end of the list
0:24
stays at the end of the list until
something is added after it.
0:27
This is great because it allows us to
index directly into the array of list.
0:31
Being able to directly access
an item in a collection
0:36
using its index is also
called random access.
0:39
Because it doesn't matter where the item
is randomly placed in the list,
0:44
we can always get direct access
to it if we know it's index.
0:48
This is why retrieving an item
from an array or list is so fast.
0:52
This is also why we can sort a list,
and it's the reason we can search it so
0:56
quickly using binary search.
1:00
Maintaining order and
1:02
fast random access are the key
advantages to arrays and lists.
1:03
There are times when we don't need
to maintain the order of the items
1:08
in a collection, or
1:11
perhaps there's no logical way to
order the items in the first place.
1:13
But we still need to be able
to find them efficiently.
1:17
You might be thinking, why can't we
sort the list and use binary search?
1:20
Binary search is fast, but
it relies on the collection being sorted.
1:25
It's often inefficient to
keep a collection sorted
1:30
if we're regularly adding or
removing items.
1:33
Remember, there are a couple of things
that arrays and lists are not so good at.
1:37
Inserting or adding an item to a list or
1:42
an array may require that
the items in the list be shifted.
1:44
It may even require that all of the items
be copied into a a larger array
1:49
in order to accommodate the new item.
1:54
Removing an item from the beginning or
middle of an array or
1:56
list also requires that
the items be shifted.
2:00
These are all potentially inefficient
operations, especially if items are being
2:03
added or removed from the beginning of
the list in order to keep it sorted.
2:08
It's common to need to be able to quickly
determine if an item is in the collection.
2:13
There is a type of collection that
makes this type of searching fast, so
2:18
long as we don't need to
maintain the order of the items.
2:22
This collection is called a set.
2:25
Just like with lists,
2:28
sets also have an interface that
define what it means to be a set.
2:30
Its right here called Iset of T.
2:34
Let's take a look at it.
2:36
We'll see that it has the Count property,
and
2:41
here are the methods that the set exposes.
2:45
The set collection type is patterned
after the mathematical set.
2:48
So there are many methods that have to do
with standard mathematical set operations
2:52
such as intersect and union.
2:56
Computer science, which is the academic
field upon which computer architecture and
2:58
programming is based, is rooted in math.
3:03
In fact, a computer at its core is
nothing but a very fast calculator.
3:06
So it's no wonder that we encounter math
terms and principles when coding software.
3:10
A set isn't an ordered
collection of items.
3:15
So we won't find any way to index
into the collection without the list.
3:18
You won't find a collection
named set in the .NET Framework.
3:23
Instead .NET provides a couple
implementations of the Iset interface.
3:26
The most common one is named HashSet.
3:32
In the school roll class, let's change our
student list from a list to a HashSet.
3:35
So here I'll change this to HashSet,
and also over here.
3:41
HashSet doesn't have an AddRange method.
3:49
Instead, we'll use one
of the set operations to
3:52
add a collection of items to it.
3:54
In this case, we'll use the UnionWith.
3:56
Just like AddRange,
UnionWith also accepts an I numerable.
3:59
And that's all we have to change to
switch from using a list to a HashSet.
4:04
Notice what we didn't have to change,
though.
4:08
Because we're using interfaces in
all of our public properties and
4:11
methods, we don't have to change the
public members of a class in the code or
4:13
in any client classes that might
be using those public numbers.
4:18
Interfaces save the day again.
4:21
Earlier I mentioned that one thing we
might want our AddStudents method to do,
4:23
is to make sure that students that
are already in the school can't
4:27
accidentally be added again.
4:30
Now that we've switched to
using a set instead of a list,
4:32
the AddStudents method automatically
works the way we want it to.
4:36
The defining property of a set is that
it doesn't allow duplicate items.
4:39
Let's see how this works by going back to
main and adding all of our students again.
4:44
We can remove these lines here first.
4:49
Now just copy this line we're adding
the students and paste it here.
4:53
So now this is trying to add
all these students again.
4:58
Now let's compile and run this.
5:02
As you can see, even though we added
these students to the school rule twice,
5:11
we still only have three
students in the role.
5:16
Had our internal collection been a list,
we'd have three duplicate students here.
5:19
HashSet ignores the last three
items we attempted to add
5:24
because they were already in the set.
5:27