1
00:00:00,430 --> 00:00:04,330
‫So now we're going to talk about the big oh of hash tables.

2
00:00:04,540 --> 00:00:11,530
‫So I'm going to bring up a hash table like this and I'll bring up our hash function like this.

3
00:00:11,800 --> 00:00:21,040
‫And what I'm going to talk about is the big o of get and set and remember that get and set both use

4
00:00:21,070 --> 00:00:22,360
‫the hash function.

5
00:00:22,720 --> 00:00:28,870
‫So the first thing we need to determine is what is the big o of the hash function.

6
00:00:29,140 --> 00:00:32,530
‫And we consider this to be a of one.

7
00:00:32,920 --> 00:00:40,660
‫Now, you might be thinking that since these keys are of variable length, that we shouldn't call this

8
00:00:40,660 --> 00:00:46,600
‫o of one, that it should be o of the number of characters in the key.

9
00:00:47,050 --> 00:00:52,600
‫But in, in this case is not the number of characters in the key.

10
00:00:53,020 --> 00:00:57,790
‫N is the number of key value pairs in the hash table.

11
00:00:58,090 --> 00:01:00,480
‫So you have to think about it like this.

12
00:01:00,490 --> 00:01:07,360
‫If you had a hash table with a million key value pairs in it, it wouldn't matter if you're running

13
00:01:07,360 --> 00:01:09,070
‫a hash on a key.

14
00:01:09,070 --> 00:01:15,010
‫That's a few more characters long, even if you had a key, that was a hundred characters long.

15
00:01:15,130 --> 00:01:21,280
‫A hundred is irrelevant if N is a million key value pairs.

16
00:01:21,880 --> 00:01:30,100
‫So let's look at setting an item washers, let's say for this hash function that washers will be at

17
00:01:30,100 --> 00:01:31,690
‫the index of zero.

18
00:01:32,140 --> 00:01:35,350
‫Adding that item is going to be o of one.

19
00:01:35,890 --> 00:01:43,810
‫Then if we do a get and we say get screws and we run this through our hash, we get an index of six

20
00:01:43,810 --> 00:01:48,790
‫and then we find screws as an O of one operation.

21
00:01:49,270 --> 00:01:56,590
‫But what if instead of having a hash table that looks like this, it looks like this.

22
00:01:57,010 --> 00:02:03,580
‫Now, when we do get screws, we start at the index of two, and then we have to iterate through this

23
00:02:03,580 --> 00:02:09,520
‫entire length list to be able to get to the item we're looking for, which is screws.

24
00:02:10,030 --> 00:02:14,170
‫This is technically our worst possible scenario.

25
00:02:14,380 --> 00:02:22,180
‫So in the most technical sense, a hash table is O of n, but even with an address space that is this

26
00:02:22,180 --> 00:02:28,660
‫small, if you had a few more items than this, you had 12 items in the hash table.

27
00:02:28,990 --> 00:02:37,360
‫The chances that they would all line up at the same index like this if you had 12 items, would literally

28
00:02:37,360 --> 00:02:40,030
‫be billions to one.

29
00:02:40,450 --> 00:02:48,160
‫So with the hash table, we assume it's going to look something more like this and we treat it as if

30
00:02:48,160 --> 00:02:49,720
‫it is o of one.

31
00:02:50,080 --> 00:02:57,370
‫And we treat it this way because it is almost mathematically impossible for it to act like an o of n

32
00:02:57,370 --> 00:02:58,480
‫data structure.

33
00:02:58,870 --> 00:03:02,800
‫And that is hash table big o.