QUESTION: Java: Code the following algorithm for finding the location of an obje
ID: 3824640 • Letter: Q
Question
QUESTION:
Java: Code the following algorithm for finding the location of an object as a static method. Assume a hash table array and an object to be located in the table are passed as arguments. Return the object’s position if it is found; return -1 if the object is not found.
Computer the index by taking the hashCode() % table.length
If table[index] is null
The object is not in the table
Else if table[index is equal to the object
The object is in the table
Continue to search the table(by incrementing index) until either the object is found or a null entry is found
HASHTABLECHAIN CODE
HASHTABLEOPEN CODE
Explanation / Answer
for open addressing:
private static int search(Object[] array, Object key) {
// Calculate the starting index.
int index = key.hashCode() % array.length;
if (index < 0) {
index += array.length; // Make it positive.
}
if(array[index] != null && (key.equals(array[index])))
return index;
if(array[index]==NULL)
return -1;
// Increment index until an empty slot is reached
// or the key is found.
while ((array[index] != null)
&& (!key.equals(array[index]))) {
index++;
// Check for wraparound.
if (index >= array.length) {
index = 0; // Wrap around.
}
}
if(array[index]==null)
return -1;
else
return index;
}
------------------------------------------------------------------------------
For Chaining:
public static int search(K key) {
int index = key.hashCode() % table.length;
if (index < 0) {
index += table.length;
}
if (table[index] == null) {
return -1;
}
// Search the list at table[index] to find the key.
for (Entry<K, V> nextItem : table[index]) {
if (nextItem.getKey().equals(key))
{
return index; //If found
}
}
return null;
}