QUESTION: Java: Code the following algorithm for finding the location of an obje

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;
    }

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

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