Transcript

The following content is provided under a Creative Common License. Your support will help MIT Open Courseware continue to offer high-quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT Open Courseware at ocw.mmit.edu. All right, let's get started. Today we're going to continue the theme of randomization and data structures. Last time we saw skip listless. Skip list uh solve the predecessor successor problem. You can search for an item and if it's not there, you get the closest item on either side in login with high probability.

Um but we already knew how to do that deterministically. Today we're going to solve a slightly different problem, the dictionary problem uh with hashts. Something you already think you know, but uh we're going to show you how much you didn't know, but after today you will know. And we're going to get constant time uh not with high probability. That's hard, but we'll do constant expected time. So uh that's in some sense better. It's going to solve a weaker problem, but we're going to get a tighter bound constant instead of logarithmic. Um, so for starters, let me remind you uh what problem we're solving and the basics of hashing which you learned in 6006.

I'm going to give this problem a name because it's important. And we often forget to distinguish between uh two types of things. Um it's kind of an old term, but I would call this an abstract data type. This is just the uh problem specification of what you're trying to do. Uh you might call this an interface or something. This is a problem statement versus the data structure is how you actually solve it. that hashts are the data structure, dictionary is the problem or the abstract data type. Uh so what we're trying to do today uh as in most data structures is maintain a dynamic set of items. Uh and here I'm going to distinguish between the items and their keys.

Each item has a key and normally think of there also being a value like in Python. Uh, but we're just worrying about the keys and moving the items around. Uh, and we want to support three operations. Uh, we want to be able to insert an item, uh, delete an item, and search for an item. But search is going to be different from uh what we know from AVL trees or skip list or even venom DOS. Uh that was a predecessor successor search. Here we just want to know uh sorry you're not searching for an item. Usually you're searching for just a key. Here you just want to know is there any item with that key and return it.

This is often called an exact search because if the key is not in there, you learn absolutely nothing. You don't you can't find the nearest key. And for whatever reason, this is called a dictionary problem. That's unlike a real dictionary. Usually, when you search for a word, you do find its neighbors. here uh we're just going to either if the key is there we find the item otherwise not and this is exactly uh what a Python dictionary implements uh so I guess that's why Python dictionaries are called uh dicts so uh today I'm going to assume all items have distinct keys so in the insertion I will assume uh key is not already in the uh with a little bit of work you can allow there to be allow inserting an item with an existing key and you just overwrite that that existing item but I don't want to worry about that here right so we could of course solve this using an AVL tree and in login time uh but our goal is to do better because it's a an easier problem and I'm going to remind you of the simplest way you learned to do this which was hashing with chaining in 006 and the catch is you didn't really analyze this in 006 so we're getting constant time per operation that's going to be expected or something uh and linear space and the remember the uh variables we care about there's uh u n and m so u is the size of the universe this is the all possible keys the space of all possible keys n is the size of your the set you're currently ly storing.

So that's the number of items or keys uh currently in the data structure. Uh and then m is the size of your table. So I'll say it's the number of slots in the table. So you remember the picture you have a table of slots uh say 0 to n minus one each of them is a pointer to a linked list. Um and if you have let's say over here is your universe of all possible keys. Uh then we have a hash function which maps each universe item uh into one of these slots and then the linked list here is storing all of the items that hash to that slot. All right. So uh yeah so we have a hash function which maps the universe.

I'm going to assume the universe has already been mapped into integers 0 to u minus one and it maps to slots. Okay. And when we do hashing with chaining think I mentioned this last week the bounds you get we achieve bound of uh 1 + alpha where alpha is the load factor n / m the average number of items you'd expect to hash to a slot. It's the number of items divided by a number of slots. Okay. Um and you proved this in 66, but you assumed uh something called simple uniform hashing. Simple uniform hashing is an assumption uh I think invented for CLRS. It makes the analysis very simple but it's also basically cheating.

So today our goal is to not cheat. It's nice as a warm-up but we don't like cheating. So um you may recall the the the assumption is about the hash function. You want a good hash function and good means this. I want the probability of two distinct keys mapping to the same slot to be one over m. There are m slots. If everything was completely random, if h was basically choosing a random number for every key, uh then that's what we would expect to happen. So this is like the idealized scenario. Now we can't have a hash function choosing an arbit a random number for every key because it has to choose the same value if you give it the same key.

So it has to be some kind of deterministic strategy or at least repeatable strategy where if you plug in the same key you get the same thing. Uh so really what this assumption is saying is that uh the keys that you give are uh in some sense random. If I give you random keys and I have a not too crazy hash function, then this will be true. Uh but I don't like assuming anything about the keys. Maybe I want my keys to be worst case. Maybe uh and there are lots of examples in in the real world where uh you apply some hash function. It turns out your data has some very particular structure and if you choose a bad hash function then uh your hash table gets really really slow.

Maybe everything hashes to the same slot. Uh or you know say you take well yeah lots of examples of that. Uh we want to avoid that. After today you will know how to achieve uh constant expected time no matter what your keys are for worst case keys. Okay. But it's going to take some work to do that. So this assumption requires assuming that the keys are random and this is what we would call an average case analysis. You might think that average case analysis is necessary for randomized algorithms, but that's not true. Uh, and we saw that last week with quicksort. Quicksort, if you say, uh, I will always choose a of one to be my partition element.

That's what the textbook calls basic quicksort. Uh, then for an average input, that will do really well. If you have a a a uniform random permutation of items and you sort with the method of always choosing the first item as your partition uh then that will be n login uh on average if your data is average but we saw you could avoid that assumption by choosing a random pivot. If you choose a random pivot then you don't need to assume anything about the input. You just need to assume that the pivots are random. So there's a big difference between assuming your inputs are random versus assuming your coin flips are random.

It's pretty reasonable to assume you uh can flip coins uh if you've got enough dexterity in your thumb then you can do it. Uh but it's not so reasonable to assume that your input is random. So we'd like to avoid uh average case analysis whenever we can and that's the goal of today. So what you saw in 006 was essentially assuming the inputs are random. We're going to get rid of that unreasonable assumption today. Okay, so that's uh in some sense review from 006. I'm going to take a brief pause and tell you about the etmology of the word hash in case you're curious. Um hash is a English word since the uh 1650s, so it's pretty old.

Um it means uh literally cut into small pieces. It's usually used in a culinary sense. Uh like these days you have corn beef hash or something. Put the definition over here. Uh it comes from French. uh hashe uh which means uh to chop up. Okay. Uh you know it in English from the word hatchet. So it's the same derivation and it comes from old French. uh I don't actually know whether that's hashe or hash but uh uh which means axe. Okay, so you can see the derivation. Um that's if you look this up in OED or what or pick your favorite dictionary or even Google uh that's what you find. But in fact uh there's a a new prevailing theory that in fact hash comes from uh another language uh which is Vulcan uh la ash I mean you could see the derivation right uh actually means axe so maybe French got it from Vulcan or vice versa but I think I think that's pretty clear uh live long and prosper and uh farewell to Spock sad news of last week.

Okay, so enough about hashing. We'll come back to that in a little bit. Uh, but hash functions essentially take up this idea of taking your key, chopping up into pieces, and mixing it like in a good dish. All right, so uh we're going to cover two ways to get uh strong constant time bounds. Uh what the probably the most useful one is called universal hashing. We'll spend most of our time on that. Uh but the theoretically cooler one is called perfect hashing. Universal hashing, we're going to guarantee there are very few conflicts in expectation. Perfect hashing, we're going to guarantee there are zero conflicts.

Uh the catch is uh at least in its obvious form, it only works for static sets. If you're if you uh forbid insert and delete and just want to do search, then perfect hashing is a good method. So like if you're actually storing a dictionary um like the OED, you know, English doesn't change that quickly. So you can afford to recomputee your data structure whenever you release a new addition. All right. Uh but let's start with universal hashing. This is a nice powerful technique. It works for dynamic data. Insert, delete, and search will be constant expected time with no assumptions about the input.

So it will not be average case. that's in some sense worst case but randomized. So the idea is we need to do something random. If you just say well I choose one hash function once and for all and I use that for my table. Okay, maybe my table doubles in size. I change the hash function. But um there's no randomness there. What we we need to introduce randomness somehow into this data structure. And uh the way we're going to do that is in how we choose the hash function. We're going to choose our hash function uh randomly from some set of hash functions call it capital H. This is going to be a universal hash family.

We're going to imagine there are many possible hash functions we could choose. If we choose one of them uniformly at random, that's a random choice. And that randomness is going to be enough that we no longer need to assume anything about the keys. So uh for that to work we need some assumption about capital H. You know maybe it's just a set of one hash function that wouldn't add much randomness. Two also would not add much randomness. We need a lot of them. And so we're going to require H to have this property and we're going to call it the property universality. Uh generally you call it a universal hash family just a set of hash functions.

What we want is that um so we're choosing our hash function little h from big h and among those choices we want the probability that two keys hash to the same value to be small I'll Okay. And this is very similar looking to universal sorry to simple uniform hashing looks almost the same here except I switched from K1 and K2 to K and K prime but same thing. Um but what we're taking the probability over what's we're assuming is random is different here. We're assuming K1 and K2 are random because H was fixed. This was an assumption about uh the inputs over here. We're thinking of K and K prime as being fixed.

This has to work for every pair of distinct keys. And the probability we're considering is the distribution of H. So we're trying all the different H's or we're trying them trying little H uniformly at random. We want the probability that a random H makes K and K prime collide to be at most 1 over M. Okay. The other difference is we switch from equals to at most. Um doesn't I mean less would be better and there are ways to make it less for a couple pairs but it doesn't really matter. Um but of course anything less than or equal to 1 / m will be just as good. So this is an assumption about capital h.

We will see how to achieve this assumption in a little bit. Let me first uh prove to you that this is enough. Uh it's going to be basically the same as uh the 006 analysis, but it's worth repeating just so we are sure everything's okay and so I can be more precise about what we're assuming. The key difference between this theorem and the 006 theorem is we get to assume we get to make no assumptions about the keys. They are arbitrary. You get to choose them however you want. But then I choose a random hash function without the hash function cannot depend on these keys. But it's going to be random.

And I choose the hash function after you choose the keys. That's uh important. So we're going to choose a random little h in big h and we're assuming uh big h is universal. Then the expected number of keys in a slot among those n keys is at most uh 1 plus alpha. Alpha is n / m. So this is exactly what we had over here. uh here we're talking about time bound but the time bound followed because the length of each chain uh was expected to be 1 plus alpha and here the expectation is over the choice of h right not assuming anything about the keys so uh let's prove this theorem it's pretty easy but uh I'm going to introduce some analysis techniques that we will use for uh more interesting things.

So, let's uh give the keys a name. I'll just call them uh K0 up to I'll be lazy. Use K1 up to KN. Okay. And I just want to compute that expectation. So I want to compute um let's say the number of keys colliding with one of those keys let's say uh ki So uh this is of course the size of the slot that ki happens to go. This is going to work for all i. And so if I can say that this is at most one over alpha for each i then I have my theorem. Okay just another way to talk about it. Now the number of keys colliding with ki here's a general trick. If whenever you want to count something in expectation a very helpful tool is indicator random variables.

Let's let's name all of the different events that we want to count and then we're basically summing those variables. So I'm going to say uh I'm going to use I capital I I J to be an indicator random variable. It's going to be one or zero. One if uh hash function of AI equals the hash function of KJ. So there's a collision between KI and KJ and zero if they hash to different slots. Okay. Now this is it's a random variable because it depends on H and H is a random thing. KI and KJ are not random. They're they're given to you. And then I want to know uh when does H map those two uh keys to the same slot.

And so this number is really just the sum of iig j over all j. Right? This is the same thing. The the number in here is the sum for j not equal to i of i i i j because we get a one every time they collide zero otherwise. So that counts how many collide. Once we have it in this notation, we can use all the great uh lemas and theorems about uh in this case e expectation. Uh what should I use here? What's a good uh how can I simplify this formula? Linearity of expectation. Thank you. If you don't know all these things, read the probability appendex in the textbook. So we want to talk about expectation of the simplest thing possible.

So linearity lets us put the e inside the sum without uh losing anything. Now the expectation of an indicator random variable is pretty simple because the zeros don't contribute to the expectation. The ones contribute one. So this is the same thing as just the probability of this being one. Okay. So we get uh sum of j not equal to i of the probability that i i j equals 1. And the probability that iig equals 1. Well, that's the probability that this happens. And what's the probability that that happens? Uh at most one over m by universality. So I'm gonna I'll write it out. This is sum j not equal to i.

Probability that h maps k i and kj to the same slot. So that's because it's an indicator. Sorry, that's the definition of iig. And uh this is at most sum j not equal to i of 1 / m by universality. So here's where we're using it. uh and sum of j not equal to i. Well, that's that's basically n. Uh but I made a mistake here slightly off um from here. Yeah. So this this uh line is wrong. Sorry, let me fix it. Uh because this assumption only works when the keys are distinct. So uh in fact yeah how did I get J? Yeah. Yeah sorry this should have been this uh actually everything I said is true but uh if you want to count the number of keys I really wanted to count the total number of keys that hash the same place as uh ki.

So there's one more which is ki itself always hashes to wherever ki hashes. Okay. So I did a summation of j not equal to i but I should also have a plus i I I captain. So uh there's the case when i hashing to the same place uh which of course is always going to happen. So you get um basically plus one everywhere. Okay. So that's makes me happier because then I actually get what the theorem said which was one plus alpha. There's always going to be the one guy hashing there when I assume that ki hash to wherever it does. Okay. So this tells you that if we could find a universal hash family then we're guaranteed insert delete and search cost uh order one plus alpha in expectation.

And the expectation is only over the choice of h not over the inputs. I think I've stressed that enough times. Uh but the remaining question is can we actually design a universal hash family? Are there any universal hash families? Uh yes, as you might expect there are. Otherwise this wouldn't be very interesting. Okay, let me give you an example of a bad universal hash family. Sort of an oxymoron, but uh it's possible. Uh bad. Uh here's a hash family that's universal. H is the set of all hash functions. H from 01 to U minus one. This is what's normally called uniform hashing. It makes analysis really easy uh because uh you get to assume I mean this says a ahead of time for every universe item I'm going to choose a random slot to put it and then just I'll just remember that.

And so whenever you give me a key, I'll just map it via H and I get a consistent slot. And definitely it's universal. What's bad about this hash function? Many things, but sorry. That's just as hard as the problem. Sort of the I'm begging the question. It's just as hard as the problem I'm solving. And what algorithmically what goes wrong here? They're two things I guess. Yeah, it's not deterministic. It's not deterministic. Um, that's okay because we're allowing randomiz randomization in this algorithm. So, uh, I mean, how I would compute this is for I would do a for loop over all universe items and I assume I have a way to generate a random number between 0 and n minus one.

That's legitimate, but there's something bad about that algorithm. It's not consistent. Not consistent. It is consistent. If I premputee for every universe item where to map it, that's good. Uh, so all these things are actually okay. It takes too much time. It takes too much time and space. Yeah. Uh, that's the the bad thing. It's hard to isolate in a bad thing. What is so bad about it? But um we need U time to to compute all those random numbers and we need U space to store that hash function. In order to get consistency, we have to uh Whoops. Good catch. In order to get consistency, we need to keep track of all those hash function values.

Uh and that's that's not good. You could try to not store them all, you know, use a hash table, but you can't use a hash table to store a hash function. That would be that would be infinite recursion. Um, so but you know, at least they're out there. So the challenge is to find an efficient hash family that doesn't take much space to store and doesn't take much time to compute. Okay, we're allowing randomness, but But we don't want too much randomness. We can't afford U units of time of randomness. I mean, U could be huge. We're only doing N operations probably on this hash table. You could be way bigger than N.

We don't want to have to premp compute this giant table and then use it for like five steps. That would be really, really slow, even amortized. So, um, here's one that I will analyze. And there's another one in the textbook which I'll mention. This one's a little bit simpler to analyze. We're going to need a little bit of number theory, just prime numbers. Uh, and you probably heard of the idea of your hasht size being prime here. You'll see why that's useful, at least for this family. You don't always need primality, but it's going to make this family work. So I'm going to assume that my table size is prime.

Now really my table size is doubling. Uh so that's a little awkward but luckily there are algorithms given a number to find a nearby prime number. We're not going to cover that here. Uh but that's an algorithmic number theory thing. Uh and in poly logarithmic time I guess you can uh find a nearby prime number. So you want it to be a power of two and you'll just uh look around for nearby prime numbers. And then we have a prime that's about the same size. So that will work just as well for from a table doubling perspective. Okay. Then furthermore, uh for convenience, I'm going to assume that u is an integer power of m.

I want my universe to be a power of that prime. Um, I mean, if it isn't, just make you a little bigger. It's okay if you gets bigger as long as it covers all of the same items. Okay. Now, once I view my universe as a power of the table size, a natural thing to do is take my uh universe items to take my input integers and think of them in base m. So, that's what I'm what I'm going to do. I'm going to view a key k in base m. Whenever I have a key, I can think of it as a vector of sub keys k1 up to k uh r minus one. There are digits in base m because of this relation. uh and I don't even care which is the least significant and which is the most significant that won't matter.

So whatever whichever order you want to think of it um and each of the kis here I guess is between zero and m minus one. So, so far so good. So, uh with this perspective, the basm perspective, I can define a dotproduct hash function as follows. It's going to be parameterized by another key. I'll call it a which we can think of again as a vector. I want to define h sub a of k. So this is parameterized by a but it's a function of a given key k as the dotproduct of those two vectors mod m. Uh so remember dotproduct is just the sum from i = 0 to r minus one of a i * ki. I want to do all of that modulo m.

We'll worry about uh how long this takes to compute in a moment I guess. Um maybe very soon. But the hash family H is just all of these HAS's for all possible choices of A. A was a key. So it comes from uh the universe U. And so what that means is uh to do universal hashing, I want to choose one of these HA uniformly at random. How do I do that? I just choose a uniformly at random. Pretty easy. It's one random value from one random key. So that should take constant time and constant space. Store one number. Okay. In general, we're in a world called the word RAM model. This is actually uh I guess M stands for model.

So I shouldn't write model. Uh random access machine. uh and which you may have heard of. The word RAM assumes that uh we're you know in general we're manipulating integers and the integers fit in a word and the computational assumption is that manipulating um a constant number of words and doing essentially any operation you want on a constant number of words uh takes constant time. And the other part of the word RAM model is to assume that the things you care about fit in a word. Say uh individual data values. Uh here we're talking about keys fit in a word. uh this is what you need to assume say in venom debose that you can compute high of x in constant time or low of x in constant time here I'm going to use it to assume that we can compute h sub a of k in constant time uh in practice this would be done by implementing this computation this dotproduct computation in hardware and the reason you know a 64-bit edition on a modern processor or 32-bit on most phones takes constant time is because there's hardware that's designed to do that really fast.

And in general, we're assuming uh that the things we care about fit in a single word. Uh and we're assuming random access and that we can have arrays. That's what we need in order to store a table. And same thing in Vano Devos, we needed to assume we had arrays. Okay. So, um I think this operation is actually pretty uh exists in Intel architectures in some form. Uh but it's certainly not a normal operation. If you're going to do this explicitly, adding up and multiplying things, this would be r is the log base m of u. So it's kind of logish time. Um maybe I'll mention another hash family that's more obviously computable, but I won't analyze here.

It's analyzed in the textbook though, so if you're curious, you can check it out there. Um let's call this Just another bit weird because it has two mods. You take mod p and then mod m. But the com the main computation is very simple. You choose a uniformly random value a you multiply it by your key in usual binary multiplication um instead of dotproduct and then you add another uniformly random key. This is also universal. Uh so capital H is uh hab for all A and B that are keys. Okay. Okay. So if you're not happy with this assumption that you can compute this in constant time, you should be happy with this assumption.

If you believe in addition and multiplication and division being constant time, then this will be constant time. Okay. Uh so both of these families are universal. I'm going to prove that this one is universal because a little bit easier. Yeah. Ah okay. Right. What is P? uh P just has to be bigger than M and it should be prime. It's not random. You can just choose one prime that's bigger than your table size and this will work. Uh I am um I forget whether you have to assume that M is prime. I have to check. I'm guessing not, but don't quote me on that. Uh that was check the section on the textbook.

Okay, so good, easy to compute. The analysis is simpler, but it's a little bit easier here. Essentially, this is very much like uh products, but there's no carries here from one uh when we do the dot productduct instead of just multiplying in base m. If we multiply it in base m, that would give the same thing as multiplying in base 2. uh but we get carries from one msized digit to the next one and that's just more annoying to think about. So here we're essentially getting rid of carries uh so it's in some sense even easier to compute and in both cases it's universal. Okay. So we want to prove this property that if we choose a random A then the probability of two keys K and K prime which are distinct mapping via H to the same value is at most 1 over M.

So let's prove that. So we're given two keys. We have no control over them because this has to work for all keys that are distinct. The only thing we know is that they're distinct. Now, if two keys are distinct, then their vectors must be distinct. If two vectors are distinct, that means at least one item must be different. Should sound familiar. Um, so this was like in the matrix multiplication verification algorithm that taught taught. Um so uh k and k prime differ in some digit. Let's call that digit d. So uh k subd is different from k subd prime. Okay. And I want to compute this probability.

Rewrite it. The probability is over a. I'm choosing a uniformly at random. I want to know the probability that that maps K and K prime to the same slot. Okay. So let me just uh write out the definition. It's probability over a that the dotproduct of a and k uh is the same thing as when I do the dotproduct with k prime. uh mod m these two val sums should come out the same mod m. Okay. Uh so let me move this this part over to this side. Uh because in both cases we have the same AI. So I can group terms and say this is the probability Probability sum over i = 0 to r -1 of a i * k i - k i prime equals z modulo m Okay.

Okay. No pun intended. Uh now we care about this digit D. D is a place where we know that this is non zero. So let me separate out the terms for D and everything but D. So this is the same as probability of let's do the d term first. So we have a d time k d minus k d prime that's one term. I'm going to write the summation of uh i not equal to d of a i k i minus k i prime. These ones, some of them might be zero, some are not. Uh, we're not going to worry about it. It's enough to just isolate one term that is non zero. Right? So, this thing we know does not equal zero. Cool. Uh, here's where I'm going to use a little bit of number theory.

I haven't yet used that m is prime. I required uh m is prime because when you're working modulo m you have multiplicative inverses because this is not zero there's something I can multiply on both sides and get um this to cancel out and become one for every value x there's a value y such that x * y equals 1 modulo m and you can even compute it in constant time in a reasonable model. So uh then I can say I want the probability that a d is minus k d minus k d prime inverse. This is the multiplicative inverse I was talking about. And then this sum i not equal to d of whatever. I don't actually care what this is too much.

I've already done the equals part. Still need to write mod m. Okay. The point is this is all about a d. Okay. And remember we're choosing a uniformly at random. That's the same thing as choosing each of the AIS independently uniformly at random. Yeah. Is the second line over there isolated? This which uh this one this that the one below that yes is that is that line isolating D or No, I haven't isolated D yet. This is all the terms and then to going from this line to this one I'm just pulling out the the i equals d term. Okay, se that's this term and then separating out the i not equal to d. Right.

This this sum is just the same as that sum but I've done the d term explicitly. Sure. Yeah. Okay. So, uh I've done all this rewriting because I know that ad is chosen uniformly at random. And here we have this thing this monstrosity but it does not depend on a d. In fact it is independent of a d. I'm going to write this as a function of k and k prime because those are given to us and fixed. And then it's also a function of a z and a1 everything except d. Uh so a d minus one a d + one and so on up to a r minus one. This is awkward to write but everything except a d appears here because we have i not equal to d and and these a i's are random variables but we're assuming that they're all chosen independently from each other.

So I don't really care what's going on in this function. It's something. And if I rewrite this probability, this is probability over the choice of a I can separate out the choice of all these things from uh the choice of a d. And this is just a useful formula. Uh I'm going to write a uh not equal to d. All the other um maybe I'll write a sub i not equal to d. all the choices of those guys separately from the probability over choosing a d of a d equal to this function. Okay, if you just think about the definition of expectation, um this is doing the same thing. We're thinking of first choosing the AI's where I is not equal to D and then we choose A D and this computation will come out the same as that.

Okay. Uh but this is the probability of a uniformly random number equaling something. So uh we just need to think about uh sorry important that would be pretty pretty unlikely that would be one over u but this is all working modulo m okay so if I just take a uniformly random integer and the chance of it hitting any particular value mod m is 1 over m and that's universality. Yes. So in this case we get exactly 1 over m no less than or equal to sorry I should have written it's the expectation of 1 over m but that's one over m because one over m has no random parts in it. Yeah. How do we know that this expression doesn't have any biases in the sense that it doesn't give more more like if you give it a uniform distribution of numbers, it doesn't spit out more numbers than others and that could potentially Oh, so you're asking how do we know that this hash family doesn't prefer some slots over others?

I guess or like after after the equal sign like the the in this middle line in the middle. This one. Oh, this one. Middle board here. Yes. So, how do we know that random variables? It won't it won't prefer certain numbers over others. So, this function may prefer some numbers over others, but it doesn't matter. All we need is that this function is independent of our choice of ad. So you can think of this function. You choose all of these random actually K and K prime are not random but you choose all these random numbers. Then you evaluate your F. Maybe it always comes out to five. Who knows? It could be super biased.

But then you choose AD uniformly at random. So you're I mean the chance of AD equaling five is the same of the chance of AD equaling three. Uh so in all cases you get the probability is 1 over M. What we need is independence. We need that the A D is chosen independently from the other AIS. But we don't need to know anything about f other than it doesn't depend on AD. Yeah. So, and we made it not depend on AD because I I isolated AD by pulling it out of that summation. So, we know there's no ADS over here. Good question. Get a bonus Frisbee for question. Uh, all right. That ends universal hashing.

Any more questions? So at this point we have at least one universal hash family. So we're just choosing in this case a uniformly at random. In the other method we choose a and b uniformly at random. And then uh then we build our hash table and the the hash function depends on m. So also every time we double our table size we're going to have to choose a new hash function for the new value of m. Um and that's about it. So this will give us constant expected time uh or in general on one plus alpha if you're not doing table doubling uh for insert delete and exact search just building on the hashing with chaining and so this is a good method question uh yeah well so um I I wanted to isolate it is the overall probability ability of this happening.

I rewrote it this way because I wanted to think about first choosing the AIS where I does not equal D and then choosing A. So this probability was supposed to be only over the choice of AD. And you have to do something with the other AIS because they're random. You can't just say what's the probability of AD equaling a random variable. That's a little sketchy. I wanted to have no random variables overall. So I have to kind of bind those variables with something. And I just want to add them. I just want to see what the this doesn't really affect very much but to make this algebraically correct I need to say what the AI's I not equal to D are doing other questions yeah I'm a bit confused about your definition uh yeah sorry this is a funny notion of colliding I just mean I want to count the number of keys that hash to the same slot as KI.

So it's not necessarily like a collision. You may not call it a collision when it collides with itself. Yeah. Uh whatever you want to call it, but I just mean hashing to the same slot as KI. Yeah. Just because I want to count the total length of the chain. I don't want to count number of collisions in the chain. Yeah, sorry. Probably poor choice of word. Uh, we're hashing because we're taking our key, we're cutting it up into little bits, and then we're mixing them up just like a good corn beef hash or something. All right, let's move on to perfect hashing. This is uh more exciting, I would say.

Even cooler. This was uh cool from a probability perspective. Depending on your notion of cool, uh, this method will be cool from a data structures perspective and a probability perspective. But it uh so far our data structures are what we know from 006. Now we're going to go uh up a level literally we're going to have two levels. Um so here we're solving you can actually make this data structure dynamic but we're going to solve the static dictionary problem which is uh when you have no inserts and deletes you're given the keys up front you're given n keys you want to build a table that supports search and that's it.

You want search uh to be constant time and perfect hashing also known as FKS hashing because it invented by Fredman Klo and Seamaretti 1984. Um what we will achieve is constant time worst case for search. So that's a little better because here we're just doing constant expected time for search, but it's worse and that we have to know the keys up in advance. Um, we're going to take linear space in the worst case. Uh, and then the the remaining question is how long does it take you to build this data structure? And for now, I'll just say it's polomial time. It's actually going to be nearly linear.

Uh and this is also an expected bound uh actually with high probability can be a little more strong here. So it's going to take us a little bit of time to build this structure but once you have it you have the the perfect scenario. There's going to be in some sense no collisions in our hash table. So it be constant times for search and linear space. So that part's great. The only catch is it's uh static, but beggars can't be choosers, I guess. All right. I'm not sure who's begging in that analogy, but the keys who want to be stored. I don't know. Um, all right. So big idea for uh perfect hashing is to use two levels.

So uh let me draw a picture. We have our universe and we're mapping that via hash function h1 into a table. Look familiar? Exactly the diagram I drew before. Okay. Okay, it's going to have some table size m and we're going to assume that m or we're going to set m to be within a constant factor of n. So right now it looks exactly like regular and this is going to be a universal h1 is chosen from a universal hash family. So uh you know universal hashing applies. The trouble is we're going to get some lists here and we don't we don't want to store the the uh set of colliding elements the set of elements to hash to that place with a linked list because link lists are slow.

Instead we're going to store them using a hash table. Sounds crazy but uh we're going to have so this is position one. This is going to be H2 comma one. It's going to be another hash function H2 comma 0 that maps to some other hash table. These hash tables are going to be of varying sizes. Some of them will be of size zero because nothing hashes there. Um but in general each of these slots is going to map instead of to a linked list to a hash table. Okay. So this would be h 2, m minus one. I'm going to guarantee in the second level of hashing there are zero collisions. Uh let that sink in a little bit.

Um let me write down a little more carefully what I'm doing. So H1 is picked from a universal hash family uh where m is theta theta n. Uh I want to put a theta. I mean, I could say M equals N, but sometimes we require M to be a prime. So, I'm going to give you some slop in how you choose M. So, it can be prime or whatever you want. Okay. And then at the first level, we're basically doing hashing with chaining. And now, uh, I want to look at each slot in that hash table. So between zero and n minus one I'm going to let l j be the number of keys that hash that's the length of the list that would go there.

It's going to be the number of keys among just the n keys. Uh, number of keys hashing to slot J. So now the big question is if I have LJ keys here, how big do I make that table? You might say, well, I make it theta LJ. That's what I always do. But that's not what I'm going to do. That wouldn't help. We'd get exactly I think the same number of collisions if we did that more or less in expectation. So we're going to do something else. We're going to pick a universal hash pick a hash function from a universal family H2, J. It again maps the same universe. The key thing is the size of the hash table I'm going to choose which is LJ squared.

So uh if there are you know three elements that happen to hash to this slot this table will have size nine. So it's mostly empty only square root fraction if that's a word uh if that's a phrase will be full most of it's empty y squared any ideas I claim this will guarantee zero collisions with decent chance. Yeah. With one probability with one half probability I'm going to end up with no collisions. Why? What's it called? Markov inequality would prove it. Uh but it's uh more commonly known as the whoa as the birthday paradox. Yeah. So the the whole name of the game here is the birthday paradox.

If I have uh how's it go? If I have n squared people with n possible birthdays, then is that the right way? No, less. If I have n people and n squared possible birthdays, the probability of getting a collision, a shared birthday is 1/2. Normally, we think of that as a a funny thing. You know, if I choose a fair number of people, then I get uh immediately a collision. I'm going to do it the opposite way. I'm going to guarantee that there's so many birthdays that no two of them will collide with probability of half. Now half's not great. We're going to fix that. So actually I haven't given you the whole algorithm yet.

Uh there are two steps one and two but there are also two other steps 1.5 and 2.5. So, but that's this is the right idea and this will make things work in expectation but I'm going to tweak it a little bit. Uh so first let me tell you step 1.5 it fits in between the two. Um I want that the space uh of this data structure is linear. So I need to make sure it is. If the sum j = 0 to n minus one of lj^2 is bigger than some constant times n. We'll figure out what the constant is later. Then uh redo step one. Okay. So after I do step one, I know how big all these tables are going to be. If the sum of those squares is bigger than linear, start over.

Okay. Okay, I need to prove that this this will only have to take this will happen um expected constant number of times login times with high probability. Uh in fact why don't we yeah let's worry about that later. Okay, let me first tell you step 2.5 which is I want there to be zero collisions in each of these tables. It's only going to happen with probability a half. So if it doesn't happen just try again. So 2.5 is while there's some hash function H2J that maps two keys that we're given to the same slot at the second level. uh this is for some uh j and let's say k i different from k i prime but they map to the same place by the first hash function.

Okay. So if two keys mapped to the same uh secondary table and there's a conflict uh then I'm just going to redo um that construction. So I'm going to repick H2J. H2J was a random choice. So um if I get a bad choice, I'll just try another one. Just keep randomly choosing the A or randomly choosing this hash function until there are zero collisions at that in that secondary table. I'm going to do this for each table. So, we worry about how long these will take, but I claim expected constant number of trials. So, let's do the second one first. Just write uh after we do this while loop, there are no collisions with the proper notion of the word collision, which is two different keys mapping to the same value.

So uh at this point we've guaranteed that searches are constant time worst case after we do all these four steps because uh we apply H1 we figure out which slot we fit in then we say it's slot J then we apply H2 2J. And if your item's in this in the overall table, it should be in that secondary table. Because there are no collisions, you can see is that one item the one I'm looking for. If so, return it. If not, it's not anywhere. If there are no collisions, then I don't need I don't need chains coming out of here because it's just a single item. Okay, the big question. So, constant worst case space because 1.5 guarantees that constant worst case time for search.

Uh the big question is how long does it take to build? How many times do we have to redo uh steps one and two before we get a decent before we get a perfect hasht. Okay. So uh let me remind you of the birthday paradox how why it works here. As uh mentioned earlier, this is going to be a union bound. We want to know the probability of collision at that second level. Well, that's at most the sum of all possible collisions, probabilities of collisions. So I'm going to say the sum overall i not equal to i j of the probability uh now this is over our choice of the hash function h2j of h2j of ki equaling h2 j of ki prime.

So union bound says of course the probability of any of any of them happening we don't know about interdependence or whatnot uh but certainly at most the sum of each of these possible events uh there are a lot of possible events there are if there's li things they're going to be li choose two possible collisions we have to worry about we know I is not equal I prime um so the number of terms here is li Uh, and what's this probability? One over LI at most because we're assuming H2J is a universal hash function. So the probability of choosing sorry LI squ the size of the table uh one over M but M in this case the size of our table is LI squ.

So uh the probability that we choose a good hash function in that these particular keys don't hit is at most 1 over li. This is basically li over two and so this is at most 12. This is slightly less than li over two. So this is at most a half and this is basically a birthday paradox in this particular case. That means there's a probability of at least a half that there are zero collisions in one of these tables. So that means I'm basically flipping a fair coin. If I ever get a heads, I'm happy. Each time I get a tails, I have to reflip. Should sound familiar from last time. Uh so this is um two expected trials uh or login with high probability.

Uh we proved login with high probability. Uh that's the same as saying the number of levels in a skip list is login with high probability. How many times do I have to flip a coin before I get a heads? Definitely at most login. Okay. Uh now we have to do this for each secondary table. There are m= theta n secondary tables. Uh and yeah uh there's a slight question of how big are the secondary tables? If a if one of these tables is like linear size then I have to spend linear time for a trial and then I multiply that by the number of trials and also the number of different things that would be like n squ n.

But you know a secondary table better not have linear size. Uh I mean a linear number of li equal n that would be bad because n li squar is n squ and we guaranteed that we had linear space. Um so in fact you can prove uh with another churnoff bound let me put this over here that all the li are pretty small not constant but logarithmic so uh li is order log n with high probability for each i and therefore for all i. So I can just change the alpha in my one minus one over n and to the alpha and get that for all i uh this happens. In fact the right answer is log over log log if you want to do some really messy analysis but uh we just logarithmic fine for us.

So what this means is uh we're doing n different things for each of them with high probability li is of size log n and then maybe we'll have to do like login trials repeating until we get a good hash function there. And so the total build time for steps two and 2.5 is going to be uh n at most n* log squar n. You can prove a tighter bound but that's it's polomial. That's all I wanted to go for and it's almost linear. So I'm left with one thing to analyze which is step 1.5. This to me is maybe the most surprising thing that it works out. Uh I mean here we we designed we did this Liy to LII squared so that birthday paradox would happen.

That's this is not surprising. I it's a cool idea but once you have the idea it's not surprising that it works. Uh what's a little more surprising is that squaring is okay from a space perspective. 1.5 says we're going to have to rebuild that first table until the sum of these squared lengths is at most linear. I can guarantee that each of these is logarithmic. So the sum of the squares is at most like n log 2 n. But I claim I can get linear. Okay, let's do that. So for step 1.5 we're looking at what is the expectation of the sum of the LJ squares being more than linear. Oh sorry expectation um let's first compute the expectation then we'll talk about a tailbound um which is the probability that we're much bigger than the expectation.

First thing is I claim the expectation is linear. So uh again whenever we're counting something I mean this is basically the total number of pairs of items that collide at the first level right uh with double counting. So I mean if you think of LJ and then I make a complete graph on those uh LJ items that's going to have like square number of edges. So if I also multiply by two. So this is the same thing as counting how many pairs of items map to the same spot the same slot. So this is going to and that I can write as an indicator random variable which lets me use linearity of expectation which makes me happy because then everything's simple.

So I'm going to write I I J this is going to be uh one if H1 of I sorry of KI I guess equals H1 of KJ and it's going to be zero if H1 oh otherwise right this is the total number of pairways colliding items including I versus I. Uh and so like if LI equals 1, LI squ is also one. There's one item colliding with itself. So this actually works exactly. All right, with the wrong definition of colliding if you bear with me. Uh so uh now we can use linear of expectation and put the E in here. So this is sum i = 1 to n sum j = 1 to n of the expectation of iig. But we know uh the expectation of iig is the probability of it equaling one because it's an indicator random variable.

Probability of this happening over our choice of h1 is at most one over m by universality. Here it actually is m because we're at the first level. So this is at most 1 / m which is theta n so um uh when i does not equal j. So uh it's a little bit annoying. I do have to separate out the uh the i terms from the i and different i not equal to j terms. But there's only I mean it's basically the diagonal of this matrix. there's n things that will always collide with themselves. So we're going to get like n plus uh the number of i not equal to j pairs double counted. So it's like 2 * n choose 2. Uh but we get to divide by m.

So this is like n^2 over n. So we get uh order n. Okay. So that's that's not well that's cool. expected space is linear. This is what makes everything work. Uh last class was about getting with high probability bounds when we were working with logs. When you want to get that something is log with high probability, you have to use with respect to n you have to use a choff bound. But this is about now I want to show that the space is linear with high probability. Linear is actually really easy. You can use a much weaker bound called Marov inequality. So I want to claim that the probability of H1 uh of this thing uh LJ squares being bigger than some constant times N is at most uh the expectation of that thing divided by CN.

This is Marov's inequality holds for any thing here. by just repeating it over here. Okay, so this is nice because we know that this expectation is linear. So we're getting like a linear function divided by CN. Remember, we get to choose C. The step said if it's bigger than some constant times N, then we're redoing the thing. So I can choose C to be 100, whatever. I'm going to choose it to be twice this constant. And then this is at most a half. Okay, so the probability of my space being too big is at most a half. We're back to coin flipping. Every time I flip a coin, if I get a heads, I have the right amount of space at less than CN time space.

Uh less than C * N space. Um if I get a tails, I try again. So the expected number of trials is two at most. not trails trials and uh it's also login trials with high probability how much time do I spend for each trial linear time I choose one hash function I hash all the items I count the number of collisions squared or number the sum of LJ squ that takes linear time to do and so the total work I'm doing for these steps is n log n. So n log n to do step one and one prime. N log squ n to step to do steps two and two prime overall n poly log or polomial time. Uh and we get guaranteed no collisions for static data.

Uh constant worst case search and linear worstase space. This is kind of surprising that this works out, but everything's nice. Now you know hashing.

Seek backward 5s ←
Longer seek (10s) Shift ←
Play Space Seek forward 5s →
Longer seek (10s) Shift →
0:00 Auto-scroll A Copy link at current time S

8. Randomization: Universal & Perfect Hashing