COMP2521 26T2 Week 8 Lecture 1

[00:00:46]Okay, let me check this.

[00:00:51]I think this one not working. So, we will have just one screen today.

[00:01:42]Okay everyone hello any question from last week because this week the topic is completely different and we'll start new ADT and new data structure today.

[00:02:01]Last week was about directed graph minimum spanning tree and dystra.

[00:02:11]No question.

[00:02:14]So this week we will discuss a completely new topic.

[00:02:23]Map ad a new abstract data type and hash table as a new data structure uh that we can use to implement maps and also some other entity that we will discuss on Thursday.

[00:02:41]So the main topic actually is hash table hashing and resolution.

[00:02:50]But let's start with maps. What is maps and what kind of edit it is and what is it uh actually main feature and behavior.

[00:03:03]So far we discussed different type of entities. If you remember we discussed a lot of sex cubes sets uh we will discuss few more on Thursday and also like graph also another entity that we will disc that we discussed already but let's see what is maps one of the actually type of abstraction that you would like to do in computer science is mapping a kind of data to another type of data. So for example, you want to map keys to values like word to definition or um a student Z ID to their name. So for having this kind of uh mapping ability actually we use maps data type which can map actually a key to a value.

[00:04:14]So and it has several application based on the list you can see that we can map some keys to some values.

[00:04:24][snorts] uh two important feature of maps. First it's constructed of pairs of key and value and the second important feature is keys are unique. So you cannot have a maps with two similar keys. Values can be similar but keys are unique.

[00:04:49]Here you can see some example. For example, this is the pair of keym values. The key here is for example a name and value is a favorite color. So as you can see uh the color can be similar like we have two red but the key must be unique. For example you we cannot have two student with the same Z ID but we can have lots of student with the same name. That's not the issue.

[00:05:19]And one more thing is uh map can be called dictionaries also. So dictionary and map in general are same thing same add and also there are some other names that sometimes maybe you see in some resources like associative arrays or symbol tables they are all same thing but generally the name is math and the reason we shouldn't have two similarities is when we actually ask and want to retry the information. If we have a similar key that it will make confusion for our model because in this case if you want to get the color associated to Sasha then the model will be confused that the color is purple or red because we have two similar keys which is young uh wrong.

[00:06:15]So map add a also has some operations like before.

[00:06:22]Three main operations on map is insert inserting a pair of key and values.

[00:06:32]Look up or search. If you are looking for a particular key to return the value associated to that key and also delete.

[00:06:42]For delete also we have to find a particular key and then if it exists we remove the pair of key and value from the map.

[00:06:59]So any question?

[00:07:06]Now we want to implement this ADT.

[00:07:12]Uh to implement ADT and store this information in the memory. We can use different data structures. We already knows about unordered array, ordered array and BST.

[00:07:27]So first see uh how is the complexity if we use this tree and then we will see that we can use hash table for this purpose also that will be a new data structure that we will introduce today.

[00:07:46]Uh you already know about unordered array as we can see from the name there is no order. So we can easily just insert all pairs of key and values in the unordered array. But we want to see what is the performance of insert lookup or search and delete if you unordered array.

[00:08:21]So the insert complexity is O N.

[00:08:26]Can anyone explain why it is O? If you want to insert key and value in unordered array because in unordered array we can easily insert at the end of the array because there is no order. So it should be O1.

[00:08:51]So why is O N?

[00:09:00]Is it because we have to first?

[00:09:06]>> Sorry.

[00:09:08]>> Is it because we have to first?

[00:09:13]>> No, because we can have this. you have the size of the array. You already know how many items exist. You can directly uh that index or do the reason in map we cannot have duplicates. So we need to have unique keys before inserting we have to check if the keys already exist or not. So we need to have a search and because it's unordered that search is linear search we have to check each and every case if is not exist we will insert this new pair at the end of the array if it exists we just change the value so because of that insertion complexity is all n because it has a search not because of insertion itself insertion is 01 but overall it will be O N because of search uh look up O N because we know it's unordered array and we have to do linear search to see if this key exists and then if it exists we can return the value or show up for something that is found and the next is delete for delete also we have to search and see if that key exists. If it exists then we remove the pair of key and value. Again it needs search that is a a linear search again any question here. So the main thing is about insertion that you have to consider that search in it and the complexity is O N and next is ordered array. So we have to insert all pairs of key and values uh in order based on keys order. So what is the performance here for insertion again is O N.

[00:11:31]Why? Because if it's about to search to see if this field already exists or not because it's order we can do binary search and is log na Suppose we did binary search and we found that this new pair need to be insert in the first slot because we have to keep it in order. What we should do?

[00:12:20]They have to shift our make a space and then do. So this shifting poss so here the O is not because of search because search is log N here but then we have to do shifting in worst case it can be O N so the dominant part is O N so we don't mention log N here because it's log N plus n we just kept n so that is because of shifting look up or search lock n because it's uh order and you just need to do binary search to find the key for delete is again o n why for delete you need to first find the key if it exists you delete Because after you find the key with the block end and remove it then you need to do shifting again all the items to the left to keep all the empty slots at the end. So again because of shifting delete also m any question.

[00:13:55]So here we can see that uh lookup is log n but for insert and delete because we have shifting the cost is O N.

[00:14:09]And third data structure that we can use to implement math is using balance while in search.

[00:14:23]What is the performance here?

[00:14:27]BST. Balanced BST.

[00:14:31]For balance BC, we know that the insert, look up and delete is log N.

[00:14:38]Why is not O N? Because the name of that word of balance. So this PSC cannot be school three because it is balanced and in balance tree always cost of insertion look up and relies. This is all we discussed before. Any question here?

[00:15:02]Okay. Next.

[00:15:07]Next is hash table which is new. We want to see what is hasht data structure and how we can use hash table to uh actually store map and Thursday we will see more example of a can be saved and store hash table. So first let's see what is hash table and how we can use it to uh save map.

[00:15:46]uh hash table as I mentioned is a data structure can be used to store key value pairs but as you can see there it can be used for this purpose but not necessarily for saving pairs of key and value hash table can be used for different purposes. One of them is saving uh key value pairs like a map. So it can be used for different purpose.

[00:16:19]What has actually hash table? Hash table constructed from two main things. One is a array that can store these values and the another important uh thing is hash function. The hash function actually convert key to a index which shows the location of the item that can be saved in the array. In all the data structure that I already mentioned we have to find the location and then do the insertion.

[00:16:52]for example for insert but if we use hash table we can directly find where I should insert this pair of key and value because we will have a particular index for it. So in this case it directly put this icon in this particular location and then always we can use this hash function later also to always find this location to retrive it to delete it or whatever because of that is very important for indexing and saving data. So we will see that how this hash function work is very important. So you can easily convert a key to a index in array.

[00:17:38]Um sometimes the index might change but we will see uh even it change you can find it in a mostly in a limited search but we will see how it work. So uh how it works we give a key key can be everything can be a name can be a integer whatever doesn't matter can be a file can be a text and then hash function compute an index for it for example seven and then we'll store or retrive the value in this particular index. So we will have a direct access instead of scanning and searching find the location of the pairs of key and value.

[00:18:31]So overall uh we have a input key then we have a hash function and the output of hash function is a number but we have to make sure that this number is in the range of length of array because normally your array has a limited length. It can be for example the length of array can be 10 20 100 but we have to make sure that value is in the range. To do that we calculate calculate the mode uh of the number on the length of array.

[00:19:08]to make the index within uh the range of array lengths and then we can store or retrive the pairs of key and value in that particular slot in the array. This is the example. For example, the key is Sasha or whatever.

[00:19:28]And then we have a hash function. The Sasha will be inputed this hash function. And then the output can be a number like this. And then if the length of the array is 10, we calculate the mode of this number on 10. then it will bring uh give us a index in range of 0 to 9 and then we can directly put Sasha in the index one.

[00:19:58]For example, here like we could uh for example this is if this is a hash function and this is the input and suppose the output become four and we directly insert this pair of key and value in the index four.

[00:20:20]We we will see more detail about that.

[00:20:23]So the interface of hash fun hasht you could do different operation on hash table. For example, you can create a new hash table. You can free the memory.

[00:20:36]You can insert a value pairs of keym value in the hash table. You can check if there is a particular key value exists in this hash table. You can return the value if the key exist. You can find the element and delete it or you can find the size of the hash table.

[00:20:57]So the variety of things based on what is the problem and why why you are using hash table you can define different operations or function here for example this code is I think yeah it's provided yeah it is in the material here okay uh for example if this is a if you create a new table then you can in call the insert function and then send the key and the value and if you call the get and give the key it will return the value associated to jazz and if you insert uh another pair of key and value and if keys exist which is exist here it will just change the color so green will be converted to orange and then next time if you want to call it it will give you orange instead of green and also you can delete the whole table.

[00:22:09]Okay. Um I already explained about this hashing application. Hashing is very important.

[00:22:19]It can be used for different purpose.

[00:22:21]One of them is indexing that we will discuss in detail today. But it can be used for different purposes. For example, for password storage. For example, to increase the security of saving password in our system. Normally uh actually the password itself will not be saved. U always will be converted to a hash value using the hash function and then that value will be saved. So in this case if someone access to your computer or the memory or whatever even they retrive the password it will not be the real password it will be the hash value associated to your password.

[00:23:04]So it will increase the uh security or for lookup in a database. Uh for example for as we saw we can associate um index to a value in database then quickly we can access that part or file integrity. We can even have some hash function that the input can be the whole file and do calculation on the file and give you a value and next time if you want to say this file already been changed or edited now or not you don't need to check you just need to recalculate the hash value again. If it change it means the file itself is changed and the hash function can be very complicated and can be used for different purposes.

[00:23:54]or this one hasht which is we are discussing today. So this is a very very small and easy application of hash tables and hashing. It can be very uh more complex and can be used for different purposes but here we are just using it for indexing and finding a location of item and then save it in the array.

[00:24:20]So we will see different type of hash function but they are all actually very easy one. So overall whatever is the hash function it always maps a key to a index in the range of 0 to n minus one.

[00:24:39]uh n is length of array and normally we use a cheap and easy function because uh if it is too complicated and then because we for each item we have to calculate the hash value it will take so much time. So it should be reasonable shouldn't be too much complex or too difficult. Uh because our file can be very big and then if you want to calculate for each and every item it can be very time consuming and also deterministic. It means your function should always give you the same value for the same input.

[00:25:20]You shouldn't have any random part in it because uh for that key always should give you the same value or same index here. Simple example.

[00:25:39]For example, this is a hash function.

[00:25:43]And this function is just calculate.

[00:25:46]Whatever key you give, it will just calculate the convert a key to 32 byt integer and then calculate the mode of that number on sides of the array and give you one index.

[00:26:04]or this one for a string. If the input key is a string, for example, we can use this hash function. Can you tell me what is doing this one on the string?

[00:26:19]How it convert a string to a index?

[00:26:31]This one. Any idea?

[00:26:36]Sorry.

[00:26:48]>> Yes, actually we convert the string to a number. The number is for each character we find the value and sum all those numbers to get the final number which is sum and then we calculate the model of sum length of the array. So index to save the string.

[00:27:14]So whatever is the input you can design a hash function for it but you have to make sure that the output is in the range of length of array. And another thing is we or function should actually distribute items all throughout the array.

[00:27:35]But we do have a collision collision also. We will see but we will see what is the issue with this.

[00:27:43]And this is another one more robust. It will add some extra value also. And in this one uh again it using the asky value of each character but the length of the string and also the sequence how the character appeared in the string can affect on the final indexing. So it is a little bit more complex compared to previous one. You don't need to learn just just there are there are example of different type of hashing that uh we can design different type of function that convert uh key to uh index and this is even more complex.

[00:28:27]This one applying lots of mixing shifting and then at the end will have a one value and then again apply mode to get the final index. So the hash function can be very complicated. Again you don't need to memorize it. Now let's see example. The hash function is quite easy here. Whatever is the key we divide it by 11 and then get the mode and use it that as a index. Why is 11? Because the length of the array is 11. So for four we calculate four mode 11 which will be four. So four will go in the index four.

[00:29:17]For simplicity, we just see the keys.

[00:29:21]But for example, is actually a pair of keys and value. For example, four is a key and value can be a name of the person or whatever. But for simplicity, we just seeing the keys here because all the calculation in hashing actually apply on the keys not on the value.

[00:29:39]But it can be a pair of u key and value.

[00:29:43]Next is eight. Again 8 / by 11 the remaining will be eight. We put eight in the index 8. Then 15 will be four. This is the collision. So we found two different keys but the hash function giving us the same index or same location to save them. So we have to find a way how to manage this kind of situation.

[00:30:13]So if we have the same index for different keys we will say that collision happened. Now we will see how we can solve this problem. This is the important thing. Any question here?

[00:30:28]Okay. Now um this is a definition of it. So always the array that we are using for saving our data has a limited length like 0 to n minus one and it happen that sometimes our hash function put different keys in the same place we call it collision and then we have to find a method to resolve this problem.

[00:30:56]We have three main uh main way of uh address this issue. Today we will discuss all three of them. First is separate chaining. In separate chaining actually instead of say that each slot of the array can keep one key or value each slot can be a list of uh notes. So in this case if we have two keys that will go to the same slot we will put it in the one of the we add one notes there and then add that number there. So say for example then I will back to this for example here instead of using each slot for saving one value actually each slot is a pointer to a list. So if after calculating the hash function we found the same index for different keys we just add those keys or keys and value in this list. So in this case we will not have collision.

[00:32:06]So we will see the example but before to go further on that and see the example one of the things that show that uh the percentage or possibility of happening collision is load factor. Load factor actually shows that how uh how percentage of or array is already full or how much spot is remaining.

[00:32:37]How full is the hash table. So and it's mide by n. m is number of items and n is the number of slots. If the load factor is 0.5, it means the half of the hash table is already full. If it is one, it means the whole table is full. And if it is more than one, it means the we have some chaining for example in the model that I said because all the uh slots are full. So we have to go for chaining. Uh and another things you as a person who design your model, you have to make a decision that when you prefer to resize your array because if you keep getting data and you want to insert in your hash table, you need to make a decision in when you want to uh maybe double the size of your array.

[00:33:42]Otherwise it will be very difficult to manage all these chains. That is a design decision.

[00:33:50]So as I said this is the first method to address collision which is separate chaining.

[00:33:59]For example suppose our hash function is k uh mode 7. So for 23 23 divide by 4 the remaining will be two. So 23 will go to the index two because it's empty. We just create a node and put it the number in the first as a first node in this list and then four will go to the slot. Four 16 will be two again. So the 16 will go we will create a new node and put 16 also here.

[00:34:39]So we creating actually a chain 42 will go to the slot zero 8 will go to a slot one and 15 will go to one again.

[00:34:53]So this is chaining.

[00:34:58]Any question here?

[00:35:08]So before we see the code we can discuss like look up, insert and delete here and then you can see the code.

[00:35:17]If we get a new item and we want to insert first we calculate uh the hash function we find the index.

[00:35:29]If that slot is already empty we just create a new node and insert the key there. So this is the first case.

[00:35:39]If uh the index is a slot which is not empty, it means we need to go find the end of this list and then create a note and insert it there. And the third, if we search and find the index and I see that this keys already exist, then you just need to change the value. So we have a three different cases for insertion. If the slot is already empty, so we create a node and insert a pair here. If the slot is not empty and key also not exist, we have to find the end of this chain and create a node and do insertion. And if a slot is not empty and keys already exist, we can just change the value. This is for insertion for delete.

[00:36:37]If we have a key, we want to search and find this key and then when we find we want to remove it from this hash table.

[00:36:46]If we calculate the index and we come for example the key index is six and we found it empty it means this key is not exist. So it should show some message or something that this key is not exist to be deleted.

[00:37:02]Otherwise if it is just uh one node we just safely remove it.

[00:37:10]But what if what we are want to remove is 23 for example.

[00:37:15]If we just simply remove it then we will lost the rest of the chain. So we have to keep the address of this one the next node and then remove 23. So to make sure that we are not losing the rest of the chain. So all this detail need to be uh considered when we want to implement deletion or insertion and then lookup also we just calculate the index again if that key exists we uh return the value associated to that key.

[00:37:50]So this is the implementation.

[00:37:54]First we have to uh define the hash table structure which has a node number of a slots and number of items. We need the number of slots and item to check load factor and whenever the load factor reach to particular threshold then we need to resize it and also each node has a key value and also the pointer to the next item.

[00:38:23]Here how we can create a new hash table.

[00:38:27]We allocate a memory and then allocate a memory for each node and also we initialize the number of slots. um it's a predefined number and also number of item initially zero here insertion that already I said if load factor exceed the threshold you have to do resizing otherwise we calculate the index first and then start the insertion. If we go that index and it is null, it means there is no item associated to that slot. We just increase the number of items and then create a new note and do the insertion.

[00:39:11]If the keys already exist, we just change the value. Otherwise, we have to continue searching on the chain to go to the end of the chain and then do insertion. So this is how the insertion happening. Any question here?

[00:39:34]Uh contain also is a search. So to find a value associated to a key, we give the key to hash function, calculate the index and then we go to that particular slot. If is not empty then we check the key. If we found the key we will return true that we found that key otherwise we have to go down on the change. We go to the next and check. If we go to the end of the list and still we couldn't find the key then we return the false. It means that key is not exist.

[00:40:13]And the third one can say is not exist or you can return the value associated. So get and contains are same things that one of them return the value one of them return just say if this key exists or not then we will see that we can combine these two as a one function. We don't need to have two function for it. And then for delete also again for a key we calculate the index and then call the delete function. And if the list is null it means nothing to delete. Otherwise we have to check the key. If we found the key in associated slot, we have to keep the address of next node otherwise we will break the chain and then free the memory and then reduce the number of items because we delete item from hash table.

[00:41:14]So overall uh the cost analysis for separate chaining suppose we have a n number of arrays m number of store item and this is a load factor if items are evenly distributed we don't have a long long chain and most of the slots empty in this case the insert lookup and delete cost 01 plus load factor or for example All the items are in just one chain.

[00:41:47]Then to do search, insert or look up, you have to check each and every item in worst case to find that what you are looking for. So in this case, uh it will be more complicated. It will be worst case which is OM because for example if you want to do insert you find the slot and there is a long chain you have to go at the end of the chain and do insertion so and the complexity will be O any question here no question for separate chaining So next is linear probing second way of addressing collision in hashing.

[00:42:45]So if in this case if we found the index and index that the slot is already full we have to go to the next and find the first empty spot and do insertion there.

[00:43:02]This is linear probing. So let's see how it works.

[00:43:08]For example, here suppose we want to insert and this is our uh actually uh array.

[00:43:21]Suppose we want to insert 22 and is our hash function is k mode 10. So 22ide by 10 it will be index two. So we can safely insert 22 in this slot because it's empty.

[00:43:38]Suppose the next number is 14. 14 divide by 10 remaining will be four. But we can see that the slot four is already full.

[00:43:46]So we go and check the next slot. This is also full. The next is empty. So we insert 14 in index six instead of four.

[00:43:57]So this is linear probing. Every time we jump to the next slot, we check and as soon as we find the first empty slot, we will do insertion there.

[00:44:10]And the next is eight. U 8 / 10 is 8. 8 is already full. We go to the next is full. So we go to the first of the array. We found the MTS slot. We do insertion there. So this is linear probing. If the slot is already full, we go to the next until we find the first emptiest slot. But now a little bit retrive is more complex because when you calculate the index and check the slot, if you didn't find it, you cannot say right away is not exist because it might be in other neighbors in slots. So it has a little bit extra work to retry the item.

[00:45:00]Any question here?

[00:45:03]Easy.

[00:45:10]So let's see how we implement it and then see how the challenges with linear probing.

[00:45:17]So here each slot can just save one pair of key and value. We don't have any chaining. So each we have a slot we need to know the number of a slot number of item and each slot can save a key and value. And if it is empty we can say it's empty for example true. If it is full we can change it empty to the full to true.

[00:45:44]So to create a new table we allocate memory to the hash table and then we add true to each slot initially. It means all the slots initially are empty and also we initialize the number of slots and also number of item.

[00:46:11]Now insertion. See how we insert.

[00:46:15]If you want to use linear probing again if load factor exceed the threshold you can resize it. It depends on you. You can make a decision how you want to when you want to resize your array.

[00:46:30]And then we have a hash. We give the key and get the index.

[00:46:38]Then start searching to find this index.

[00:46:42]That slot can be either contained the given key. If that key already exists, we need to change the value or u if is is empty, we can insert in that place and if it is not empty, then we have to go and find the next available slot. The implementation is part of week nine lab exercise. But we will see how it works here theorally.

[00:47:12]For lookup again we have a key we converted to the index.

[00:47:20]Uh this is important a start from that index. For example a key is 22 index is two. We have a look to that index. If what we are looking is exist we find a slot and we return um the key that we find but if that slot is empty we cannot say it is not exist we need to continue search that we will see how it work.

[00:47:50]So uh one important point here is you continue search until first empty spot. So let me uh I don't have my pen. Okay. I will show the example here.

[00:48:14]I can show you here.

[00:48:19]For example, we know that 14 is inserted here at six instead of four because four was already full. Five was five was full and then we inserted 14 in index six. Suppose not we are now we are looking for key 14.

[00:48:42]So we should calculate the index for 14.

[00:48:45]The index will be four.

[00:48:49]We come to the index four but we see the key is not 14 is 24. So we cannot say now right away 14 is not exist in linear probing. You have to continue search until the first emptiest spot. If you reach to the first emptiest spot and you couldn't find 14 you can say is not exist otherwise it's possible that is exist. So you come to come to the five.

[00:49:15]This is not the key you are looking and you will find it in the index six and you can say you found the key. But if is not exist you will continue always searching until the first empty spot.

[00:49:28]Then you say if it exists or not exist because it can be displaced because of the type of insertion that we do.

[00:49:39]insertion look up.

[00:49:47]So for example here this pseudo code here if you are want to find a key and return the value for example first you need to calculate uh the index and then you have to check that a slot if that slot is empty it means that's not exist if you find the key you will return the value otherwise you will go and check The next spot you will continue until reach to empty slot. Even if you reach to empty slot and still you didn't find then error and for delete also we need to do some extra things because of linear probing.

[00:50:40]For example, this is our hash function and this is our hash table and these are the values that already inserted. Now we want to delete an item.

[00:50:53]So we want to delete 24.

[00:51:03]For example, we calculate 24 / 10. It will be the remaining will be four. If we come and right away delete 24 from this slot 0 1 2 3 4 from this slot there will be a problem. We cannot do like this because if you make this slot empty next time if you are searching for 14 you will not find the 14. Can you tell me why?

[00:51:43]Because in the previous slide we say if it is empty break it means is not exist but this is wrong because 14 exist but is displaced is somewhere else. So after deleting we need to do some refinement.

[00:51:57]We cannot leave it as it is. We cannot say we delete 24 finish. We have to do some refinement here to make sure that we will not lose 14 or other um displaced items. So how we do it? This is very important. There is two way to address this issue after deleting. This is just for deleting. When you delete an item in linear probing you have to do two type of like refinement.

[00:52:31]One is back shift. It means when you remove one item you have to check all the item between this item and the next empty spot and if is needed do back shift. We will see what is back shift. And the second method is to thumbstone that we will discuss today. So let's start with back shift. Again this is just for deleting.

[00:52:59]So let's see how back shift work. In back shift after we delete the item and we have one empty spot because we delete the item. So we remove the target item the item that we want to delete. We delete that one. and then a scan forward for a deleted position. Continue this scanning until we find the first mtl spot and then temporarily remove and reinst item between the current empty spot and the next empty spot and with needed we have to change the location. So let's see how it work. I think we have an example here. Yes, this is important.

[00:53:48]For example, this is our array and we want to remove 24 and we want to use back shifting for deletion. So first stop is we have to find which index is 24.

[00:54:04]So based on that uh hash function that we had the 24 index is four. So first we remove the 24 from a slot four. 24 was here. We remove it.

[00:54:18]Then we have to check all the items between the current emptiest spot and the next emptiest spot. So we have to check all these items between the current emptiest spot and the next empty spot. So we go to the five. We recalculate the index to see if five is in the right location or not. If you So we need to recalculate the index again based on the function. What was the function? Kide by 10.

[00:54:54]So if you um divide five by 10, the mode is five. So five is in the correct location. You don't need to you don't need to change it location.

[00:55:06]Next we check 14.

[00:55:08]14 14ide by 10 the remaining is four. So it means 14 correct index is four not six. So we have to shift or reinsert 14 to its correct location. We shift the 14 to the empty spot. Next we have to check four.

[00:55:30]fouride by 10 the remaining will be four. So it means this is not the uh right location of the four but we have one empty spot before four. So we reinsert four to this empty spot. So we trying to bring items as close as possible to the right location. So again we shift four also to the six and then check 18. 18 divide by 10 remaining is eight. So this is in its correct location. You don't need to relocate 18. We reinsert it to its colle to its location. So this is back shifting overall.

[00:56:12]One more time. We calculate the index. We remove the item. We check all the items between the current empty spot to the next empty spot. And if is needed we reinsert the item in its own place or we and relocate it based on the index.

[00:56:32]This is also a part of your exercise in week nine. Any question here? Did you understand theorically how it works?

[00:56:42]>> Yes.

[00:56:51]How you know which one is because that can be very large >> and you have to recalculate each of them again to see if they are in the right location or they are being misplaced before I will show you more examples next week also for each of these uh each and every of these operations. Today I'm trying to just introduce all these hash table the operations the all this algorithm that we can use for collision and then I will give you more example Thursday we review each and every of these operation to see how they work but any questions so far so this is back shifting now uh is quite fast but in long term can reduce the performance of your hash table. The back shift actually u initially is a little bit complicated but always keep your hash table more balanced. We will see how buttonstone is quite fast but we will reduce the per performance gradually.

[00:58:30]For tombstone if we need to delete our item we delete it right away and we put some marker on its place. So this markers for if uh the next operation is insertion we it will treat it is as a empty slot and we'll do insertion in it. If we are in lookup function, we treat it as a occupied uh location.

[00:59:02]So let's see how it works. For example, this one again we want to delete 14 and then we want to use method.

[00:59:15]So 14 divide by oh wait which was our okay four. So the hash function is uh um key divide by 10 and calculate the mode.

[00:59:32]So 14ide by 10 the mode is four. So we come here but this is not 14 because is linear probing. You have to go to the nexus slot and here. Okay, this is after 24 sorry. Okay, here we need to first suppose we already deleted 24 and put no six is which item is six that is already deleted. Okay, we suppose we deleted 14. Okay, we deleted 14 in tombstone. We delete the 14 and replace the 14 with a sign or something that uh we can put in can be nan or whatever whatever we consider to uh uh actually say that there was a item that we deleted and then we want to search for four.

[01:00:30]So we calculate the index for four.

[01:00:32]Index will be uh fouride by 10 remaining will be four. The first we come to the index four but this is not the four. We go to the next. This is not the four. We go to the Dell. I said for lookup we consider Dell as a occupied the slot. So we continue searching and then finally we found the four and it will finish. So in when we are doing search this sign means this slot is occupied. We do not treat it as a empty slot.

[01:01:08]If you are doing insertion for example we want to insert 15 so the index will be five so this is already occupied we cannot insert 15 here we go to the next but del in the insertion phase is like a empty slot so we can safely insert 15 in this slot this is thumbstone we delete we put a sign that sign in the insertion phase means means empty slot in the lookup phase means is occupied. So we can continue search.

[01:01:45]Any question.

[01:01:59]So in back shifting we moving item closer to their hash index. You saw that when we remove and we check the next items and if is needed we insert them and move them to their right location.

[01:02:16]So it will reduce the length of the propad. Propad means uh the number of items between two empty spots. We call it cluster also.

[01:02:33]So deletion is more expensive when you are doing back shifting because you need to do some search and reinsertion.

[01:02:40]What is tombstone is quite fast but it cannot reduce the prop path because we do not uh changing the location of any item after deletion and if we do large number of deletion then we will have lots of a spot with the sign of delete. So back shifting pay more during deletion to preserve the future performance but tombstone deletion is quite cheap but in the long term it can u create lots of del sign and also will not reduce this uh prop path that I said that clustering means we have lots of continuous occupied uh slot in the array. So if you have a long cluster and we want to insertion, it uh may we need to uh explore so many slots to find the empty spot to insertion. So uh if you have a very big cluster in our array then it can increase the cost of insertion especially when it uh you inserting lots of item in your hash table.

[01:04:05]Uh okay let's see one example also for um clustering.

[01:04:15]Okay, this is another example. This is hash hash function is k mode 15.

[01:04:20]Initially it is empty. Then we want to do insert. So we have to calculate index for each and every item. 1 / 15 mode is one. So we put one in the slot one. 2 / 15 mode is two. Three also will go in the index tree. 17 will go to the 17 / 15 will be two but 2 is already occupied. We go to the next is also occupied. So we have to go to the next slot and put the 17 here.

[01:04:54]Next is 18. 18 / 15 will be three. Three is already occupied. We go to the next.

[01:05:02]Next is already occupied. So it will come to this index.

[01:05:07]And then we want to insert seven. Seven is already empty directly we insert. 9 is empty directly insert. 22ide by 15 will be seven. Directly insert.

[01:05:20]24 / 15 will be 9.

[01:05:25]9 is already full. So we go to the next spot and insert. 37 will be seven. 7 is already occupied. We have to go until find the empty spot which is 37 here and enable directly to the 11 is also full.

[01:05:41]We go to the next spot and first the first uh possible emptiest spot and then do the insertion.

[01:05:51]How about now eight? Where I should put eight? If I want to insert eight, can you tell me which index it will go?

[01:06:01]>> Which one?

[01:06:04]13 because eight is already full is 22.

[01:06:08]Next full full. So it will come here.

[01:06:11]Eight come here. How about six?

[01:06:18]Suppose we want to insert six.

[01:06:25]Six is already empty. So we can insert it here.

[01:06:31]So this is linear probing.

[01:06:35]Any question here?

[01:06:43]So how much? Okay, I will tell this one also then we can have five minutes break and then do and we'll discuss double hashing.

[01:06:58]So again for lookup cost in linear probing also we need to calculate the load factor alpha which is m / n number of sort um stored item and the number of slots for successful lookup u this is the cost for unsuccessful you may need to search until end of the array so it will give you it will be more costly compared to this one because in linear probing you first check the index and if it's not exist you have to continue until the next empty spot. So it depends on the load factor but this is the average this is the average number of slot that you need to search for lookup.

[01:07:48]Okay, we can have fine five minutes break and then I will continue and if you have any question you can come and What else?

[01:13:31]Let's go.

[01:14:03]Okay. Uh the third technique uh for collision resolution is double hashing.

[01:14:16]In double hashing actually we use two hash functions.

[01:14:21]The first hash function find the index to insert our key. If there is a collision, if the spot is already occupied instead of checking the next slots one by one to find the first empty slot actually we use the second uh hash function and that give us a jump. So instead of going one by one we we will jump to certain um slots and check if that is available or not. So based on output of second function we may jump every two slots and check if there is available a spot again. If it's not again we jump two more slots. So this can improve the distribution of the uh items in the array and will reduce the cluster and having a long uh probe.

[01:15:28]So in double hashing first we calculate the index based on the first hash function.

[01:15:39]We give the key and get the index and then we check that a slot for example a slot I if it is empty we do the insertion if is not empty and the collision appear so we have to compute the step size the step size is actually second hash function and then we go based on the step size we go further and jump to a particular slot and then If it is still full again we need to do next jump until we find the emptiest spot and then we can do insertion.

[01:16:22]So h1 is to find the initial index and h2 is to determine the step size and step size um should be somewhere between one and n minus one. One important point in double hashing is the size of the table and step size should be a prime number. In this case uh we can visit all the slots. Otherwise if we do not choose uh proper uh array size or proper u second hash function then we always don't use few of these slots and then they remain empty.

[01:17:17]We will see how this happen. For example, if our table size is 10 and double hashing gives off a step two, then if the uh start index is one, we always check slot one and then three and then five and then nine, 7, 9 and then one again. So we may not use few of these slots. So to use all the slots properly is better we have a uh actually the table size and the uh the way we choose our second hash table create a prime number for us. In this case we will efficiently use all the slots for saving keys and values.

[01:18:07]This is just for double hashing not for other method. So for example, this is our hash table. We already have 15, 10 and four inserted. And this is our first um hash function to find the index. And if there is a collision, we use the second one to find the number of steps.

[01:18:38]Suppose we want to insert 22. First we find the index. 22 / by 7 remaining will be one. We check the slot one is already occupied. So we have to use now second one to find how many steps we need to go forward to find the next uh slot. So 22 / 3 we get a rem remaining + one. So it will be two. So we jump two slot. So next will be this slot which is occupied already. Again we go two more slot. We found the empty spot. So we uh actually insert 22 in this slot. This is how double hushing works.

[01:19:27]question right insert 22 in the index five. Now another example suppose our table has 11 slots. This is our first hashing function and this is for uh second one to find the steps. We want to insert five. Five divide by 11 remaining is five. So we put in the slot five 20 will be nine. We will because it's empty we right away insert it. 16 will be five. Again we have a collision here. So we have to find the number of steps. 16 remaining by 5 + 1 will be two. So we have to jump two more slots. So we will insert 16 in index 7.

[01:20:26]Next is one remaining is one. So right away we will insert 42. Remaining is nine which is already occupied. So we need to calculate the jump.

[01:20:39]Jump is three. So 1 2 3 will be here again is occupied again. One two three.

[01:20:47]So it will come to uh slot index four and then 15. Uh the remaining is four.

[01:21:01]Four is already occupied. We need to calculate the jump which is one. If we go with one, five is already occupied.

[01:21:08]So it will go to the next. This is the empty spot. So 15 will be inserted here.

[01:21:15]So this is how we do with double hashing.

[01:21:22]To create this table we have this is the data structure that we use for hash table.

[01:21:33]This is a um pointer to the LA. We need to know how many slots we have, how many items and what is our second um hash function but is not a function itself.

[01:21:46]It's important for us the number that we are using for calculating the mode. So normally we save this number. Again, it depends on how you want to design your model because normally this part is fixed and plus one is fixed to make sure it's a prime number. And then we have to make a decision that what number we want to put here.

[01:22:11]And then each item in the hash table has a key value and boolean variable that said if it is empty or already occupied.

[01:22:24]So to create a new new hash table, first we allocate memory and then uh we allocate for each slot and then initialize each slot to true because they are all empty and initialize all the slots items and what actually uh number we can use for calculating the mode for the step one for the second hash table for insertion. As you see first we check load factor is if is already full uh we or reach to the ex um threshold we need to resize it and then we need to for each key we calculate the index using the first hash table hash function and then we calculate the jump in case if we need it and then we start insertion. If the slot that already we want to do the insertion is empty then we insert the key in the key part value in the value part and also the empty will be false because it's already occupied and then increase the uh number of items.

[01:23:35]If is not empty then uh sorry if is already exist uh then we just change the value and if is occupied we have to calculate the new index and then search that spot to see if we can insert there um get also do we want to search and return the value. So again we have to calculate index and increment for the steps and then we check that index. If it is empty it means this item or this uh key is not exist. So break otherwise if the key exists we will return the value and if there is another value key there in that location that we have to jump and check the other spots also. So we have to use this increment and check other spots.

[01:24:43]And if we check all the slots and we still couldn't find it then error it means that um key is not exist for deleting. If you want to delete from u double hashing we back shift can be difficult because in the previous one we know that every time a step is one for all the items but in double hashing a step for each item can be different. It's not fixed. So back shift is quite complex. Normally we use thumbstone for it.

[01:25:27]And complexity again based on load factor.

[01:25:33]Uh number of uh stored item m number of slots n cost of lookup. If you we are searching for an item we have to compute h1 and h2. The complexity is one. is just one time calculate index and uh number of steps and the remaining cost is depend on how many slots we need to check to find what we are looking for.

[01:25:58]For welldesigned hash function if it can distribute items properly it approximately we need to check this amount of uh slots to find uh that item and for unsuccessful search we need to search more.

[01:26:17]So in this best case the complexity or is 01 if directly we check an index and the item is existed an average again 01 if we just need to have a few search and in worst case we may need to check each and every item to find the item that we are looking for which will be O N um for oh this is summary of whatever we discussed today. So if you have a if you are using hashing table and we have a collision we have a separate chaining we have linear probing and double hashing that we discuss um all the approach can be used to achieve 01 performance but it condition is we have a good hashing function that can distribute items properly to reduce the collision. the more collision they make make the whole cost more bad.

[01:27:19]And the next point is uh we have to make a decision that when we want to resize the array that is also uh based on how you design your hash table.

[01:27:36]Um normally for resizing the hash table will double the size. For example, if it is 10 and the load factor is one and we know that it will uh we don't have a space to insert more. Normally we do the size double hash. But if you do double hashing, you have to reinsert each and every item again. It's not like copy.

[01:27:58]For example, if it is 10 item, we copy that 10 item from one to 10 and then the rest are empty. you have to re recalculate again because maybe they are not in their own correct location and you need to change the location after resizing the hash table.

[01:28:18]So, so all the item need to be reinserted.

[01:28:24]So for each and every item that you are copying to the new hash table, you need to recalculate the index again.

[01:28:32]Uh normally we do double size.

[01:28:38]Um and the next thing last thing is we see we have a hasht get and hasht contains one of them just search for a key and if it exists say it is exist and another one if it is exists return the value. So we can easily combine these two and have one function instead of having two different function and have a double cut.

[01:29:05]That's it.

[01:29:08]I will show you more example of using all these techniques next week.

[01:29:16]Any question here?

[01:29:26]Okay, now we have a time. How about the final exam?

[01:29:32]Do you prefer 50% uh theorical section, 50% programming or you prefer 40% theorical section and 60% programming?

[01:29:46]Or you prefer more questions or less question for programming. For example, we have if it's 50/50, you prefer five question each of them mark five or for example four question and we increase the mark. Do you have any preference or just I choose myself >> or no difference?

[01:30:16]>> No, >> more programming.

[01:30:20]>> Okay.

[01:30:23]>> That's has a is also tradeoff because if the mark is high and if you miss one question or you don't cannot answer that will be also big lost. So it's a but you have to take care of time also you just have 3 hours so you have to manage to answer all the question also in 3 hours.

[01:30:50]Okay maybe we can keep it 50/50 and five programming question each of them mark 10.

[01:31:04]Okay. So we will stick with this.

[01:31:09]>> Yeah.

[01:31:11]50/50.

[01:31:12]The number of question for theor theorical part can be more because the question can have a very simple answer one word two word answer also. So number of question is theorical part is more.

[01:31:25]But for programming part I will keep five question each one mark 10.

[01:31:34]Okay, that's it.

[01:31:37]Anything else?

[01:31:40]Last in week 10, we will uh I will show you one example of uh previous year's final exam and we go through all the question. You can see some samples that how the question look like for theoretical and programming part also can give you some insight.

[01:31:59]Okay, that's all for now. See you on Thursday.

[01:32:10]100% programming. Someone suggest 100% programming.

[01:32:16]It's not possible.