Homework 4: Hashing using Linear Quotient Collision Algorithm (LQ)

How to submit: Upload to Blackboard under assignment 4


Name:
CMSC 341 Homework 4
LQ Hashing
Another hashing collision algorithm is called Linear Quotient (LQ) and is another form of double hashing with a few twists.
Requires a 4K+3 prime for the primary storage array. A prime is a 4k+3 prime if there is an integer, k, such that p = 4k + 3.
857 is not a 4k+3 prime: k = (857 - 3) / 4 = 213.5 
859 is a 4k+3 prime: k = (859 - 3) / 4 = 214.0
Uses a load factor of .75.  If you know you will be storing about 5100 nodes in the primary storage area, calculate the size based on the load factor
5100/.75 = 6,800
Select the 4K + 3 prime just larger than 6,800.

Here are some prime numbers between 6673 and 6997:

Choose 6803 – is it a 4K+3 prime?
(6803-3)/4 = 1700.0 YEP it is!
6803 will be the size of the primary storage area
Collision algorithm for an array of size N 
ip = (ip + offset) % N, where: 
offset = q if (q%N != 0) ; else offset = a 4k+3 prime
N is the array size, 
q = key / N (integer division)


Example
N = 19, 4k+3 prime = 23 ip is result of the initial hash (key % N)
Case 1: key = 593.  Initial hash: ip = 593%19 = 4. Let’s assume 4 is already full.
LQ collision algorithm: key = 593, q=593/19 = 31, q%19 = 31%19=12 (not equal to 0, use 31 as offset)
ip = (ip+31)% 19, so the next index we would check would be (4+31)%19 = 16
if 16 was filled, the next index we would check would be (16 + 31)%19 = 9

Case 2: key = 5058. Initial hash: ip = 5058%19 = 4. Let’s assume 4 is already full.
LQ collision algorithm: key = 5058, q=5058/19 = 266, q%19 = 0, we use the 4K+3 prime (23) as offset
ip = (ip+23)% 19, so the next index we would check would be (4+23)%19 = 8
if 8 was filled, the next index we would check would be (8 + 23)%19 = 12

Case 3: key = 251.  Initial hash: ip = 251%19 = 4. Let’s assume 4 is already full.
LQ collision algorithm: key = 251, q=251/19 = 13, q%19 = 13%19=13 (not equal to 0, use 13 as offset)
ip = (ip+13)% 19, so the next index we would check would be (4+13)%19 = 17
if 17 was filled, the next index we would check would be (17 + 13)%19 = 11




Given the following key values,  Draw what the open addressing data structure would look like after insertions using the LQ Hashing Collision Algorithm, use 23 as your 4K+3 prime
66 47 87 90 126 145 153 177 285 393 467 566 620 735

First determine what the size of the primary storage area should be

We need an array of S = 19/ 0 .75 = 18.67 = 19

Draw the array (No hand drawing, use a table)


Index


0
145
1
153
2
735
3


4


5


6
177
7
285
8
620
9
66
10


11
47
12
126
13
393
14
90
15
87
16
467
17
566
18







Given the following key values, draw what the chained data structure would look like after insertions using the primary storage area N = 7 using the modulo remainder technique. Assume inserted items are inserted to the beginning of the bucket’s list.
66 47 87 90 126 145 153 177 285 393 467 566 620 735
Draw the chained data structure (No hand drawing, use tools available to you in word)

0
735 , 126
1
393
2
177
3
87,66
4
620
5
467,285,145,47
6
566,153,90









Fill in the following table based on the previous questions

Number of comparisons to retrieve this element

Key
Open addressed array – length of collision path +1 (for initial hash)
Chained array - # of elements in linked list compared + 1 (for initial hash)
66
1
2
467
4
1
566
3
1
735
1
1
285
3
2
87
2
1


 can you look over my answers and check if theyre correct