A 23 element array has been allocated to store nodes using the LQHashed data structure discussed in this chapter. Give the array index used to store the nodes with the following keys, assuming they are inserted in the order given:

a) 4618

b) 391

c) 6941

d) 547

Note: Use the 4k + 3 prime 19 to resolve any problems with the quotients.

public class LqHashed { int N; int n = 0; // the number of nodes in the structure int defaultQuotient = 9967; // the default 4k+3 prime double loadingFactor = 0.75; Listing deleted; // the dummy node, v2 private Listing[] data; // the primary storage array public LqHashed(int length) { int pct = (int)((1.0/loadingFactor-1) *100.0); N = fourKPlus3(length, pct); data = new Listing[N]; deleted = new Listing("","",""); for(int i = 0; i 1; d--) { if(prime%d == 0) break; } if(d != 1) // prime not found prime = prime +2; else aPrime = true; }// end of the prime search loop if((prime-3)%4 == 0) fkp3 = true; else { prime = prime +2; aPrime = false; } }// end of 4k+3 prime search loop return prime; } public static int stringToInt(String aKey) // from Figure 5.18 { int pseudoKey = 0; int n = 1; int cn= 0; char c[] = aKey.toCharArray(); int grouping =0; while (cn < aKey.length()) // there is still more character in the key { grouping = grouping << 8; // pack next four characters in i grouping = grouping + c[cn]; cn = cn + 1; if (n==4 || cn == aKey.length()) // 4 characters are processed or no more characters { pseudoKey = pseudoKey + grouping; n = 0; grouping = 0; } n = n + 1; } return Math.abs(pseudoKey); } }