‫So now we're going to do hash tables and with a hash table, we're going to have an address space.
‫And this address space is just an array.
‫And what I'm going to do in this section is use a hash table for keeping the inventory of a hardware
‫store.
‫And one of the things that we would have in a hardware store would be nails.
‫This is what is known as a key value pair, where nails is the key and a thousand is the value.
‫And what we'll do with this key value pair is we will run it through a hash function.
‫We will write that hash function in a couple of videos, but I'm just going to graphically represent
‫it here.
‫And the hash is performed on the key.
‫So we run the key through the hash, we'll get our key value pair back.
‫But the thing that the hash function does is based on the calculation that we do on this key, it gives
‫us an address.
‫And that address is one of the indexes in this address space, and that is where this key value pair
‫will be stored.
‫So now let's talk a little bit more about this hash function that we're going to write and the characteristics
‫of it.
‫So the first thing to know about hashes is they are one way.
‫So let's say if we have a key nails and we run it through the hash function and it produces the number
‫two, you cannot take the number two and run it through the hash and get nails.
‫It only goes one way.
‫The other thing about hashes is that they are deterministic.
‫And that means if Nails produces the number two, it will always produce the number two.
‫So this hash function contains both of these characteristics.
‫So let's bring our address space back here.
‫So we will create a couple of other functions in the hash table section that will use the hash function.
‫One of those will be set.
‫We'll pass this a key and a value.
‫So let's say we pass this nails and 1000.
‫The set function will call on the hash function and the set function will create this key value pair.
‫But the hash function will create an address and that is where we'll store the key value pair.
‫So let's add a few more of these to our hash table.
‫Say we have set screws and that'll create this key value pair and an address of six.
‫That key value pair goes down there and then we'll say, set nuts, 1200.
‫Now when we do this.
‫We get an address we've already used.
‫This gives us an index of two.
‫Now, what we don't want to do is overwrite the other key value pair.
‫We want to leave the other key value pair there and add this one.
‫What this situation is called a collision where you have more than one key value pair at a particular
‫address.
‫And we'll talk about a couple of ways that can be dealt with in the next video.
‫So let's just add one more.
‫So we have a more full hash table.
‫We'll say set bolts, we'll get a key value pair and an address and that goes there.
‫And that brings us to the next function that will build, which is called Get Get also uses the hash
‫function and remember that hashes are deterministic.
‫So when we run bolts through this, we know the index where bolts would be stored.
‫It's going to be at the index of four.
‫So we go to the index of four and we'll return the value that goes with that key value pair.
‫So now let's look at get on another key value pair.
‫We'll say nails.
‫And when we run this, we get the index of two.
‫And at the index of two we have more than one key value pair.
‫So part of the get function is we're going to have to have a way to iterate through all the different
‫key value pairs that might be at a particular address.
‫And when we iterate through in this situation, we will find nails and return 1000.
‫And that is our quick introduction to hash tables.