Double hashing can still be affected by clustering. Every key that has the same

Question

Double hashing can still be affected by clustering. Every key that has the same value for the second key will probe the table in the same pattern and can still be affected by clusters. Show how to modify the following code so that it computes the second hash value and then uses it in the search. private int locate (int index, T key) [ boolean found = false; while ( !found && (hashTable[index] != null) ) { if ChashTable[index].isInO && key.equals ChashTable[index].getKey ())) found-true; // key found else // follow probe sequence index = (index + 1) % hashTable.length; //linear probing / end while // Assertion: either key is found or a nu1 location is reached int result = -1; if (found) result = index; return result; // end locate

Explanation / Answer

public int secondHash(int key) {
return 6 - key % 6;
}

private int locate(int index, T key) {

int stepSize = secondHash(key);
  
boolean found = false;
while (!found && (hashTable[index] != null)){
if(hashTale[index].isIn() && key.equals(hashTbale[index].getKey()))
found = true;
else
{ //avoid linear probing
index = index + stepSize; //compute second hash value and then calculate new index using it
index = index % hashTable.length;
}
}//end while

//Assertion: either key is found or null location is reached
int result = -1;
if(found) result = index;
return result;
}//end locate

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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