Video 9-1: Random trick in Hashing

0:04 In this next unit, we'll look at some standard tricks or algorithmic design techniques if you want that come from randomization and allow you to do uh things in a in a certain way better than without randomization. I'll I'll come back to that in a second. Uh I had to pick um only some isolated examples. There's there's many more and uh many places have a a dedicated lecture just on randomization. uh for a full term. Uh so it'll be a a small sample of what you can do with randomness which kind of fits the topic but it's not completely random. I gave it some thought. Anyways uh so we've seen probably a complexity theoretic not too much to win but we can still get algorithms that are simpler even if they don't achieve better performance. Or we could achieve algorithms that improve performance. We've seen very far back the example of median selection, right? So it can be provably more efficient to use randomization even if it doesn't get you from exponential to polomial and it can also improve robustness which in practical terms is often a very effective way to use randomization and quicksort with random pivots would be the uh the basic example of that but there's many more. So here uh as I said just a collection of some uh some things some examples that illustrate techniques and specifically I want to show how how fingerprinting and hashing is used and that's where bloom filters fit very well. Um another thing is uh whenever you have a problem where you're trying to show some property and there's an abundance of witnesses you may be able to just guess a random thing and try to show that it is a witness. witness in the sense of a certificate for for proving some property um is a bit yeah we we'll come back to that and and random sampling generally means um to pick pick an object at random uh if you have a good chance that that object is what you want then that's an effective strategy I guess these will make more sense on the concrete examples the first thing I want to briefly look at is hashing I didn't dare to ask who knows hashts but this is a very standard undergraduate algorithms topic so I will uh only briefly recap some of those bits and rather show a few cases where where really uh the randomized angle comes through and maybe some analyses there uh we may may just have time for that today uh what's what's the uh overall setup um in abstract terms often think of think of building a diction ary what you could solve with a binary search tree. Um you have objects that come from some large universe of possible values say all strings or something of that sort. Uh a huge huge uh possible uh universe.

3:08 Um here we'll we'll already assume that this is somehow mapped to integers but it could be um a very generous mapping that just translate things into binary strings and then binary strings can be interpreted as integers. Uh so u is the size of this universe but we're expecting to only deal with a very small subset of this at any point in time. the actual input size is n and these uh I guess these items come from u would have been useful to add but uh we think of the the number of items that we have to be much smaller than the size of the possible values that we could have and that's the case where fingerprinting can help in various various ways. Um we pick fingerprints from yet another parameter here. So u the size of the universe, n much smaller than u the number of things we actually have and independent of n we could pick uh m for the size of the possible fingerprints that we allow and then uh conventionally called a hash function is some mapping from the universe to fingerprints.

4:19 Now clearly because we also think of M to be much smaller, H will have collisions, meaning there are X and Y in the universe so that they have the same hash value. That's inevitable if we reduce the uh the large universe to a much smaller range. And uh in I mean in general we will have some collisions yes but we'll actually have many collisions. The point is that we hope to have few on the actual data items that we deal with. All right. Um classic examples of using hash functions for various problems are hashts and bloom filters. So a hash table um for let's let's maybe uh draw this briefly. um also do the analysis next time. So for this course, the hashts I'm thinking of are very simple um indirect chaining hashts.

5:40 What I mean by that is that the hash table itself is just a a collection of of buckets. So these are slots that are named by the possible fingerprints up to um m minus one. uh the elements from our universe this much bigger universe u right they are mapped by h to some of these slots here's our x is mapped to h of x and then here we just store a a linked list of elements that hashed to this slot and that we store and maybe then there's a a null pointer. That's what I mean by an indirect chaining hash table. I don't care too much how you exactly store this uh all the elements that hash to the same bucket. Uh for now, let's suppose it's just a link list. It's good enough for what we what we need.

6:52 Um so the the key property there is that well performance of such a hash table. The key interesting question is how big are the buckets or more formally um I think we'll always denote this by capital X or a fingerprint Okay.

7:41 well I don't I don't think it's a set. It's a number. So the number of keys with hash value J in our hash table. So of course over the entire universe there's many more but we care about the elements that we want to store. Okay.

8:14 Uh second big application of this fingerprinting is bloom filters. The picture looks almost the same but it's it's used for something different and so also restores things differently. We still have these these rows or slots 01 up to m n m minus one. We also have our big universe mapped via H to some slot.

8:50 But now here this is a binary vector. We only store zeros and ones. And uh the way a bloom filter works is it's a it's a fussy set um or an approximate membership data structure. it can tell us uh whether it's potentially true that some element is there and it's easier to work out uh if you insert an element x then if this is our hash table insert just sets the appropriate position so you hash x and it sets that to one no matter what it was before and that's pretty much All it can do we can we can then do query and that just returns the value there and that's what the uh the basic bloom filter does which means if I ask a bloom filter has someone inserted this value x it might tell me yes even if actually it never was inserted just something else that hashed to the same value. So an output one can be wrong can be a false positive.

10:23 So you might wonder when would you ever want to use such a thing? But I'll tell you in a second. Uh the nice thing is if it says zero you're sure this is always correct because if no if nobody hashed to that place then certainly the thing that you're currently checking also wasn't inserted otherwise it would be would be a one now you can um there's many ways so the basic version that I'm I'm explaining here is is not working well because uh it's most it's it's too probable that something hash to the same value. It has a lot a high false positive rate. Um you would want to include several independent hash functions and several bits and then check all of them and only if all of the hash tables are one you would say this element is present. So you uh can boost the false you can reduce the false positive rate by using several bloom filters in parallel if you want.

11:51 uh you can even use uh several hash functions but one big table age. And so you you could have collisions between the same values with a different values with the same hash value with the same hash uh address or different positions with different hash functions hashing to the same value. Uh you can still deal with that. And there's also ways to somehow make deletions work in the pure form. You cannot delete something once it's been inserted. We cannot remove it again. And the reason is clear. If you wanted to remove something, if you don't know for sure whether it was there before, you don't know whether taking it away, putting it to zero would delete effectively many other things as well. Right? So, uh, bloom filters are like this. They are fuzzy. They can be wrong. In this case, they can only have false positives. So the a standard application for this would be uh some kind of um uh a segmented data structure or database where you have uh your your data is too big to be stored in one place. So you split it up in in different parts. Now you could ask the big database is this element in your portion of the data and it will tell you but it's it's an expensive operation. So instead you can have a bloom filter over all the data that's stored and ask the bloom filter first. And if the bloom filter says no then you don't even have to check the database. But if the bloom filter says one, you still don't know. You still have to check. But at least then there's a good chance it's a it's a true positive and the effort was worth it.

13:40 So it's kind of a a cheap a cheap first check whether it's uh promising to look uh do the expensive true query that's bloom filters.

14:05 Uh so I'm I'm only thinking of a query. I would um so you have some some database split up according some rule but you don't know where elements are. Now you're trying to find you're trying to do a lookup. Find me the uh value stored for a key. Then you can ask the bloom filter of each of the segments is that key stored in your portion of the data. And if it says no you don't have to check. If you insert then you would uh you would pick one of the portions and in the bloom filter of that portion inserted. Is that what you meant?

14:42 There's many more um sophisticated versions of this. So in practice maybe uh the standard bloom filters wouldn't be the choice. Um but that's that's the prototypical application of hashing there. Uh okay.

14:56 Um let me just give you a bit of the uh the plan for what we're going to do on hashing and then uh we might have to stop. Uh there's um there's essentially three ways in which uh randomization helps hashing. Um one way is uh hashing always has a terrible worst case. If you look at either the bloom filter or the hash tables, if uh the universe conspires against you, the everything will map to the same spot and you'll get the worst case will always be everything maps to the same bucket. So ax one is n and all the others are zero and then the whole thing doesn't work at all. And similarly in the bloom filter, you could have everything mapped to the same thing. You don't get any information. But that's astronomically unlikely to happen in most cases. And in particular, if you uh if you just test uh practical data with some halfway reasonable function, even if you're not super clever, it often works out fine.

16:04 So one way how uh randomization helps there is uh to formalize an assumption about the the uh data and then analyze probabilistically what the guarantees for the data structures are. Now undergrad you would do expected values only. Um we can also do with high probability in many cases you get um more reliable guarantees there. That's one way in the analysis you can use it and that's uh uniform hashing is this assumption that all hash sequences that you get are equally likely.

16:50 Um, and here it's really the hash function or a specific hash function that you pick. You get a a collection of elements from the universe, say n of those.

17:21 And how many are there? If you have m different choices of uh values and you pick n elements sequences are equally likely. This is an extremely strong assumption um because it it doesn't just say something about the input but it's the combination of hash function and input. Uh then the other um the other two uses are using randomization explicitly to pick a random hash function so that you're uh you can expect good performance even if the input is adversarial. Uh and lastly um we'll see some example of uh probabilistic method turned into an algorithm for for perfect hashing.