So, as we talk about building hash functions, it may seem initially to be very easy to build the hash function. We can think about all of the data that we might consider as part of our hash function, we can think of a pretty easy mapping to it. In fact for small values of input, this is going to be extremely easy. I can think about what my data is, I can think about what I expect my user to input, and I can map it in a relatively uniform way, and it's not going to be hard. But what often happens is when you actually see a code move into production and not simply be something you're thinking about in your office; you're going find that the actual amount of key space is going to be much larger than you imagined, and we need to have a hash function that considers all of this key space, and not just what the user expects. So, here instead of just mapping to a small key space, we have to consider the fact that our circle maybe here or maybe way out here. In doing so, we have different parts of that key space when you consider all of these subspaces of the key space needs to be uniform. This incredibly difficult to do. So, one of my examples that I ran into, when I personally tried to create a new hash function was that I wanted to map strings that were of some arbitrary length, and I went ahead and I created a hash function, that map a string of arbitrary length by mapping a string of only eight characters. I figured you know what a string of many characters is really easy to create a hash function around, I'll sum of their values, do some mode and some multiplication on them, and I will have a really great system to make sure that every string is uniformly different. So, here I have the text of Alice Wonderland. This text has a lot of different sentences and I if I look at the first eight characters of every single line, I can see the first eight characters of every single line is quite different. There is no two lines that are the same, and if I look at the first eight characters and do some clever math on them, I can come with numbers that are going to be different at every single point of time. I think I am really confident in my ability to actually create a hash function that's going to map each line of Alice Wonderland to a particularly unique value or at least in a uniform way. Awesome. So, creating this hash-function did a great job, it worked great on some texts corpuses, but then as soon as I went and plug this into a different application as building, some weird things happened. The next thing I built was a web scraper and I was scraping Wikipedia articles to do some research on the texts and the Wikipedia articles. In doing that, the keys to my hash table, the data point that describes what data I have, the key value was a URL. So, using the exact same hash function, I looked at every single URL and let's look at the first eight characters of those URLs. In Wikipedia, the first eight characters of all the URLs are exactly the same value. So, here every single point in this dataset has a number of values that are mapping to the exact same point. What that means is every single point I have a collision, and I have a number of different collisions happening, and I have to resolve all of these collisions, and I absolutely do not have a uniform set of functions. Because of this, I actually developed a hash function that worked really well in one piece of data and as soon as they use another application, I found this hash function fell apart. So, these are some of the problems that we're going to deal with, when we deal with hash functions. It's incredibly hard to think of all the UC user's going to use. So, whenever we think about a hash function, we want to be very careful. If at all possible, we're going to use some of the established hash functions that have already existed for many years, because the best way to test whether or not a hash function is good is to use it for a really long time. So, we've talked a lot about the hash function, and now we're going to talk more about diving into the next aspect of this, about the array and how we deal with collisions. So, I'll see you then.
