Hi. In this video we will talk about direct addressing, which is the first step on the way to hashing. Remember this computer code from the last video. We implemented procedure UpdateAccessList using a data structure C, which stores a counter for any IP address. Now the question is, how to implement the data structure C itself. The idea here, is that there are 2 to the power of 32 different IP addresses. According to IP(v4) format. And we can actually convert each IP to a 32-bit integer. And it will be a one to one correspondence between old possible IPs. And all numbers between zero and two to the power 32 minus one. Thus, we can create an array A, of size exactly two to the power of 32, with indexes zero to two to the power of 32 minus one. And then for each IP, there will be exactly one position in this array, correspondent to this IP. And then, we will be able to use the corresponding answer in array A. Instead of the counter for this IP. Now, how do we actually convert IP addresses to integers? If you look at this picture, you will see that any IP address actually consists of 4 integer numbers. Which are all, at most, 255. And each of them corresponds to 8 bits, or 1 byte in the total 4-byte or 32-bit integer number. Basically, if you just coordinate all the 8 bytes corresponding to first number with 8 bytes. Corresponding to the second number and to the third number and to the fourth number. You will get 32 bytes. And if you then convert this string of 32 bytes into the decimal form. You will get an integer number in the form which we are used to. For example, if you take a very simple IP address, 0.0.0.1. It will convert to integer 1, because all the higher bits are zeroes and in the lowest byte. The only bit set is the lowest bit and that corresponds to number 1. If we convert the number in the picture, to the decimal form, we will get 2886794753. Now, what do you think will be the integer number corresponding to this IP? And the correct answer is 1168893508. Now, here is the formula and the code to convert an IP address to an integer number. Why is that? Well, the lowest eight bits are in the fourth number of the IP address. So we use them without changing. The next Eight bits, are in the third number of IP. But to use them, we need to move them to the left by eight positions in the binary form. And to do that, we need to multiply the corresponding integer number by two to the power of eight. The next eight bits are in the second number of the IP. And to use them we need to move them to the left by 16 positions in the binary form. To do that, we multiply the corresponding integer number by two to the power of 16, and so on. This gives us a one to one correspondence between IP address and integer number. Now, we can rewrite the code for UpdateAccessList using array A, instead of mysterious data structure C. And the only thing that changes is the incrementing and decrementing the counters. So when we need to increment a counter corresponding to the IP in the ith line. We first convert this IP to integer number from 0 to 2 to the power of 32 minus 1. And then we increase the entry of the integer RA A, add this index. Note, that each IP is converted to its own integer number. So, there will be no collisions between different IP numbers. When we try to increment a counter for one IP number and by chance increment the current correspondent to another IP address. All IP addresses are uniquely mapped into integers from zero to two to the power of 32 minus one. We do the same thing when we need to decrement the counter. So basically, in the position in array A corresponding to any IP address, we will store the counter. Which measures how many times this particular IP was accessed during the last hour. Now, how to answer the question, whether this IP was or was not used during the last hour, to access your services. This is very easy. We first convert the IP to the corresponding position in the area A, and then we look at the counter this position. If the IP was used, then the counter will be more than zero. Otherwise it will be exactly zero. So, now lets look at the asyptotics of this implementation. UpdateAccessList is as fast as we can do. It is constant time per log line. Because for each log line, we only look at some position in the array and increment it. And also increment some counter, or decrement some counter. AccessedLastHour is also constant time. Because the only thing we do is, we look at some position in their rate. Which is a constant time impression and compare it with a zero, but there is a drawback. Even if during the last hour, for example, in the night, there are only five, or 10, or 100 IPs. From which your clients use the service. You will still need 2 to the power of 32 memory cells, to store that information. And in general, if you have for example, new IP protocol. IPv6, it already contains 2 to the power of 128 different IP addresses. And if you create an array of that size, it won't fit in memory in your computer. In the general case, we need O(N) memory, where N is the size of our universe. Universe is the set of all objects, that we might possibly want to store in our data structure. It doesn't mean that every one of them will be stored in our data structure. But if we at least at some point might want to store it, we have to count it. So for example, if some of the IP addresses never access your service. You will still have to have a cell in your array for this particular IP, in the direct addressing method. So, this method only works when the universe is somewhat small. And we need to invent something else to work with the universes which are bigger than that or even infinite. Such as, for example, the universe of all possible words, all possible strings, or all possible files on your computer. And we will talk in the next videos about that.
