[MUSIC] Today we're going to move over to an entirely new type of algorithm. And this algorithm's often computer science's favorite algorithm, because you're going to find the results of hashing, it's going to give us a fantastic run time for certain operations. Let's dive into what it means to do hashing. Mathematically, we define hashing as a keyspace that we want to transform into a number of different values. So, everything inside of our keyspace is going to be every possible key that we can have inside of our dictionary. And our goal of a hash table is to be able to map every single key to the value that it contains in that dictionary, and do so as quickly and as efficiently as possible. You may already be familiar with hashing if you've ever used a dictionary structure in a language like Python or JavaScript. At the core of these native data types, we have the idea of hashing. Let's go ahead and look at what it might mean to actually do some hashing. So, for example, let's look at a hash table. And the first example I can remember about hashing is thinking all the way back to high school. In high school I went to a large school that had a number of lockers. And every single person was assigned a locker. And I remember all the way back from my high school days that here in this hash table I was assigned locker 103, so that was my locker. And then I knew the locker numbers of some of my friends. Because if I wanted to see some of my friends between courses, I would go to their locker and meet them at their locker. And that way I could find exactly where they were going to be located. I could go directly there. Even to this day, I remember some people's locker. One of my best friends Blake was at locker number 92. And there's a number of different lockers here at the school. The one thing to note is that the lockers are unique key value that every single locker has some instrument number and then that locker is associated with some data. The data here is the name of the person who owns the locker. I imagine somewhere in the administration, there was a mapping between the student who owned the locker and the locker number. So given any locker number you could quickly look up which student had that locker. A hash table is going to allow us to do exactly that. We're going to input a number into our hash table, and we're going to use some function, so we can go ahead and map every possible number input into a fixed sized output. Because ultimately, in a locker key space, we might know exactly how many lockers there are, but we may also consider things like identifier, such as a social security number or other identifier that may be a random number that's not entirely filled up in the key space. So we know the key space can be any possible integer, and we want to be able to map any possible integer into our output space. The entire goal of hashing is always going to revolve around this diagram. Here we have input coming in, this is going to be something like an integer. Some function that we are going to define later, that's going to transfer this integer or string or whatever our input is into a number that is in the range zero to whatever the size of our array is, which I'm going to call n. The transformation of this key input into a number and then how we manage that array and ensuring to deal things without collisions is exactly what we're going to be talking about as we talk about hashing. So specifically when we define a hash table, there's always going to be three things at play and we're going to dive into what each of these three things means. The first thing is we need some function, a hash function, that's going to map our input space into an array index. So if we have a string as our input, we need to map that string from the string input type down to some integer between 0 and n. The second thing we need to look at is we need to actually have an array that stores the actual data. So notice that here at the hash table we have an array that's going to store data, that's going to be indexed in by our hash function. The very last thing is, we can imagine that sometimes we're going to have two things in the same spot in the array, and we know that's not allowed. So we need some way to decide what we want to do in collisions. So when we have collisions we want some collision handling strategy that's going to allow us to handle the collisions that occur when our hash function maps two different values to the same point in the array. The combination of all three of these ideas is going to be the subject of this week's videos. And we're going to dive in to exactly what it means to build a good hash function. What it means to have a good strategy with our array, and exactly what we do when we do have a collision. So while this may be a little confusing right now, it'll become clearer as we move through these videos. Let's get started with the hash function in our next video. I'll see you there. [MUSIC]
