Video 3-9: Uniform Chaining Hashing Analysis

0:03 In the last part of this fundamental data structures uh unit, we'll talk about hashing. So let me briefly recap um what that is and also tie it a bit to the um binary search tree part because in a way you could ask um aren't the binary search trees the best we can even hope for? uh what we've seen so far was essentially stuck at this beta login barrier. We couldn't get any operations really faster than that. And you could ask um a question that in theoretical computer science you always want to ask is there a way to do it better or if I fail to be able if I cannot do it better is there a reason I'm am I just stupid or is there some fundamental reason that stops me from making progress and the answer is yes and no uh in a specific model of what is allowed this is best possible and specifically here in the comparison model. So assuming that all I can do to the keys is ask which of two keys is smaller or larger.

1:15 Uh then indeed I need login comparisons for implementing such a search in a in a symbol table even and therefore of course I can't do the operations faster than that. Uh the proof is is rather straightforward. Um, we'll see a more uh spelled out version of this decision tree argument in the sorting chapter briefly. So, I'm I'm here going to be brief. Um, every algorithm that uses comparisons, you can think of as a tree where when you ask a comparison, there's two outcomes. Either the question is is true or false. And then there's two branches where you could continue. If all I care about an algorithm is how many comparisons it asks, it looks really just from the outside like such a tree, it may ask at some point a question. I answer it and then it follows one of the two branches and then maybe it asks more questions. At some point it's done and then I can say the depth in this in this decision tree that is the cost of the algorithm.

2:23 Now, for um searching in a symbol table, if I have n keys stored, there are at least these n plus one different outcomes where um I'm looking up the value of n different keys and maybe there's a another one for not found, right? And so this decision tree of any correct algorithm for searching in a in a simple table needs to have at least n plus one leaves. And it is a binary tree because all I can do is do a a branch in two cases is my key that I'm looking for smaller equal than this key Xi. And so um we already worked out couple of times now that if I have a binary tree with a certain number of leaves, it needs to have log the number of leaves rounded up um in height. And so any correct algorithm on some of these inputs at least needs to spend login comparisons which means up to constant factors you can still debate what is in front of the login but up to that apart from that uh binary search trees are best possible.

3:34 So what are we doing here with hashing like am I telling you something impossible? Now any such lower bound has two messages to tell. One message is you cannot do better. You shall not pass. But it also has the story of what assumptions are made in such a statement. And if you break those assumptions, you may do better potentially. Here for example, the crucial thing was in the comparison model. So let's leave the comparison model behind and then suddenly things may improve.

4:14 And that's precisely what hashing does. Um it assumes more about the keys. In particular, it assumes that there are just numbers. Uh in practice, um like taking a a quick step back, in practice, you apply hashing to all sorts of objects. And hashing in implementations like in Java kind of is two steps mingled together. There's one step that takes an arbitrary object and turns it into an int, the hash code. That's what Java calls hash code. And then that int is still the full range of an integer. So that is what we would call the universe here. It's some set of integers. Now you also have collisions at this level of the mapping because uh potentially different objects have the same hash code. But because the range of hash code is all integers, four billion, that's often enough so that you can spread out the objects you have. So we'll mostly ignore this collision, the collisions at this first stage. If you want to be a bit more um careful about this, you could use some more cryptographic hash function where the range is bigger and where at least it's not easy to find two different objects or two different strings that collide.

5:32 uh we abstract from this here for the data structures and say we already have this first level done. The input is just numbers x1 up to xn.

5:42 Then we have a table which is just an array where you can store things by index and this has um size m and how this relates to n is is guided by this load factor. So the number of keys divided by the table size is is this alpha. And then the the star of the show is the hash function which is a mapping from all possible keys from our universe to positions in our table. And note that this universe you should think of this as being really big. It might be all all integers all 64-bit integers say and then um you're not going to usually have enough space for storing that. So this hash table uh this hash function needs to somehow be fast to compute and small to store. The key idea of hashing then of course is you take an element x this number from your universe. You apply the hash function that gives you an index in the table and that's where you should find this element.

6:49 Um sometimes we call also call this the bucket of item X. Now now get put delete these essentially are accesses to this array T. Now but of course this only works if every object gets a different index then I can simply store the element there. This is almost never true for hashing. Uh again you can do a bit of of math there that I'm I'm uh short uh that I'm shortcutting here. If this universe the number of possible uh keys that you could have is much larger than the table size and this will almost always be the case. It's kind of always then collisions are inevitable. you will have two different keys that have the same slot in the table. And even this is a likely event. The fact that um this is what what's behind this is this this birthday paradox statistical um uh toy problem. You have a room full of uh of n people. How many people do you need? So that it's with probability 1/2 that two people have the same birthday. And it turns out this is around the size of a school class. Uh maybe shockingly small.

8:11 So the same for hashing means if you don't have very very few keys in your hash table, usually you'll see some collisions. So you have to deal with those. And of course there's um various ways to do that. Uh the two big ones are either you have something like this on the side. Several keys are allowed to go to the same bucket and they form a list. All of them that hash to position two are inserted here. Uh the other big uh family of collision resolution um procedures is this open addressing where you allow the element not only to be stored in this in its bucket but maybe also some close by positions and there's various forms of how to do that. Uh we'll briefly come back to this but I'll mostly um talk about this this separate chaining which is also what Java does. Um it's a rather practical and simple scheme but has some some interesting uh analysis bits to it that algorithm data structures is is missing.

9:29 So um one one more thing that uh we occasionally have to do if if you think of this as a dynamic data structure. If I want to keep inserting elements then eventually my hash table is either strictly full in the sense of open addressing then I cannot put more elements in or I have very long such chains and it becomes unfavorable for the running time. Um so a typical practical um scheme for that is to keep this load factor in some certain range where the performance and space time trade-off is is decent and if it leaves that range then we throw away the old hash table and we rebuild the new one with the size chosen appropriately. Often times you get away with just doubling the memory. That's I think what Java still does for for hashmap and hashet. So if you're if you're adding more elements than uh you allow in your load factor then you double the size and that means you uh have to recomputee the position of all the elements currently in the hash in hash table and move them to the new array. That's again a linear time operation.

10:42 So you better use something like doubling arrays so that this at least doesn't happen too often. But all these hashts are fundamentally amortized. It's um much harder there to deamortize. Uh you can I guess you can apply the same same kind of tricks but you you have to deal with this smaller table and so on. This is not usually done.

11:12 Um for the following an analysis we'll assume that an operation um has as cost as as the primitive operation. the number of keys that we look at, number of positions that we have to check. And um how bad can that get? Well, if we're very unlucky, all your elements could hash to the same bucket and then we have say one long chain with all the elements in it. This is not a chain anymore. Then this is linear time and very bad. But the hope is that this will be unlikely.

11:51 What can we say about this? Let's first make an excursion to wishful thinking land where um we just wish for things to be nice. We've done that with binary search trees. So maybe um let's try the same again. Um for the analysis, the best possible scenario in a way is uh this assumption is called the uniform hashing assumption. And it's really an assumption. Okay, this is this is kind of a lie. It's almost never true. And we will see in a second that it kind of cannot be true most of the time. Um but for the analysis, it's still a useful guiding um guiding figure to uh to aim towards and some of the analyses work in a more restricted assumption as well. So the assumption here is that whenever you take uh some keys in your dictionary, the probability for two keys to have the same hash value is precisely what you would expect if they're random, which means one over m ch because I I've fixed one, right? I fixed the bucket of of x i. There's m buckets in total. If I choose a random one for xj, the chance that it will pick the same one is 1 / m.

13:09 Under this model, you can assume that the the buckets in the hash table are just uniformly identically distributed and uh are equally spread. And then we can try to analyze things based on that. Again, kind of unrealistic.

13:34 Uh but wait for a sec. We'll come back to that. Let's first see what we can do with this assumption even though it is a bit unrealistic.

13:52 Let's analyze separate chaining under this assumption of uniform hashing. So again I have my my hash table with buckets. Let's make it a bit more uh quantitative this time. I have m positions that I can hash into and then I'm collecting the elements in this bucket as a linked list.

14:15 Now if you think about how you would search or insert etc in such a a hash table everything depends on how long this list is. If you search for an element you may have to go through the entire list to decide ah darn it's not there. Then you can never never stop early. And um all the other operations are also upper bounded by that. That's what's listed here. If we denote by li I the length of this list the number of uh elements that is it's here simply the number of elements that hash to this position I for um uh a randomized analysis. Let's look at the expected value. What is the expected value for the length of this list? In other words, uh the expected length of the list where x i hashes two. Okay, that's what we'll look at. It turns out this is pleasingly easy to analyze.

15:18 If we define um one piece of notation, the notation is the these xig are indicator events that the keys x i and xj have collide in the same bucket. Okay, then you can rewrite the length of the bucket, the size of the bucket of some XI simply as the sum of those XI J events where you sum over all J and keep I fixed. The number of keys in my bucket is for every buck for every other element summed up. Do you collide with me? Yes or no? If yes, then I add a one and if zero um if if not a zero. That's what this indicator event of course denotes, right? This is um one if the condition is true and zero otherwise.

16:17 And then um writing a random variable as the sum of other random variables is useful because of linearity of expectation. Right? We want to compute the uh expected value for this. Uh first of all um the x i are always one because I am always colliding with myself and the uniform hashing assumption gives me for all the other ones that they occur with probability 1 / m. So I can now compute the expected size of the bucket that x i falls into is this expectation of the sum which is the sum of the expectations. The expectation of an indicator variable is the probability that it occurs and that is one over m as we know well one more step uh except for the x i which is deterministically one. So we pull that out and we essentially have this uh n minus one * this probability uh so in equal this is 1 n -1 / m alpha was n / m so as an upper bound you have 1 + alpha.

17:25 So in particular, if you keep your uh load factor a constant, say two at most twice as many keys as the table has uh slots or buckets, then you're going to have search cost three in expectation at most. That's rather good. Unfortunately, all of this was uh contingent on the uniform hashing assumption.

17:53 So, um assuming the world is nice, indeed the results are good. And fixing that, um we'll look at next week.