Q1) Implement Hash Table algorithm with an array. . The array size is 33 -The ha

Question

Q1) Implement Hash Table algorithm with an array. . The array size is 33 -The hash function is hash(i) ® abs(i) % length Resolve collisions by implementing linear probing Include methods add, remove and contains . Your code should provide rehash method if the hash table is full up to 75% Q2) Suppose you are given the following array of integers 1. After inserting the numbers into a tree, construct a valid min 2. Implement heap sort algorithm by repeatedly calling remove 3. You can use a supplementary array for sorting 6, 50, 11, 25, 42, 20, 104, 76, 19, 55, 88, 2 heap tree for this sequence the root method by using arrays 4. Print the intermediate array after step 1 and also the intermediate arrays after each iteration in step 2

Explanation / Answer

1.

import java.io.*;
import java.util.*;

class HashEntry {
      private int key;
      private int value;

      HashEntry(int key, int value) {
            this.key = key;
            this.value = value;
      }     

      public int getKey() {
            return key;
      }
      public int getValue() {
            return value;
      }
      public void setValue(int v) {
            value = v;
      }
      public void setKey(int a) {
            key = a;
      }

}

public class HashMap {
      private static int TABLE_SIZE = 33;

      HashEntry[] table;

      HashMap() {
            table = new HashEntry[TABLE_SIZE];
            for (int i = 0; i < TABLE_SIZE; i++)
                  table[i] = null;
      }
     
      public void remove(int key){
          int found = 0;
          for (int i = 0; i<TABLE_SIZE; i++){
              if (table[i] != null){
                 if (table[i].getKey() == key){
                    found = 1;
                    table[i] = null;
                 }
              }
          }
          if (found == 0)
             System.out.println("Not found");
      }
      public int get(int key) {
            int hash = (Math.abs(key) % TABLE_SIZE);
            while (table[hash] != null && table[hash].getKey() != key)
                  hash = (hash + 1) % TABLE_SIZE;
            if (table[hash] == null)
                  return -1;
            else
                  return table[hash].getValue();
      }


      public void rehash(){
          int a = 2 * TABLE_SIZE;
          HashEntry[] table1 = new HashEntry[a];
          HashEntry[] table2 = table1;
          for (int i = 0; i < TABLE_SIZE; i++)
                  table2[i] = null;

          table1 = table;
          table = table2;
          for (int i = 0; i < TABLE_SIZE; i++){
               if (table1[i] != null){
                  add(table1[i].getKey(),table1[i].getValue());
               }         
          }
          TABLE_SIZE = a;
      }

      public void add(int key, int value) {
            int hash = (key % TABLE_SIZE);
            while (table[hash] != null && table[hash].getKey() != key)
                  hash = (hash + 1) % TABLE_SIZE;
            table[hash] = new HashEntry(key, value);
            int count = 0;
            for (int i = 0; i<TABLE_SIZE; i++){
                if (table[hash] !=null)
                   count++;
            }
            double d = TABLE_SIZE;
            if (count > 0.75 * TABLE_SIZE)
               rehash();
      }

}

2.

public class HeapSort
{
    public void removeRoot(int arr[], int i){ // Removinng root means we are shifting root to the last position
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
    }
    public void sort(int arr[])
    {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);
        for (int i=n-1; i>=0; i--)
        {
            removeRoot(arr,i);
            heapify(arr, i, 0);
            System.out.println("Step " + i);
            for (int j = 0; j<arr.length; j++)
                System.out.print(arr[j] + " ");
            System.out.println();
        }
    }

    void heapify(int arr[], int n, int i)
    {
        int largest = i; // Initialize largest as root
        int l = 2*i + 1; // left = 2*i + 1
        int r = 2*i + 2; // right = 2*i + 2

        if (l < n && arr[l] > arr[largest])
            largest = l;

        if (r < n && arr[r] > arr[largest])
            largest = r;

        if (largest != i)
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
           
        }
    }

    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();
    }

    public static void main(String args[])
    {
      
        int arr[] = {-6, 50, 11, 25, 42, 20,104,76,19,55,88,2};
        int n = arr.length;

        HeapSort ob = new HeapSort();
        ob.sort(arr);

        System.out.println("Sorted array is");
        printArray(arr);
    }
}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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