//implement other functions: rehashing and findprime public static void main() {

Question

//implement other functions: rehashing and findprime

public static void main() {
  MyHashTable hashtable = new MyHashTable(11);
  System.out.println(hashtable.hash(5));
  for(int i = 1; i <= 4; i++)
   hashtable.put(11*i, 11*i*10);
  hashtable.printArray();
  for(int i = 1; i <= 4; i++)
   System.out.println(hashtable.get(11*i));
  
  //when i = 5, rehashing function should be called automatically from put function
  //because hashtable has 5 items, m/2 = 11/2 = 5
     //the size of new hashtable should be 23
  for(int i = 5; i <= 10; i++)
   hashtable.put(11*i, 11*i*10);
  
  hashtable.printArray();
  
  //put into the hashtable with more items
  //you can generate your own version of key-value pairs, do not have to (11*i, 11*i*10)
  //note that all keys and values must be nonzero, it is important.
  //because in this homework, we are assuming 0 as the empty bucket.
  
}
}

3. (60)Hashtable with Quadratic Probing. Implement a simple hashtable using quadratic probing for collision resolution. Both the keys and values are integers, assuming greater than 0. The initial table size rn should be 11 (it is too small for a real hashtable, we just use it for the purpose of this homework). Let n be the number of items in the table. When nm/2, use the technique of dynamic arrays to enlarge the table. You want to approximately double the table size but keep to the primes. The next table size m will be 23 You should use key%m as the hash function. Let b be the hash value modulo m. If bucket b is occupied, you probe (D+ 12) % m, (D+ 22) % m, (b+32) % m, . .. , (D+ (m/2)2) % m, and stop as soon as you find an empty bucket As long as n is kept less than m/2, you will find an empty bucket by the end of the probing You should at least implement the following functions (a) void put (int key, int value): insert key-value pair to the hashtable. Insert key to the key array, value to the value array based on the hash function (b) int get (int key): get the value of the key (c) boolean contains(int key): return true if the hashtable contains the key d)void remove(int key): remove the key-value pair (e) void rehashing): this method is called automatically when n 2 m/2. You should enlarge he table and use findPrime(2 m) to get the new table size. You need to compute new hash index for every key stored in the existing hash table (f) nt findPrime(int x): find the next (the smallest) prime bigger than x. For example, ndPrime(8)-11, findPrime(22) 23

Explanation / Answer

public int findPrime(int a){

   int prime = 0;
   while(prime == 0){
       a = a + 1;
       prime = 1;
       for (int i = 2; i < a; i++){
         if (a % i == 0)
             prime = 0;
       }
   }
   return a;
}

public void rehashing(){

     int n1 = findPrime(2*m);
     int[] newkeys = new int[n];
     int[] newvalue = new int[n];
     int[] tempkeys = new int[m];
     int[] tempvalues = new int[m];
     for (int i = 0; i<m; i++){
         tempkeys[i] = keys[i];
         tempvalues[i] = values[i];
     }
     k = m;
     keys = newkeys;
     values = newvalues;
     m = n1;
     n = 0;
     for (int i = 0; i<k; i++){
         put(tempkeys[i],tempvalues[i]);
     }
    
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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