The code bellow is for linear probing in hash tables. You are asked to modify insert and delete methods, so they will pe

[answerhappygod]

The code bellow is for linear probing in hash tables. You are
asked to modify insert and delete methods, so they will perform
quadratic probing Instead of linear probing
// ---Do not change DataItem class
----------------------------------
public class DataItem {
private int key; // key to hash
private int value; // (key,value):DataItem
public DataItem(int k) {
this.key=k;
}
public DataItem(int k, int v) {
this.key=k;
this.value=v;
}
public void setKey(int key) {
this.key = key;
}
public int getKey() {
return key;
}
public int getValue() {
return value;
}
}
//Modify insert and delete methods only
public class HashTable {
private int arraySize;
private DataItem hashArray[];
private DataItem delItem;
private int nbElem;
//constructor
public HashTable(int s) {
this.arraySize = s ;
this.hashArray = new DataItem[arraySize];
this.delItem=new DataItem(-1); //to mark deleted items
nbElem=0;
}
public int hashFunction(int key) {
return key%arraySize;
}
public void insert(DataItem dItem) {
if(! isFull()) {
int hashValue= hashFunction(dItem.getKey());
while(hashArray[hashValue]!=null &&
hashArray[hashValue].getKey()!=-1) {
hashValue++;
hashValue=hashValue%arraySize;
}
hashArray[hashValue]=dItem;
nbElem++;
}
else
System.out.println("Hash Table is Full");;
}
public DataItem delete(int key) {
int hashValue= hashFunction(key);
while(hashArray[hashValue]!=null) {
if (hashArray[hashValue].getKey()==key) {
DataItem temp=hashArray[hashValue];
hashArray[hashValue]=delItem;
return temp;
}
hashValue++;
hashValue%=arraySize;
}
return null;
}
public void display() {
System.out.print("Hash Table: {");
for(int i=0;i<arraySize-1;i++) {
if(hashArray!=delItem && hashArray!=null) {
System.out.print(hashArray.getKey()+":"+hashArray.getValue()+",
");
}
else if(hashArray==delItem )
System.out.print(" del, ");
else
System.out.print(" null, ");
}
if(hashArray[arraySize-1]!=delItem &&
hashArray[arraySize-1]!=null)
System.out.println(hashArray[arraySize1].getKey()+":"+hashArray[arraySize-1].getValue()+"}
");
else if(hashArray[arraySize-1]==delItem )
System.out.println(" del } ");
else
System.out.println(" null } ");
}
public boolean isFull() {
return nbElem==arraySize;
}
}
// ---------- do not change the HashTableApp class
-------------------
public class HashTableApp {
public static void main(String[] args) {
HashTable myHashTable = new HashTable(7);
System.out.println("Quadratic probing:");
myHashTable.display();
System.out.println("\nInsert 50, 700, 76, 85, 92, 73, 101");
DataItem insItem = new DataItem(50);
myHashTable.insert(insItem);
insItem = new DataItem(700);
myHashTable.insert(insItem);
insItem = new DataItem(76);
myHashTable.insert(insItem);
insItem = new DataItem(85);
myHashTable.insert(insItem);
insItem = new DataItem(92);
myHashTable.insert(insItem);
insItem = new DataItem(73);
myHashTable.insert(insItem);
insItem = new DataItem(101);
myHashTable.insert(insItem);
myHashTable.display();
//700, 50, 85, 73, 101, 92, 76
System.out.println("\nDelete 85:");
myHashTable.delete(85);
myHashTable.display();
System.out.println("\nDelete 92:");
myHashTable.delete(92);
myHashTable.display();
}
}
When run your program needs to generate the following
output.
Output:
Quadratic probing:
Hash Table: {null, null, null, null, null, null, null}
Insert 50, 700, 76, 85, 92, 73, 101
Hash Table: {700:0, 50:0, 85:0, 73:0, 101:0, 92:0, 76:0}
Delete 85:
Hash Table: {700:0, 50:0, del, 73:0, 101:0, 92:0, 76:0}
Delete 92:
Hash Table: {700:0, 50:0, del, 73:0, 101:0, del, 76:0}