Up until now, we've talked a lot about hashing functions. The hashing function is going to sometimes result in a collision where two different inputs are hashed the exact same value. Under sue how, this should be rare, but it may happen quite often if we don't have a strong hash algorithm. Let's look at some strategies to deal with this. The first strategy, the idea of separate chaining is going to be a strategy where we're going to dive into the array but you treat it more like a linked list. Every time we run into a collision, we'll simply add the element to the linked list. Let's look at how this might work. Here, I have a number of values in my set S that I'll be inputting into our hash table. Our hash function is K mod seven. So, here, we're going take the value 16, multiply it by seven, and we get a remainder of two. So, we know we need to hash into in x2 and add the value 16 to value two. Here are array and seven of being an array of values, it's an array of linked lists where each list is initially empty. Next value, eight, eight mod seven is one. So, we go ahead and add eight to index one. Next value is four, four mod seven is four and go ahead and add that right here. Next, I use 13, 13 mod seven is six. So, we can add 13 off of six. Now, we have 29, 29 mod seven is 28 remainder one. So, here, we have a value of one. Now, we have a collision. When we have a collision in separate chaining, we can simply look at this and say, how can we insert into a linked list as quickly as possible? From earlier in the semester, you learned that inserting into a linked list can be done in O of one time if I insert at the beginning. So, in separate chaining, whenever we have a collision, we're just going to simply insert at the beginning of the linked list. Let's do that here. Here, we're going to go ahead and move eight out of the way to put 29 at the front and then link to eight afterwards. Next element is 11, 11 mod seven is four. We have another collision, so we put 11 at the front, moving four back and finally, 22 mod seven is another collision and it maps to the value one. So, here, at the front of one, we have 22. That then points to 29 and then 0.8. So, using separate chaining, we have an ability to deal with collisions by simply adding two linked list. You can imagine the very, very worst case of this algorithm would be quite bad. If we had a hash function that always kept returning to the same value, what we have is we have a linked list that grows in size equal to exactly the value of the number of data in our hash table. That means our algorithm is going to run in O of n time if we ever have to find something inside the hash table. This is going to be really, really bad and down here on the right-hand side, we see the worst case for an insert is O of one but the worst case to find it is O of n. If we have this simple uniform hashing assumption to be true, we know that the insert time still O of one, we can always enter the front of the linked list. But to remove find, we're going to express in a new variable. A variable that I'm going to call alpha. This alpha is going to be the load factor of the table. The load factor of the table is alpha is going to be defined as the number of elements inside of the table divided by the size of the table itself. So, little n divided by big N. This term determines how full the table is. A load factor of 1.0 means that you have exactly as much data in the table as there is space in the array. A load factor of 0.5 means on average, the arrays have four or we have linked lists that wouldn't fill up half the array or half the table if we put them in there. A load factor of two means on an average, every single node has two items in the linked list. So, you can see as a load factor grows, the amount of time it takes to run this algorithm is also going to grow. Here, we have just one strategy of doing separate chaining. In the next video, I'm going to discuss another strategy that's going to take a completely different approach to doing this. I'll see you then.
