Hashing tables
k lets go
hey sudaaa lets start from the beging
we learn aloooooot of ways to make search for an element
for example the linear sreach in that type of search we was have to check all the elements till we find our target so in the worest case it cost( n step) if we search an array of size n(the worest case assume that the element in the array[n] i mean the last element in the array )
and the binary search ......etc
but there is a probelm in the normal search way that probelm is that (the more the elements the more the cost in the consederation of the time and the speed of the search so the normal ways of search is not ideal to be used if the array size is very large it is not optimized that case )
thats why we need the hashing it will simplly solve this problem
------------------
how?!!!!!!!
------------------
k lets see
------------------
but friest what is the hashing ?------------------
hmmm suda the hashing is a very cool and simple consept its idea is to caculate the location of the elements in the table so we find it with just one step instead of search all the table to find the element
------------------
it is not clear give an example to make it clear
------------------
k sudaa lets say that we have a table and we wanna to search for an element its value is (99) using linear search how that will be
------------------
we will make a programe check all the element of the array till we find (99)and trhen we will retutn the location to the user .
------------------
geart thats right ......but what if insted of that we use the hashing with a hash function
h(X) = X ....thats mean that if there is an element its vlue is1000 it will be in the location 1000 in the array (array[1000]) thats mean that if we have to search for the element that its value is 99 we will find it in only one step just calculate the hash function of the element it will give the loction of the element in the array wich is array[99]
------------------
come on wht is that hahahahah it is a disaster asmii if we wanna to store let say (1 , 1500)so (we have to store1 in array[1] and 1500 in array[1500])oooooooh make an array of size (1501) to store just 2 elements ....nooo this is not optimized .. the memorry is very Critical we have to be wise when use it
------------------
yaaa u are right myeverything ..... but thay find a cool way to solve that problem just by changing the hash function for example lets say that our hash function is like that (h(X) = X mod 2) so
will store in array[1] cos (1%2=1 1
and 1500 will store in array[0] cos (1500%2=0)
------------------
nooooo asmii ha ha ha loooooool there is anther disaster what if we wanna to store (98 and 1500)
98 will store in array[0] cool but
1500 will store in arry[0] tooo thats not right
------------------
yaaaaa myeverything thats right....thay call that Phenomenon ( collision ) and thay find a sloution for that too
------------------
really so what is it ?!!!!!!!!------------------
acully there is 3 way let see them
------------------
k
------------------
well 1-linear probing
it work that way
it is very simple we will start (“circular” linear search ) from the loction where the collision happend the aim of that search is to find free locarion and then the collision elemnt will be store in that free location
note: it is called “circular” linear search .. cos if it deal with the table as a circle i mean if we reach the end of the table but not find the element we will start from the beginning till we find a free location in the table it looks logic right ?
------------------
yaa it is k what a bout the other ways
------------------
the second way called 2-open- addressing( jumping)
and it some how look like the way # 1
but insted of make (“circular” linear search ) when the collision happen we will make this
lets say that our hash function is this (h(x)=x%31)
if we wanna to store this element 65
h(65)=65%31=3 so we will store ir on array[3]
but what if there is an elemenr alreay in array[3](there is a collision)!!!!!!!
in this case we have to add 1^2 to 3
3+1^2=4 ====array[4]
what if anther collision happen (array[4]) alreay taken
in that case
we subtract 1^2 from 3
3-1^2=2 ====array[2]
what if array[2] already taken ?
we will add 2^2 to 3
3+2^2=7 ===== array[7]
what if array[7] already taken ?
in that case we will subtract 2^2 from 3
3-2^2=30
and soo one till there is noo collision and we find free locarion to store our elemet
------------------
3-2^2=30!!!!!!!!!!!
------------------
ya cos the hash function is (h(x)=x%31)so capacity is 31(the size of the array is 31 from 0 to 30) and we subtract from the index of the array (imagine we are in the location 3 the last location of the array is 30 so if we Subtract 4 mean that we will back 4 srep from 3 so the friest step we are in the location 2 the 2st step we are in locaton 1 the step3 we are in location 0 the step4 we are in location 30 ) thats why (3-2^2=30)
------------------
k what about the last way to solve the collision u said that there is 3 ways
------------------
hmmm hahaha im not know alot about it hahahaha all what i know is that it called Chaining
and that the hash table in this way is in the form of array of linked lists
------------------
ha ha ha ha + lol k
------------------
i hope that will help
hahaha well sudaa sorry if that was not good enough and we just revise the consept part not make a programming cos im not know any thing about c
hahah pls do not laughing cos i have a loooooooot of typing error u know im bad in english
hahaha i used google traneselator to fix my typing error i do not know if it help
k lets go
hey sudaaa lets start from the beging
we learn aloooooot of ways to make search for an element
for example the linear sreach in that type of search we was have to check all the elements till we find our target so in the worest case it cost( n step) if we search an array of size n(the worest case assume that the element in the array[n] i mean the last element in the array )
and the binary search ......etc
but there is a probelm in the normal search way that probelm is that (the more the elements the more the cost in the consederation of the time and the speed of the search so the normal ways of search is not ideal to be used if the array size is very large it is not optimized that case )
thats why we need the hashing it will simplly solve this problem
------------------
how?!!!!!!!
------------------
k lets see
------------------
but friest what is the hashing ?------------------
hmmm suda the hashing is a very cool and simple consept its idea is to caculate the location of the elements in the table so we find it with just one step instead of search all the table to find the element
------------------
it is not clear give an example to make it clear
------------------
k sudaa lets say that we have a table and we wanna to search for an element its value is (99) using linear search how that will be
------------------
we will make a programe check all the element of the array till we find (99)and trhen we will retutn the location to the user .
------------------
geart thats right ......but what if insted of that we use the hashing with a hash function
h(X) = X ....thats mean that if there is an element its vlue is1000 it will be in the location 1000 in the array (array[1000]) thats mean that if we have to search for the element that its value is 99 we will find it in only one step just calculate the hash function of the element it will give the loction of the element in the array wich is array[99]
------------------
come on wht is that hahahahah it is a disaster asmii if we wanna to store let say (1 , 1500)so (we have to store1 in array[1] and 1500 in array[1500])oooooooh make an array of size (1501) to store just 2 elements ....nooo this is not optimized .. the memorry is very Critical we have to be wise when use it
------------------
yaaa u are right myeverything ..... but thay find a cool way to solve that problem just by changing the hash function for example lets say that our hash function is like that (h(X) = X mod 2) so
will store in array[1] cos (1%2=1 1
and 1500 will store in array[0] cos (1500%2=0)
------------------
nooooo asmii ha ha ha loooooool there is anther disaster what if we wanna to store (98 and 1500)
98 will store in array[0] cool but
1500 will store in arry[0] tooo thats not right
------------------
yaaaaa myeverything thats right....thay call that Phenomenon ( collision ) and thay find a sloution for that too
------------------
really so what is it ?!!!!!!!!------------------
acully there is 3 way let see them
------------------
k
------------------
well 1-linear probing
it work that way
it is very simple we will start (“circular” linear search ) from the loction where the collision happend the aim of that search is to find free locarion and then the collision elemnt will be store in that free location
note: it is called “circular” linear search .. cos if it deal with the table as a circle i mean if we reach the end of the table but not find the element we will start from the beginning till we find a free location in the table it looks logic right ?
------------------
yaa it is k what a bout the other ways
------------------
the second way called 2-open- addressing( jumping)
and it some how look like the way # 1
but insted of make (“circular” linear search ) when the collision happen we will make this
lets say that our hash function is this (h(x)=x%31)
if we wanna to store this element 65
h(65)=65%31=3 so we will store ir on array[3]
but what if there is an elemenr alreay in array[3](there is a collision)!!!!!!!
in this case we have to add 1^2 to 3
3+1^2=4 ====array[4]
what if anther collision happen (array[4]) alreay taken
in that case
we subtract 1^2 from 3
3-1^2=2 ====array[2]
what if array[2] already taken ?
we will add 2^2 to 3
3+2^2=7 ===== array[7]
what if array[7] already taken ?
in that case we will subtract 2^2 from 3
3-2^2=30
and soo one till there is noo collision and we find free locarion to store our elemet
------------------
3-2^2=30!!!!!!!!!!!
------------------
ya cos the hash function is (h(x)=x%31)so capacity is 31(the size of the array is 31 from 0 to 30) and we subtract from the index of the array (imagine we are in the location 3 the last location of the array is 30 so if we Subtract 4 mean that we will back 4 srep from 3 so the friest step we are in the location 2 the 2st step we are in locaton 1 the step3 we are in location 0 the step4 we are in location 30 ) thats why (3-2^2=30)
------------------
k what about the last way to solve the collision u said that there is 3 ways
------------------
hmmm hahaha im not know alot about it hahahaha all what i know is that it called Chaining
and that the hash table in this way is in the form of array of linked lists
------------------
ha ha ha ha + lol k
------------------
i hope that will help
hahaha well sudaa sorry if that was not good enough and we just revise the consept part not make a programming cos im not know any thing about c hahah pls do not laughing cos i have a
loooooooot of typing error u know im bad in english hahaha i used google traneselator to fix my typing error
i do not know if it help