Hello again! In this video, we are going to look at unordered associative containers.
Associative containers store their elements in an order which depends on the key. For containers like
set and map, these use a tree.
The less-than operator of the element decides where the element goes, in the tree.
C++ 11 introduced so-called "unsorted" or unordered associative containers, and these use a hash table
instead of a tree.
If you are not sure about hash tables, I will try and explain them fairly quickly. In C++ terms,
the hash table is an array of so-called "buckets". And these buckets could be a linked list or a vector
or some other sequential container. If we have, say, a lot of random numbers between one and 100,
and we want to put them into a hash table,
we would arrange them into buckets. So we could say, for example, random numbers between one and 10
go into the first bucket. Between 11 and 20,
they go into the second bucket and so on. Up to 91 to 100, which goes into the last bucket.
How do we know which bucket a number goes into?
We can work it out. If it is between one and 10,
it goes into bucket with index zero.
So we need some way to map "between one and 10" into zero.
We can do that by subtracting one and dividing by 10. An integer division.
That is known as a hash function. So it calculates the so-called hash of the number. And then that
hash number is also the index into the array.
So, for example, four. 4 - 3 is 1, 3 divided by 10 is zero - integer division.
So it goes into the element with index 0.
So let's look at a fairly simple hash map.
This is our array of linked lists.
So those are going to be the buckets.
There's 10 of them.
We are going to be generating random numbers.
So there is our engine and the distribution, between 1 and 100.
And then we have our loop. I am going to use one 150 random numbers, because that more
or less fits onto the screen. Then we get a random number on each iteration.
Then we work out its hash, so there is our "quote" hash function.
So this hash number is going to be the index into this array. And then we go to the bucket which has
that index, and we push the random number onto the linked list.
And then we do that for all the random numbers. And then we can iterate over all the elements in the
array, and we can print each of the numbers from the linked list in that element.
So let's see what we get.
Well, they do not actually quite fit on the screen, so maybe I should use less than 150!
But you can see we have elements between 11 and 20 in bucket 1, and so on.
If we want to find an element in our hash map, how do we do that?
Well, that's pretty straightforward, actually.
We are going to call the find() algorithm. So we need the header. Then we create the same hash
map again.
Then let's say, for example, we want to find the number 43.
So we make that our target.
We calculate the hash of 43, using our hash function.
So that should be, 43 minus 1 is 42. 42
divided by 10 is 4.
So we are going to look in bucket number 4.
So we pass the iterators for that bucket as the arguments to find(), and the target that we are looking
for.
So we are looking in buckets 4, apparently and yes, 43 is in there.
And yes, we have found it.
So in our simple hash map, we had an array of linked lists, and the linked lists contain a copy of
the numbers. In the actual C++11 unordered container implementation,
those would be pointers, so they actually have pointers to the elements.
So we have an array of lists of pointers to elements. Got that? :)
So all the details of the hash map are actually implemented for us by the container. So we do not
actually need to compute hashes or search around in linked lists ourselves.
The index of the array is calculated from the element.
There is the hash function, which will generate a number based on the key, which is the hash of the
key.
So that is the index into the array. And usually, this should be a very fast operation.
And then the hash of that key is used as the index into the array.
To insert an element, we calculate the hash number for its key.
Then we find the bucket which corresponds to that hash number, and then we go to the linked list
for that bucket.
And we push a pointer to the new element, onto that list.
To search for an element, we calculate its hash number again.
We go to the bucket with that hash number, and then it searches the bucket for the element or elements
which have that key.
And this will use the equality operator of the key, and not the less than operator which the ordered
containers use.
The most efficient hash table is one in which each element has its own bucket, so there is no need
to process linked lists.
So that means that each key will produce a different hash value, and that requires a hash function which
can perform a so-called "perfect" hashing.
In the real world, perfection is difficult or even impossible to attain, and often very expensive.
So in practice, people usually write hash functions which give the same results for different keys.
And that's known as a "hash collision". And generally that makes the hash map less efficient, because you have
to process a linked list instead of a single element.
On the other hand, the hashing function is much faster.
So it is a compromise, as is often the case in the real world.
In C++ containers, we have multimaps and multisets. And we can have several elements which have
the same key.
So we are definitely going to get collisions there.
And, in general, the more elements there are in the bucket, the longer it will take to perform operations
on that bucket.
So, as far as actually using unordered containers is concerned, they are very similar to using the ordered
versions.
For example, if we want unordered map, so a map which uses a hash table instead of a tree.
We just include the header.
We create an unordered_map object, and then we can call all the usual member functions.
So, for example, with insert(), again, the keys have to be unique, so duplicates will be ignored.
So we get one element with the key "Graham".
If we use an unordered multimap.
Then we can have duplicate keys. And we have three elements with the key "Graham".
Okay, so that is it for this video.
I will see you next time, but until then, keep coding!