1 00:00:02,480 --> 00:00:06,017 Welcome back. Today we're going take a look at hashing, 2 00:00:06,017 --> 00:00:11,127 which is another approach to implementing symbol tables that can also be very 3 00:00:11,127 --> 00:00:16,564 effective in practical applications. Here's our summary where we left of with 4 00:00:16,564 --> 00:00:21,216 red black BSTs, where we can get guaranteed logarithmic performance for 5 00:00:21,412 --> 00:00:26,915 broad range of symbol table operations. And the question is, can we do better than 6 00:00:26,915 --> 00:00:30,256 that. Is logarithmic performance the best we can 7 00:00:30,256 --> 00:00:33,663 do. And the answer is that actually we can but 8 00:00:33,663 --> 00:00:36,480 it's a different way of accessing the data. 9 00:00:36,683 --> 00:00:39,873 And also doesn't support ordered operations. 10 00:00:39,873 --> 00:00:45,778 But there's plenty of applications where the extra speed for search and insert that 11 00:00:45,778 --> 00:00:52,774 we can get this way is worthwhile. The basic plan is to think of the symbol 12 00:00:52,774 --> 00:00:59,262 table, as really try to reduce the problem to being like an array. 13 00:00:59,548 --> 00:01:07,507 And what we do is use the function known as a hash function, that takes the key a 14 00:01:07,507 --> 00:01:14,319 symbol table key and reduces it to an integer and array index. 15 00:01:14,319 --> 00:01:22,010 Now we use that array index to store the key in the value in an array, 16 00:01:22,010 --> 00:01:27,355 Maybe the value in a parallel array. Now, there are a lot of issues in doing 17 00:01:27,355 --> 00:01:30,562 this. First thing is we need to be able to 18 00:01:30,562 --> 00:01:36,478 compute the hash function that is easy for some types of data, but it can get 19 00:01:36,692 --> 00:01:40,256 complicated for more complicated types of data. 20 00:01:40,470 --> 00:01:45,793 Then the other thing is that instead of doing comparatives we're going to be doing 21 00:01:45,793 --> 00:01:49,442 equality tests. So we have to be sure we've got the method 22 00:01:49,442 --> 00:01:52,613 that we want for checking whether two keys are equal. 23 00:01:52,792 --> 00:01:57,697 All we're going to do is look in to the table and try to see if the key that's 24 00:01:57,697 --> 00:02:00,330 there is equal to the key we're looking for. 25 00:02:00,548 --> 00:02:06,880 And then is the problem of collision resolution where it's, since there are so 26 00:02:06,880 --> 00:02:12,339 many possible values for typical data type, your going to get the situation 27 00:02:12,339 --> 00:02:15,687 where two values hash to the same array index. 28 00:02:15,687 --> 00:02:21,219 And we need a collision resolution strategy to try to figure out what to do 29 00:02:21,219 --> 00:02:25,222 in that case. And these things are not difficult, but 30 00:02:25,222 --> 00:02:30,827 they are all worth articulating as separate issues that we have to deal with 31 00:02:31,045 --> 00:02:35,360 in order to get an effective symbol table implementation. 32 00:02:35,360 --> 00:02:40,048 Hashing really at its core is a classic space time tradeoff. 33 00:02:40,048 --> 00:02:46,456 If we had no limitation on space at all, then we could have a very huge array with 34 00:02:46,456 --> 00:02:51,848 space for every possible key and just use the key itself as an index. 35 00:02:51,848 --> 00:02:59,349 If our keys are 32 bit integer keys and we've got a table of size two^32, then 36 00:02:59,349 --> 00:03:03,599 we're just fine. If there were no time limitation at all, 37 00:03:03,599 --> 00:03:09,142 Then I would just hash everything to the same place and then do sequential search. 38 00:03:09,337 --> 00:03:13,315 But sequential search can be slow if we have lots of keys. 39 00:03:13,315 --> 00:03:18,858 So what hashing is kind of in the real world where we're trying to trade off this 40 00:03:19,054 --> 00:03:24,140 idea that we don't have unlimited space and we also don't have unlimited time. 41 00:03:24,140 --> 00:03:27,140 So we are trying to find something in between. 42 00:03:27,860 --> 00:03:31,360 So we'll look at hash functions, separate chaining. 43 00:03:31,360 --> 00:03:36,711 And then two collision resolution methods, called separate chaining and linear 44 00:03:36,711 --> 00:03:42,762 probing. Now look at the implementation of hash 45 00:03:42,762 --> 00:03:46,670 functions. So idealistically what I'd like is to be 46 00:03:46,670 --> 00:03:52,342 able to take any key and uniformly scramble it to produce a table index. 47 00:03:52,342 --> 00:03:56,991 We have two requirements. Now one is that, we have to be able to 48 00:03:56,991 --> 00:04:01,797 compute the thing efficiently in a reasonable amount of time. 49 00:04:01,797 --> 00:04:07,942 And the other is that it should be the case that every table index is equally 50 00:04:07,942 --> 00:04:12,671 likely for each key. Now mathematicians and computer scientists 51 00:04:12,671 --> 00:04:18,407 have researched this problem in, a lot of detail and its quiet a bit known about it, 52 00:04:18,607 --> 00:04:24,477 but in practice, this is something that's still, we have to worry about, somewhat. 53 00:04:24,677 --> 00:04:28,680 So for example, lets suppose that our keys are phone numbers. 54 00:04:28,860 --> 00:04:33,914 Probably a bad idea if you use the first three digits of the phone number as a hash 55 00:04:33,914 --> 00:04:37,945 function because so many phone numbers'ill have the same area code. 56 00:04:37,945 --> 00:04:42,758 It's not equally likely that each phone number has the same, same first three 57 00:04:42,758 --> 00:04:45,585 digits. You have a better chance using the last 58 00:04:45,585 --> 00:04:48,894 three digits. But actually, in most cases, you want to 59 00:04:48,894 --> 00:04:53,186 find a way to use all the data. Another example, social security numbers. 60 00:04:53,186 --> 00:04:57,614 Again, it's not to good to use the first three digits because, their associated 61 00:04:57,796 --> 00:05:02,285 with some geographic region and it's better to try and use the last three 62 00:05:02,285 --> 00:05:05,385 digits. And the real practical challenge with 63 00:05:05,385 --> 00:05:10,737 hashing is that with developing hash function is,, that every type of key needs 64 00:05:10,737 --> 00:05:15,240 a hash function and you need a different approach for every key type. 65 00:05:15,240 --> 00:05:19,858 Now, for standard keys like integers, and strings, and, doubles, and so forth. 66 00:05:20,040 --> 00:05:24,415 The, we can count on the implement, designers and implementers of Java to 67 00:05:24,415 --> 00:05:28,487 implement good hash function. But, if we're going to be implementing 68 00:05:28,487 --> 00:05:33,044 symbol with our own types of data. We're going to have to worry about these 69 00:05:33,044 --> 00:05:37,480 things in order to get a hash function that's effective that leads to an 70 00:05:37,480 --> 00:05:43,925 effective symbol table implementation. So hashing is, widely used for, systems 71 00:05:43,925 --> 00:05:50,877 programming and applications, so, some conventions for hashing are built into 72 00:05:50,877 --> 00:05:55,188 Java. In particular, all Java classes inherit a 73 00:05:55,188 --> 00:06:00,732 method called hash code, which is, returns a 32 bit int value. 74 00:06:00,996 --> 00:06:08,300 And it's a requirement that if, x and t Y are equal, then their hash code should be 75 00:06:08,300 --> 00:06:09,356 equal. So, 76 00:06:09,620 --> 00:06:14,011 That's, Something that is a convention that's 77 00:06:14,011 --> 00:06:18,927 built into java and that enables the hash code to be used for hashing. 78 00:06:19,138 --> 00:06:24,967 Also, of course, if they're not equal then you'd like it, like it to be that their 79 00:06:24,967 --> 00:06:28,830 hash codes are not equal but you can't always get that. 80 00:06:29,144 --> 00:06:36,409 Now the default implementation for hashing is the, memory address, of the object. 81 00:06:36,409 --> 00:06:40,429 For hashing an object is the memory address of an object. 82 00:06:40,429 --> 00:06:44,871 So that, kind of, meets these two requirements for Java. 83 00:06:44,871 --> 00:06:50,513 The one that it doesn't, maybe, meet is the idea that every table position should 84 00:06:50,513 --> 00:06:55,096 be equally likely. So, so usually we'll do some more work, to 85 00:06:55,096 --> 00:07:00,456 try to, make that one happen. As far as the algorithms go, as far as the 86 00:07:00,456 --> 00:07:04,590 rules go, you could always return seventeen that's legal. 87 00:07:04,796 --> 00:07:08,837 It doesn't have this, highly desirable attribute. 88 00:07:09,043 --> 00:07:14,181 But everything would compile. So you have to be a little careful that 89 00:07:14,386 --> 00:07:20,210 somebody isn't in there doing that. And again for important. 90 00:07:20,210 --> 00:07:24,042 Key types that lots of people are going to use. 91 00:07:24,042 --> 00:07:29,750 Some care has gone into the design of hash functions and the built in 92 00:07:29,750 --> 00:07:34,560 implementations. So Java has customized implementations for 93 00:07:34,560 --> 00:07:40,105 the standard data types that people would use for simple table keys. 94 00:07:40,105 --> 00:07:46,628 And that's the sweet spot for hashing where some expert has done implementation 95 00:07:46,628 --> 00:07:51,276 of the hash-code. And also, your application does not need 96 00:07:51,276 --> 00:07:55,133 ordering. But for useful to find types, you're on 97 00:07:55,133 --> 00:07:58,811 your own. And we'll talk a little bit about how to 98 00:07:58,811 --> 00:08:02,420 implement hash codes. So here is the Java library 99 00:08:02,420 --> 00:08:08,702 implementations for a few standard types. And they are what they are, and what we'll 100 00:08:08,702 --> 00:08:14,693 do is, with knowledge that that's what the hash code is we'll do some extra work to 101 00:08:14,693 --> 00:08:20,684 try to get this extra property that every table position should seem to be equally 102 00:08:20,684 --> 00:08:23,788 likely. So if it's an integer, the hash code 103 00:08:23,788 --> 00:08:28,912 supposed to be 32 bits, the integer supposed to be 32 bits, so they just 104 00:08:28,912 --> 00:08:33,226 return the value. If it's a boolean, they pick out a couple 105 00:08:33,226 --> 00:08:39,202 of particular values that they return so hashing a boolean types, there's only two 106 00:08:39,202 --> 00:08:44,456 different values so well it's hard to think about what you really might want 107 00:08:44,456 --> 00:08:48,199 there. For double value this is the code they 108 00:08:48,396 --> 00:08:53,058 convert to 64 bit and x or the most significant 32 bits with the least 109 00:08:53,058 --> 00:08:57,261 significant 32 bits. This illustrates something that you want 110 00:08:57,261 --> 00:09:02,777 to do if you have a lot of bits, you want to try and involve all the bits somehow in 111 00:09:02,777 --> 00:09:08,780 the hash function. And for strings it kind of creates the 112 00:09:08,780 --> 00:09:19,170 string as a, a huge number and then really computes the value of that number a mod 32 113 00:09:19,492 --> 00:09:27,475 it uses an arithmatic a way of evaluating a polynomial or a number, a so called 114 00:09:27,475 --> 00:09:32,033 Horner's Method, where for each digit, you just multiply. 115 00:09:32,033 --> 00:09:38,235 So it treats it as a base 31 number and to get, to compute that whole number you 116 00:09:38,235 --> 00:09:42,794 multiply 31 times where you have so far and add the next digit. 117 00:09:42,794 --> 00:09:48,099 And that's called Horner's rule and if you're familiar with it, fine. 118 00:09:48,099 --> 00:09:53,928 If you're not you can look at this little example and decide what it is. 119 00:09:53,928 --> 00:09:59,502 And again it involves all the characters of the string, in completing the, hash 120 00:09:59,502 --> 00:10:04,330 function. So. 121 00:10:04,567 --> 00:10:11,069 And actually, since strings are immutable, what Java does is keep the hash value in 122 00:10:11,069 --> 00:10:15,113 an instance variable so it only gets computed once. 123 00:10:15,430 --> 00:10:21,377 And that is going to be very effective for performance in lots of applications. 124 00:10:21,377 --> 00:10:26,690 So once it computes the hashcode, it stores as an instance variable. 125 00:10:26,690 --> 00:10:33,191 And the next time you ask for the hascode for that string, it will just provide it. 126 00:10:33,191 --> 00:10:36,760 And that works because strings are immutable. 127 00:10:36,760 --> 00:10:42,169 So how about implementing a hash code for our own type of data. 128 00:10:42,169 --> 00:10:48,522 And so, we might have, our transaction type might have a couple of instance 129 00:10:48,522 --> 00:10:55,133 variables, a string, a date, and a double. And we need to compute a hash code, so 130 00:10:55,133 --> 00:11:00,456 return a 32 bit value. And again, we want to try to make use of 131 00:11:00,456 --> 00:11:07,068 all the pieces of data that we have. And we also want to make use of the hash 132 00:11:07,068 --> 00:11:12,165 code implementations for the types of data that we're using. 133 00:11:12,165 --> 00:11:19,607 So, one thing, to do is, start out with some, small prime number, and this kind of 134 00:11:19,607 --> 00:11:25,643 mimics, Horner's method, to, just add in more data as we get it. 135 00:11:25,643 --> 00:11:32,919 So we pick some other small prime number and for each field we multiply by 31 and 136 00:11:32,919 --> 00:11:37,660 then add the hash code for that field. So, 137 00:11:37,660 --> 00:11:42,530 If it's a reference type just use the hash code, so who was a string? 138 00:11:42,530 --> 00:11:47,949 So string has a hash code method, so we add that in and dates and when's a date, 139 00:11:47,949 --> 00:11:52,682 so we add that hash code, multiply it by 31 and add that hash code in. 140 00:11:52,682 --> 00:11:58,581 Trying to take all the bits and scramble all the bits and use'em and for primitive 141 00:11:58,581 --> 00:12:01,874 types, take the wrapper type and use the hash code. 142 00:12:02,080 --> 00:12:07,567 So that's a, a simple example of implementing a hash code for our own type 143 00:12:07,567 --> 00:12:13,420 of data that might include several different types of instants variables. 144 00:12:13,420 --> 00:12:19,377 So that's the standard recipe. Use the 31 x plus y rule to combine all 145 00:12:19,377 --> 00:12:23,865 the fields. If it's a primitive type, use the wrapper 146 00:12:23,865 --> 00:12:27,620 hash code. If the field is null, return zero. 147 00:12:27,893 --> 00:12:34,546 And if it's a reference type, use that hash code and apply it recursively. 148 00:12:34,546 --> 00:12:40,014 And if you have an array, you have to apply it to each entry. 149 00:12:40,014 --> 00:12:45,664 Or actually Java implements that in the array, in its arrays library. 150 00:12:45,664 --> 00:12:52,316 So this recipe works pretty well in practice and it's used in several, in 151 00:12:52,316 --> 00:12:56,964 Java's libraries. Now in theory it's possible to do 152 00:12:56,964 --> 00:13:04,296 something that has the property that, that all positions are equally likely. 153 00:13:04,296 --> 00:13:10,306 It's called Universal Hash Functions. These things exist, but they're not so 154 00:13:10,306 --> 00:13:15,756 widely applied in practice. So the basic rule is if you're computing 155 00:13:15,756 --> 00:13:22,007 your own, try to use the whole key, but consult an expert if you're seeing some 156 00:13:22,007 --> 00:13:28,658 performance problems or you really want to be certain in some performance critical 157 00:13:28,658 --> 00:13:35,146 situation. Now what we get back from the hash code is 158 00:13:35,365 --> 00:13:42,331 a INT value that's between -two^31 and two^31 - one. 159 00:13:42,339 --> 00:13:49,430 Now, what we need is, if we have a table of size m, an array of size m that we're 160 00:13:49,430 --> 00:13:56,692 going to use to store the keys, we need an int value between zero and m - one. 161 00:13:56,693 --> 00:14:05,340 And the value of m is maybe a power of two or sometimes we pick, pick a prime because 162 00:14:05,340 --> 00:14:12,527 of the way that we normally would get the big hash code value down to be a number 163 00:14:12,527 --> 00:14:16,358 between zero and m - one is just to do Mod m. 164 00:14:16,358 --> 00:14:22,379 And if Mod, if m is a prime then, then from math, Modular arithmetic, we know 165 00:14:22,379 --> 00:14:27,540 that we are using all the bits in the number in that point too. 166 00:14:27,808 --> 00:14:34,699 Now, since the hash code can be negative this doesn't quite work the way this 167 00:14:34,699 --> 00:14:40,963 arithmetic is implemented in Java cuz it's one in a billion times. 168 00:14:40,963 --> 00:14:47,991 You really have to take the absolute value well sorry you have to take the absolute 169 00:14:47,991 --> 00:14:53,550 value I would because other wise it'd be negative and you cannot have a negative, 170 00:14:53,550 --> 00:14:58,977 you want it to be between zero and -one. But even if you take the absolute value 171 00:14:59,175 --> 00:15:06,058 there's going to have -two^31 is possible. so you have to just take the 31 bits. 172 00:15:06,256 --> 00:15:11,220 You get the hash code out make it positive and then mod M as the way to go. 173 00:15:12,312 --> 00:15:18,792 The math doesn't quite work out right so anyway, that code down at the bottom is 174 00:15:19,010 --> 00:15:23,743 You can use that as a template for what you might want to do. 175 00:15:23,961 --> 00:15:30,514 And that's what we do in order to get the hash code to be a number between zero and 176 00:15:30,514 --> 00:15:34,155 M minus one. And if M is prime, it gives us some 177 00:15:34,155 --> 00:15:40,999 comfort that we have some possibility of each table position appearing with equal 178 00:15:40,999 --> 00:15:43,771 likelihood. So that's our assumption. 179 00:15:43,771 --> 00:15:49,685 That each key is equally likely to hash to an integer between zero and m-1. 180 00:15:49,685 --> 00:15:55,993 And this assumption again, it's, with work it's possible to come close to this. 181 00:15:55,993 --> 00:16:00,093 Lots of researches have done good work to show this. 182 00:16:00,093 --> 00:16:06,677 We'll assume that as a starting point. And that allows us to model the situation 183 00:16:06,677 --> 00:16:13,512 with the so-called bins and balls model that directly relates the study of hash 184 00:16:13,512 --> 00:16:21,328 functions to classical probability theory. So we've got the n bins, that's our That's 185 00:16:21,328 --> 00:16:27,659 our corresponds to our hash table and we get M balls and with some number of balls, 186 00:16:27,659 --> 00:16:32,958 however many keys we have and we throw'em uniformly, at random, into M bins. 187 00:16:32,958 --> 00:16:36,605 And, with. These things are studied in classical 188 00:16:36,605 --> 00:16:40,940 combinatoric analysis. For example, there's the birthday problem. 189 00:16:41,147 --> 00:16:46,514 Which, how many balls do you throw before you find two hitting the same bin? 190 00:16:46,514 --> 00:16:51,744 When do you get the first collision? And the answer to that is, it's about 191 00:16:51,744 --> 00:16:56,168 square root of pi M over two. When does all the bins fill up? 192 00:16:56,382 --> 00:16:59,454 That's called the coupon collector problem. 193 00:16:59,454 --> 00:17:04,240 After about m, natural log m tosses, every bin has at least one ball. 194 00:17:04,454 --> 00:17:09,740 Those are just examples of classic results from commonatorial analysis. 195 00:17:09,954 --> 00:17:16,240 It help us understand what happens when we do this, which is what we're doing with 196 00:17:16,240 --> 00:17:20,954 hashing. And we'll look at more advanced versions 197 00:17:20,954 --> 00:17:24,240 of these problems when we wanna study hashing. 198 00:17:24,454 --> 00:17:31,148 And in particular it's known that after you've thrown n balls into the n bins, 199 00:17:31,148 --> 00:17:36,302 then the most loaded bin has about log m over log, log n balls. 200 00:17:36,551 --> 00:17:44,947 So that's going to help us get a handle on the performance of hashing algorithms when 201 00:17:44,947 --> 00:17:52,013 we get to the implementations. So this is just an example showing all the 202 00:17:52,013 --> 00:17:59,828 words in a tale of two cities using the modular hashing function for strings like 203 00:17:59,828 --> 00:18:05,100 the one that Java uses. And their pretty uniformly distributed. 204 00:18:05,100 --> 00:18:08,700 And that's the summary for hash functions.