Afrikaans
Akan
Albanian
Amharic
Armenian
Azerbaijani
Basque
Belarusian
Bemba
Bengali
Bihari
Bosnian
Breton
Bulgarian
Cambodian
Catalan
Cebuano
Cherokee
Chichewa
Chinese (Simplified)
Chinese (Traditional)
Corsican
Croatian
Czech
Danish
Dutch
English
Esperanto
Estonian
Ewe
Faroese
Filipino
Finnish
French
Frisian
Ga
Galician
Georgian
German
Greek
Guarani
Gujarati
Haitian Creole
Hausa
Hawaiian
Hebrew
Hindi
Hmong
Hungarian
Icelandic
Igbo
Indonesian
Interlingua
Irish
Italian
Japanese
Javanese
Kannada
Kazakh
Kinyarwanda
Kirundi
Kongo
Korean
Krio (Sierra Leone)
Kurdish
Kurdish (Soranî)
Kyrgyz
Laothian
Latin
Latvian
Lingala
Lithuanian
Lozi
Luganda
Luo
Luxembourgish
Macedonian
Malagasy
Malay
Malayalam
Maltese
Maori
Marathi
Mauritian Creole
Moldavian
Mongolian
Myanmar (Burmese)
Montenegrin
Nepali
Nigerian Pidgin
Northern Sotho
Norwegian
Norwegian (Nynorsk)
Occitan
Oriya
Oromo
Pashto
Persian
Polish
Portuguese (Brazil)
Portuguese (Portugal)
Punjabi
Quechua
Romanian
Romansh
Runyakitara
Russian
Samoan
Scots Gaelic
Serbian
Serbo-Croatian
Sesotho
Setswana
Seychellois Creole
Shona
Sindhi
Sinhalese
Slovak
Slovenian
Somali
Spanish
Spanish (Latin American)
Sundanese
Swahili
Swedish
Tajik
Tamil
Tatar
Telugu
Thai
Tigrinya
Tonga
Tshiluba
Tumbuka
Turkish
Turkmen
Twi
Uighur
Ukrainian
Urdu
Uzbek
Vietnamese
Welsh
Wolof
Xhosa
Yiddish
Yoruba
Zulu
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.
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.