Consider the following hash function:
which is used in a Hash Table which has linear probing implemented (with a standard probe step size of 1).
Also, consider the following strings:
Calculate and state the hash value of the above strings. Explain and show how they are inserted into the table (using the same order of insertion). State what happens when you search for the strings “python”, “java” and “program”.
Ord values: h: 104, w: 119, p: 112, t: 116
Hash Value:
“hello”: 104%13=0
“world”: 119%13=2
“python”: 112%13=9
“hash”: 104%13=0
“table”: 116%13=12
“programming”: 112%13=9
2 collisions
Insersion:
front 3 will be insert normally because no conflict.
which is [‘hello’, ,’world’,…, “python”..]
the forth elements “hash” have same hash value as first elemnts”hello”, so there is a conflict, and then we add the hash value by probe step (1) becomes 1 and then we check if there is any elements in there, if yes add another step, if no place it in.
becomes: [‘hello’,’hash’ ,’world’,…, “python”..]
we apply the same rule to other insert elements as well, we got:
[‘hello’,’hash’ ,’world’,…, “python”, ‘programming’,.., ‘table’]
Searching:
we need to put the elements we are going to search into the hash function to get hash values.
“python”=9
“java” = 106%13=2
“program”=9
If we are going tosearch python, we access 9th elements in the hash table, check if there is the right elements there. It is, then return the value.
If there is no the right elements, 9th place is ‘python’ not ‘program’, we add the probe step into the hash value, and keep looping untill it looped throgh whole table, it is not there so return false or raise error.
If there is no value stored in the hash value link ‘java’, it will return false or raise error.