Not sure what am I suppose to do on this question, since collision probing doesn

Question

Not sure what am I suppose to do on this question, since collision probing doesn't sound like linear hashing.

1) Assuming a Linear Quotient hashing scheme is used and that the size of the primary storage area, N, is 19 and that the default prime is 2311, calculate the first 3 indices (home index and 2 collision probes) for the following pseudo keys: pk = 119,651 pk = 4,456,556 1st index (home) 2nd index calculated 3rd index calculated

2) Assuming the first two nodes inserted into the structure had the pseudo keys in question 1 with (key 119,651 inserted first), give the index of the array element that would store the location of the deep copy of these nodes. ___________________________ and __________________________

3) Assuming a node whose pseudokey is 401,975 is the third node inserted into the structure, give the index of the array element that would store the location of the deep copy of this node. _____________________________________________________________________

4) What is the loading factor after the three nodes have been inserted into the structure? ____________________________________________________________________

5) A maximum of 3,000 nodes are to be inserted into an LQ hashed structure whose maximum loading factor will be of 85%. a) Give the average search length. ________________________________ b) Give the size of the primary storage area array (show your calculations).

Explanation / Answer

1) Given: N = 19
Default Prime = 2311
quotient q = pk/N
where, N is the number of elements in the primary storage area (4k+3)
pk is the value of integer pseudo key
Therefore, for pk = 119651
q=119651/19 = 6297.42
Home index is given by ip,
ip = ip + q % N
ip = ip + 6297 % 19
ip = 11
Home index = 11

for pk = 4456556
q=4456556/19 = 234555.58
Home index is given by ip,
ip = ip + q % N
ip = ip + 234555 % 19
ip = 18
Home index = 18

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

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