Below is the class that needs to be implemented public class HashMap { private f

Question

Below is the class that needs to be implemented
public class HashMap { private final static int TABLE_SIZE = 100;
HashEntry[] table;
HashMap() { //Implement }
public String get(int key) { // Implement }
public void put(int key, String value) { // Implement }
public void linearProbe(int key, String value){ // Implement }
public void quadraticProbe(int key, String value){ // Implement }
} public class HashMap { private final static int TABLE_SIZE = 100;
HashEntry[] table;
HashMap() { //Implement }
public String get(int key) { // Implement }
public void put(int key, String value) { // Implement }
public void linearProbe(int key, String value){ // Implement }
public void quadraticProbe(int key, String value){ // Implement }
} Implement a hashing function. Use the hashing function to create a hash table implementation. Implement linear and quadratic probing methods and compare their performance with Red Black Trees. In-class Assignments: 1. Use the Java source files HashEntryjava and HashMapjava provided in canvas. 2. Create a hash table that is made of elements HashElement(int Key, String value). The size of hash table will be 100. 3. Implement the following methods for the hash table: a. put int Key, String Value): i. Puts the key value pair in the hash table at a certain index. ii. You need to implement a simple hash function HOkey) key mod mapsize to find the index where you will put the pair. iii. If collision occurs, ie, a pair already exists in that index and the key is not the same as the current key, then you will use this function to resolve the collision, H(key) (7 H(key)+1) mod mapsize, until you get an empty slot. iv. If the index is already full and the keys are the same, just replace the old value with the new one. b, getint Key): i. Gets the value associated with the Key. ii. You should not do linear search throughout the hash table for the key, rather you will calculate the index using the hash function stated above, go directly to that index and retrieve the value. 4. Write a driver program to test your implementation of hash table. Allow the user to put or get data. CS303 Lab Assignment 5. Implement linear probing to put a new value in your hash table. The sequence of probes are HOkey) CH(key) +imod mapsize for i 0. l.2, 3, and so on. 6. Implement quadratic probing to put a new value in your hash table. The sequence of probes are HCRey)-(H(key) mod mapsize for i 0, I, 2, 3, nd so on. I of 2

Explanation / Answer

public class HashMap {
   private final static int TABLE_SIZE = 100;
   private int currSize = 0;
   // Demo Class
   public class HashEntry{
       public HashEntry(int key, String value){
           this.key = key;
           this.value = value;
       }
       int key;
       String value;
   }
   HashEntry[] table;

   HashMap() {
       table = new HashEntry[TABLE_SIZE];
   }
   public void put(int key,String value){
       int index = hash(key);
       int originalIndex = index;
       if(table[index]==null){ // table[index].isEmpty() can be used too
           HashEntry entry = new HashEntry(key,value);
           table[index] = entry;
           currSize++;
           return;
       }
       boolean repeated = false;
       boolean checked[] = new boolean[TABLE_SIZE];
       while(!repeated){
           index = ((7*index)+1)%TABLE_SIZE;
           if(table[index]==null){ // table[index].isEmpty() can be used too
               HashEntry entry = new HashEntry(key,value);
               table[index] = entry;
               currSize++;
               return;
           }
           if(checked[index]==true){
               table[originalIndex] = new HashEntry(key,value);
               return;
           }else{
               checked[index] = true;
           }
       }
   }
  
   private int hash(int key) {
       return key%TABLE_SIZE;
   }
  
  
   public String get(int key){
       boolean checked[] = new boolean[TABLE_SIZE];
       int index = hash(key);
       if(table[index].key==key){
           return table[index].value;
       }
       while(true){
           index = ((7*index)+1)%TABLE_SIZE;
           if(checked[index]==true)
               return null;
           if(table[index].key==key){
               return table[index].value;
           }else{
               checked[index] = true;
           }
       }
   }
  
   public void linearProbe(int key, String value)
{
int tmp = hash(key);
int i = tmp;
do
{
if (table[i] == null)
{
table[i].key = key;
table[i].value = value;
currSize++;
return;
}
if (table[i].key==key)
{
table[i].value = value;
return;
}
i = (i + 1) % TABLE_SIZE;
} while (i != tmp);   
}
  
   public void quadraticProbe(int key, String value)
{
int tmp = hash(key);
int i = tmp;
do
{
if (table[i] == null)
{
table[i].key = key;
table[i].value = value;
currSize++;
return;
}
if (table[i].key==key)
{
table[i].value = value;
return;
}
i = (i + i*i) % TABLE_SIZE;
} while (i != tmp);   
}
  
}

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

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