1
00:00:00,510 --> 00:00:03,750
‫So in this video, we're going to talk about collisions.

2
00:00:04,320 --> 00:00:08,880
‫So I'm going to bring up an address space and add some items to our hash table.

3
00:00:09,090 --> 00:00:15,900
‫And a collision is when we have a key value pair that's going to map to the same address as another

4
00:00:15,900 --> 00:00:17,190
‫key value pair.

5
00:00:17,550 --> 00:00:23,310
‫And one of the ways that we can handle this is just by putting both of them at the same address.

6
00:00:23,490 --> 00:00:27,270
‫And when we do this, it's called separate chaining.

7
00:00:27,660 --> 00:00:31,830
‫And this is the most common way of handling collisions in a hash table.

8
00:00:32,250 --> 00:00:35,160
‫But now let's look at another way of handling collisions.

9
00:00:35,160 --> 00:00:38,460
‫That's probably the second most common way.

10
00:00:38,760 --> 00:00:44,010
‫And with this way, we do not store both of them at the same address.

11
00:00:44,280 --> 00:00:49,530
‫If there's a duplicate, will look to the next index to see if that is empty.

12
00:00:49,530 --> 00:00:53,010
‫And if it is, we'll store it there.

13
00:00:53,580 --> 00:01:00,450
‫And if we have another item that maps to that address, we'll just start moving through the indexes

14
00:01:00,450 --> 00:01:04,380
‫until we find one that's empty and store it there.

15
00:01:04,920 --> 00:01:12,120
‫This method is called linear probing, and it is a form of open addressing.

16
00:01:12,780 --> 00:01:19,410
‫Now, the way we'll do it in this course is we're going to store all of these at the same address,

17
00:01:19,410 --> 00:01:25,230
‫which is separate chaining, but it is not going to look exactly like this.

18
00:01:25,230 --> 00:01:31,680
‫The way we're going to do it is with a linked list at each one of these indexes.

19
00:01:32,280 --> 00:01:36,120
‫And that is how we will deal with collisions.