- [Instructor] Oh my gosh, it's week nine.
Wow, what do we have for week nine?
Good stuff.
This week, we're gonna learn about searching.
You may think we've already learned about searching
with trees,
well, we've got a little more to go yet.
And we're gonna begin our study of hash tables.
Hash tables are widely used
and they provide us with constant time access
to objects stored in the table
which is pretty cool.
Taking a step back,
you'll recall that we learned how to search for objects
in a binary search tree or an AVL tree or a splay tree
and that in general, these have a complexity
of Big O of Log N.
True, we have the worst cases for binary search trees
of O of N
but that's mitigated by the AVL and splay trees
and true if we have,
if we access the same element repeatedly in a splay tree,
we get constant time access.
But in general, we have Big O of Log N.
Now this week, we'll look at how to search
a linear structure like a vector
and we'll see that naive linear search
has linear complexity.
We'll also see that if we sort our vector first,
we can achieve Big O of Log N
using what's called binary search
which is a big improvement over linear time.
And if our data have certain properties,
we can do even better than this
with what's called interpolation search
which can achieve under good conditions
Big O of Log of Log N,
which is almost magical.
And binary search probes a vector
in search of the target
and divides the search space in half at each iteration
until it finds the target.
That's how it achieve Big O of Log N complexity.
Interpolation search takes advantage of certain regularities
in the data
that allows it to make very, very good guesses
as to where to find a particular element
in a linear list.
And if that works, it works great.
But it does require that your data have certain,
certain properties in order for it to work.
And after we complete our investigation and searching,
we'll learn about hash tables.
Now the idea behind hash tables
is that we don't search to find the index
of an item we're looking for.
We calculate its position directly.
And if we can do that,
that means we can access elements in hash table
in constant time.
Now it turns out that its not quite that simple.
It may be the case that when we try calculating
the index of two different objects,
we get the same answer
and that's called the hash collision.
And that's a problem for hash tables
and there are a number of so-called
collision resolution policies
that are used to handle cases of hash collisions.
And this week, we'll see one such policy
which is called separate chaining.
Essentially we're gonna work with a vector of vectors.
And next week, we'll learn about other hash collision
resolution policies.
But we've got plenty to cover this week:
binary search, interpolation search, hash tables,
hashing algorithms, hash collisions and separate chaining.
So get started with this week's video lectures
and demonstrations
and supplementary materials posted on Blackboard
and don't forget the assigned reading in the textbook.
At the end of the week,
we'll have another quiz which will cover
this week's material
and a little bit of material from last week.
And so that's all for now.
I'll see you on our Yellowdig discussion board.
Good luck and have fun.