All language subtitles for 28 - How to Develop a Good Hash Function English

This video I'm going to walk through what it takes to create a good hash function.

So before we decide what it takes to create a good hash function that's probably important to understand

what a hash function is.

And so what a hash function is is a delimiter that separates certain values into a data structure and

show you how this works visually and think of that as being able to have nice buckets that you can put

things in.

So of bucket one bucket two bucket three and four.

So one two three and four.

So if we were to have a set of data so say we have an array and arrays a made up of just these four

items so we have 1 4 2 3 2 1 4 1.

So this is our array in a hash function the way it would work is you would go through each item and

you would designate it to go into a particular bucket.

So you know one on one just like that.

And for your fours these two fours just click here.

I'm not doing this in any order as you probably notice men or twos look like that.

And for LWN three there we go.

So that's a way that a very very basic hash function works.

Now the problem with hash function or how hash tables is that they can be incredibly fast in the last

you have to deal with a lot of collisions and what collisions are.

Are these things right here.

He knows the three doesn't have one because only has one item.

Ideally you want to have as few collisions as possible so your hash tables have a round the same amount

of values going inside of them.

In fact if you want to write down a property the best definition that I've been able to see for what

it takes to create a good hash function is that the function should provide a uniform distribution of

hash values.

And this is because a non uniform distribution increases the number of collisions and the cost of resolution.

That's just a lot of fancy talk for saying say that this data was not what it is right now.

So say that we had.

And I'm going to raise this and we're going to work on some different values right here.

So we're still going to have our one our two three and our four except we're going to deal with a different

data set.

So in this dataset we're just going to have one

say We have a data set like this where a reasonable way of 90 percent of the data is actually the same

exact value.

This wouldn't be good because all we would have are collisions.

And if you remember back to the definition we want a uniform distribution uniform distribution means

that we should essentially have the same number of elements in each one of these buckets.

So each one of these should have as close to the same number of items as possible.

And so a good way of doing this is looking at an example.

So the example I'm going to use will get rid of all of this right here because I'm going to do actual

real life example.

This is one of my professors at the University taught when he explained how hash functions work and

how to create a good one.

Say that you wanted to organize students at a university you have a number of different options in terms

of having some theme that there's some fast way of looking them up.

So if you have a student

as a student right here there is a few different ways that you may be able to categorize a student so

you could probably say he may have a social security number he may have a phone number he may have a

driver's license and he will have a student ID.

Now when we're looking at a good hash function remember we're looking for something that has a uniform

distribution and so phone numbers even if you could assume that every every student had a phone number

you wouldn't have a uniform distribution because the majority of them if they're local students are

all going to have what they're all going to have similar area codes.

So this is not going to be uniform distribution so phone number would not be a good thing.

Driver's license seems like it would be a good one except for the fact that you're dealing with students

from different states and differ and they're in different parts of the world.

One you have students that are not even going to have a driver's license so if you even have a single

student who does not have it then it's not going to work as a hash function because every element has

to have this ID.

So that's not going to work.

And the other problem is you typically want to work with items that have the same numbers.

There's the same count of numbers so in other words if you have a driver's license number from one state

that has letters and then numbers compared with a different state that has a different set of numbers.

This is not going to be a good hash functions.

A driver's license is already not good for a number different reasons Social Security number would be

one of the best options except for the fact that you have a lot of students at universities that are

international and they do not have a Social Security number.

So that's not going to be the best option.

Because remember every single student has to have this in order to be looked up.

So that leaves the student ID as being one of the best options.

It's something every student has.

And it also has a uniform distribution.

And what I mean by that is say we have three students here say we have John

celly and Sam they have a corresponding I.D. and that corresponding I.D. is all going to be the same.

So the idea may be a seven digit number.

So we can say a 7 6

we'll just go 6 digits.

Just keep it easy 2 1 in 4 2 3 and then we'll do 7 2 4 6 2 8.

OK.

So why this.

And this is all coming from the student 90.

Why this would be a good hash function is because each one of these items fits all the properties of

a good hash function they're uniform meaning that every student has one.

They have a uniform distribution which means that these numbers are generated randomly.

So they're all different meaning that they should by mathematical probability laws.

If you have enough students that you should actually have the same number of students in each virtual

bucket of your hash table which means that your number of collisions should be minimized.

And they also have the same count.

So here are six items there of six.

On the second one and six on the third one and so that matches there.

So one of the best house hash functions for for's university student as just an example this can be

used in a number of different operations and it is as hash tables are incredibly useful in a number

of different fields of computer science.

This is a great way of generating one.

These are the properties a big thing to remember is just making sure that the data and the values are

as random as possible.

They're uniformly distributed and they are available for every single item that needs to be searched

for and categorized.

So that's what it takes to make a good hash function.

Please let me know if you have any questions whatsoever and I'll see in the next video.