‫So now we're going to talk about the big oh of hash tables.
‫So I'm going to bring up a hash table like this and I'll bring up our hash function like this.
‫And what I'm going to talk about is the big o of get and set and remember that get and set both use
‫the hash function.
‫So the first thing we need to determine is what is the big o of the hash function.
‫And we consider this to be a of one.
‫Now, you might be thinking that since these keys are of variable length, that we shouldn't call this
‫o of one, that it should be o of the number of characters in the key.
‫But in, in this case is not the number of characters in the key.
‫N is the number of key value pairs in the hash table.
‫So you have to think about it like this.
‫If you had a hash table with a million key value pairs in it, it wouldn't matter if you're running
‫a hash on a key.
‫That's a few more characters long, even if you had a key, that was a hundred characters long.
‫A hundred is irrelevant if N is a million key value pairs.
‫So let's look at setting an item washers, let's say for this hash function that washers will be at
‫the index of zero.
‫Adding that item is going to be o of one.
‫Then if we do a get and we say get screws and we run this through our hash, we get an index of six
‫and then we find screws as an O of one operation.
‫But what if instead of having a hash table that looks like this, it looks like this.
‫Now, when we do get screws, we start at the index of two, and then we have to iterate through this
‫entire length list to be able to get to the item we're looking for, which is screws.
‫This is technically our worst possible scenario.
‫So in the most technical sense, a hash table is O of n, but even with an address space that is this
‫small, if you had a few more items than this, you had 12 items in the hash table.
‫The chances that they would all line up at the same index like this if you had 12 items, would literally
‫be billions to one.
‫So with the hash table, we assume it's going to look something more like this and we treat it as if
‫it is o of one.
‫And we treat it this way because it is almost mathematically impossible for it to act like an o of n
‫data structure.
‫And that is hash table big o.