All right, let's talk about hash tables and how quadratic probing works. Let's dive right in. So let's recall how we insert key value pairs into a table of size and using the open addressing collision resolution schema. So first we initialize a variable called x to be one, which we're going to increment every time we're unable to find a free slot. Then we compute the key hash. And that's going to be our first index, we're going to check and we're going to loop while we're unable to find a free slot, meaning the table at that index is not equal to null, so it's already occupied.

Every time that happens, we're going to offset the key hash using our probing function. Our probing function in our case is going to be a quadratic function. And then we also increment x and eventually we will find an open slot to insert our key value pair. So what is the idea behind quadratic probing? So quadratic probing is simply probing according to a quadratic formula, or specifically when our probing function looks something like p of x equals A x squared plus bx plus c and a, b, and c are all constants, and we don't want a equal to zero, otherwise we degrade to linear probing. But as we saw in the previous videos, not all quadratic functions are viable because they don't produce a cycle of order and we might get stuck in an infinite loop.

So as it turns out, most randomly selected quadratic probing functions will end up producing a cycle. Here's an example suppose we chose our preferred function to be p of x equals two x squared plus two, the key we wanted to insert hash to four and the current table size was nine, then we would end up with a two cycle. So first time around, we would probe at position zero, we would get four, but position one, and get seven. Suppose those two entries are full, and then we would end up in a cycle again. So our probing function is only ever able to hit the buckets, four and seven. So it makes it impossible to reach all the other buckets, 012356 and eight.

So we're stuck in an infinite loop when four and seven are already occupied. This is really, really bad. So so the question then is, how do we pick a probing function which always works? The answer is There are numerous ways, but here are the three most popular ways I have found. So the first way is to select the probing function to be p of x equals x squared. And to keep the table size a prime number greater than three, and make sure our load factors always kept below one half or less than or equal to one half.

The other one is to say our probing function equals x squared plus x divided by two and make sure the table size is a power of two. And the last and final one says that p of x should be the alternating sign of x squared and keep the table size a prime number where n is congruent to three month four. For example, we could say that I were table size was 23 because That's a prime number, and it's congruent to three mod four. So any of these will work. But as you see, they're very specific and how they work and what the table size should be. And that's a common theme in quadratic probing.

So we're going to focus on the second one where p of x equals x squared plus x divided by two and the table size is a power of two. Alright, suppose we have an initially empty hash table, and we want to insert some key value pair, and we're using the following quadratic probing function, p of x equals x squared plus x divided by two, and the table size is a power of two, so it's eight. And let's select the load factor to be point four. Therefore, the table threshold is going to be three. So just emphasize That the table size must absolutely be a power of two, otherwise this will not work. Okay, so let's insert the first guy.

So suppose that k one hash is six. Then we're going to insert k one at position six. Right next k two, suppose k two is equal to five, then we're going to insert it at five, no collision there. Suppose k threes equal to five, then we have a collision, so we need to handle that. So we're going to try probing an offset one. So that brings us to six.

So we probe again, and that brings us to index zero which is free. So we're going to insert k three and V three key value pairs there. Let's insert key four. But before we can do that, we've reached the table thresholds, so we have to resize the table first. Okay, so let's allocate a new block of memory. And let's double the size of the table to keep it a power of two.

So our new table size is 16 max load factor doesn't change, however, a new threshold is six, and the probing function doesn't change. So we need to place the entries in the old hash table into the new hash table. So from before, we know that k three hash to five, so we're going to put it at index five, so we have collision there. And no element at position one, two, or four. And we could position five and find key two there. So we know from before that key two also has to five.

So we're going to try a preposition five, but there's a hash collision, so we probably One, and then we get five plus one equals six. So position six, we're insert k two. Now let's try insert k one. And we have from before k one hash two, six, but we can't put it there because we have a collision. So we're going to probe along. So we're going to put it in position seven.

All right, and that does it for resizing the table. So let's keep going, we serve a few more elements to insert inside our table. So suppose i k four equals 35,410. So when we made that by 16, that gives us position two. So we're going to say k for V for position two. So we've already seen k three, and we know it's hash value is equal to five.

So since k three is already in our hash table, we're going to performing an update. So k three plus the proving function zero gives us five. So let's update value to be V five instead of v3, which it was before. So suppose that the key k six hash to minus 6413. So that hashes to three months 16. So that's why it's free.

So assuming insert it and last one, k seven, suppose hashes to to, well, we have a collision right there. So let's probe along. So when we probe, our probing function gives us an offset of one that's also taken so probably can. So now we are at position five, but that's also taking so keep probing again. So we probe for a fourth time scan offset of six. So that gives us eight and that slot is free.

We're going to insert that there. Alright, and that's how quadratic probing works in a nutshell. Guys, if you like this video, please subscribe and in the next video we're going to be talking about the double hashing technique. So thank you for watching. Catch you next time.