What is a hash function?
It's something that's used all across computer science.
A hash function is simply a function that generates a value of fixed length for each input that it gets.
All right.
What does that mean?
Well, I have here a MD5 hash generator.
MD5 is the type of hash function and there's many, many types you might have heard of SHA one, SHA
256 and many others.
Using this hash function.
Let's see what happens if I do.
Hello.
You see that right away.
MD5 hashes this string and turns it into this gibberish.
That's what a hash function does.
We give it an input and the function generates some random pattern.
Now there's some key aspects of hash functions.
First is that it's one way.
In the sense that if I give somebody this, they have no idea what the input was.
And it's practically impossible for me to have any clue as to what the input is.
The second is that no matter how many times I put hello in there, it's going to be the same.
But I as soon as I change one thing, it's going to completely change the output.
If I go back to hello and.
Watch me just changed to capital H, even a capital letter.
So it starts with five D for if I do capital H, it's completely different again.
And looking at this, we can at least say that.
Hmm.
I don't know what this is useful for, but the one thing that I know is that no matter what, if I give
it the same input, it's going to give me the same result.
But I have no idea how to convert this back into.
Hello.
This is what we call independent or independent.
There's different pronunciations.
I'm not really sure which one is which, but it is a fancy way of saying that a function given an input
always outputs the same output.
Now, the one benefit and why we would want to use this in a data structure is that we get really fast
data access because all I have to do to find grapes or basket dot grapes is to pass grapes into something
like an MD5 hash.
It generates this number for me and I immediately know where it is in my memory on our computer.
But this doesn't look like an address, does it?
Technically a hash function that we use for hash tables is going to take grapes, generate some sort
of gibberish, and then convert it to an index space or an address space that it has based on this number.
You see, unlike a race where we just had ordered indexes with hash tables, all we need to do is give
it a key and we know exactly where that item is in our memory.
But you might be wondering, this black box hash function, doesn't it slow things down?
Because every time we want to add a property.
And a value grapes and 10,000 to a hash table.
We have to run it through the hash function so we can decide where to put it in memory.
And if you've noticed that good job, that is a big factor.
You don't want this to take a very long time because, well, every time you add a property to memory
or retrieve a property to memory, because, again, we both times we're sending the key grapes into
the hash function to find where to get it from.
We need this to be really, really fast.
And underneath the hood, remember, because hash tables exist in all languages, they're implemented
with an optimum hashing function that's really, really fast.
As a side note.
Hash functions like SHA 256 take a really long time to generate a hash.
And it is an overly complex hashing function that is used a lot in places like cryptography where you
want this to take longer, but that is outside the scope of this course.
If you're interested, I do recommend that you check out the differences between these two.
To review.
We have a key that is grapes.
We send it through a hash function that is going to hash something really, really fast and then map
whatever the hash came out to be into a memory address where we want to store our.
Data are grapes 10,000.
And when it comes to hashing functions, you typically leave this to whatever framework or language
you're using.
And we usually assume a time complexity or big old notation of oh one, because this happens really
fast.
All right.
Now that we understand what this black box does, let's talk a little bit more about hash tables, why
they're useful and why in some cases are better than arrays.