Search by hashing techniques 1) Hashing with linear probing 2) (bonus) Hashing w

Question

Search by hashing techniques

1) Hashing with linear probing

2) (bonus) Hashing with quadratic probing

3) (bonus) Hashing with chaining

Choose your hash function and hash table size that suits your test data such that collision code can be verified.
As an example, if I'm searching just 6 integers, I may have a table of 11 entries and a hashing function of "fold digits mod 11". By mindfully choosing the test data, I would be able to know if my collision algorithm and search algorithm works.

You should write the insertion routine to "add" items into the hash table. It will make it easier to create your database.

Try to do a delete routine too. There are additional considerations to be exercised.

Explanation / Answer

Let the 6 integers to be searched or placed in the above array are [2,10,20,30,13,25] , a table of 6 entries.

Hashing with Linear Probing calculates index value for each integer using formula

H i(x) = Hash(x) + f(i) mod 11 with f(i)=i.

Array is searched in sequential manner using above formula , until an empty cell is found.

H(2)= 2 mod 11= 2(index)

H(10)= 10 mod 11= 1(index)

H(20)= 20 mod 11= 2, but 2 index is not free so next we ll calculate H1(20)= (2+1) mod 11=3(index).

H(30)= 30 mod 11=3, but its not free so: H1(30)= (3+1) mod 11= 4

H(13)= 13 mod 11=2, its unavailable so

H1(13)= (2+1) mod 11=3, again collision, so

H2(13)= (3+1) mod 11= 4, again collision, so

H3(13)=(4+1) mod 11=5.

and so on. This way we ll put all the values in the calculated indexes as shown above.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.